Pustovit O. Application of theories of extreme graphs to modern problems of information security

The dissertation, devoted to the solution of a topical scientific and practical problem, reveals the methods of data protection involved in the Big Data call and the first samples of a quantum computer appear. A new class of groups and semigroups of transformations of the affine space K^n is considered, which satisfy the properties of superposition, ie, the possibility of calculating the product of n elements for the polynomial time T (n). These algebraic objects are defined in terms of special graphs defined by the commutative ring K. They are the tool for constructing cryptographic algorithms in the cases K=F_q (finite field), Z_m (arithmetic ring of surpluses modulo m), K=B(m,2) (Boolean ring of size 2^n). The paper describes in detail a new flow symmetric encryption algorithm for the known family of graphs A (n, K) and the corresponding group of cubic transformations of the open text space K^n. The encoding speed O (n) is comparable to the file read speed. With a certain length restriction, different slogans correspond to different ciphers. The properties of mixing were investigated based on the results of computer simulation. It is shown that linearization attacks require O(n^3) plaintext / corresponding ciphertext interceptions. The complexity of the linearization attack is O(n^10). The algorithm is supported by a secure post-quantum protocol, the safety of which is determined by the task of scheduling the transformation of the Cremona group into the product of known generators. Fast, post-quantum stable algorithms for creating digests of electronic documents are offered. New algorithms with a public key defined by transformations from many variables of unlimited degree are described. The properties of new asymmetric El Gamal-type encryption algorithms defined by post-quantum protocols are investigated. New digital signature algorithms are proposed, the security of which is also determined by post quantum protocols of non-commutative cryptography, defined in terms of cryptography from many variables.