This thesis is devoted to solving the actual scientific problem of development more effective methods (in comparison with brute force method) of solving the LPN problem over finite rings for evaluation of the security of post-quantum symmetric cryptosystems.
Analysis of available scientific publications was carried out. It showed that in spite of the considerable progress in the development of fast methods (more effective in comparison with brute force method) for solving the LPN problem over a field of two elements or some residue rings, the question of the existence of such methods in case of arbitrary finite ring remains open. To date, there are not even noasymptotic estimates of the amount of material sufficient to solve the LPN problem over an arbitrary finite ring properly. The problem of the noasymptotic time complexity of the generalized BKW algorithm, which is a natural extension of one of the best methods for solving the LPN problem over a two-element field in case of arbitrary finite ring, remains unresolved. As a result, the security of many symmetric cryptosystems over finite rings (by analogy with known cryptosystems based on the complexity of the classical LPN problem solving over the field) remains undefined, which holds back the practical application of these cryptosystems in modern information and telecommunication systems.
Analytical estimates of the amount of material sufficient to solve the LPN problem over an arbitrary finite ring properly, that generalize a similar estimate known for the classical LPN problem and allow to determine the time complexity of the generalized BKW algorithm, a known prototype of which is currently one of the most effective algorithms for solving the classical LPN problem are obtained for the first time.
The maximum likelihood method for solving the LPN problem over finite Frobenius rings has been improved based on the fast Fourier transform using, which allows to significantly reduce the time complexity of the LPN problem solving over Frobenius rings, using both the MLM itself and other algorithms that use MLM as an auxiliary procedure.
The maximum likelihood method for solving the LPN problem over residue rings modulo has been improved based on the Fermat number transforms, which enables to significantly reduce the time complexity of the LPN solving using a generalized BKW algorithm.
The method for developing new algorithms for solving the LPN problem over residue rings modulo for an arbitrary finite set of inputs of such algorithms obtained for the first time. It makes it possible to increase the effectiveness of solving this problem by properly selecting a composition of the N number.
New scientific and practical results presented in this thesis allow:
– to purposefully choose the values of the parameters of post-quantum symmetric cryptosystems over finite rings, which guarantee their security against known attacks;
– to reduce (from several times to several dozen orders) the time complexity of solving the LPN problem over finite rings using the maximum likelihood method, as well as the generalized BKW algorithm;
– to establish and prove the inexpediency (from the cryptographic security point of view) of the practical application of LPN-C type encryption systems over the residue ring modulo where ;
– to increase the effectiveness of known attacks on the Ring-LWE encryption system from to times (depending on the encryption system parameters);
– to increase the effectiveness of correlation attacks on SNOW 2.0-like stream ciphers over residue rings modulo from to times (depending on the value and gamma generator length);
– to build SNOW 2.0-like stream ciphers over residue rings modulo , which are reasonably secure against known correlation attacks, in particular, to increase the resistance of SNOW 2.0 cipher from to operations (with increasing of the amount of required material from to ) by completely replacement from boolean bitwise addition in the gamma generator scheme to addition modulo .
Keywords: symmetric post-quantum cryptosystem, LPN problem, time complexity of the algorithm, maximum likelihood method, generalized BKW algorithm, finite ring, security proving, system of linear equations corrupted by noise.
