Ivannikov Institute for System Programming of the RAS

Computer science. Algorithmic problems.

Start of project – 2014. Customer - FANO.

Different methods of analysis of random graphs, construction of new mathematical models of scale-free graphs (conforming the so-called power law) is a topical area of research concerning the analysis of networks on the Internet (in particular, social networks such as Facebook, Twitter and many others). However, the properties and parameters of these networks can change. To predict such changes it is necessary to study the general properties of mathematical models of such networks which can be considered as random graphs. But the classical theory of the Erdos-Renyi can’t properly describe graphs that arise in applications, and therefore it was necessary to develop the theory of scale-free random graphs, in which the degrees of vertices are distributed on the so-called power law. A number of models for the generation of graphs and some generators were proposed. The specificity of the problem is that the goal is the generation of such graphs with the number of vertices around a billion. To achieve this requires the development of fast algorithms and the use of parallel computing.

Obfuscation program is called any of its transformation which saves the computed program function (equivalent transformation). At the same time it gives the program a form that the extraction of key information about the algorithms and data structures implemented in this program from the text of program (program code) is a time-consuming task.Unlike traditional types of encryption obfuscation does not involve the construction of efficient algorithms for decryption, i.e. restore of the original text of the program, but it requires the preservation of the meaning of the encrypted messages - function computed by obfuscated program. Therefore, the task of obfuscation programs can also be attributed to the field of cryptography and cryptanalysis. It is the duality of this problem and explains that the research for more than 15 years is conducted in two directions: system programming and cryptography, which are very little interaction with each other.

In the study of the mathematical problem of program’s obfuscation should start with the determination of the resistance of obfuscation, which essentially depend on the applications that use obfuscation.


Theoretical Computer Science

Go to the list of projects