Analysis of Post-Quantum Cryptography Use in Practice

摘要

Quantum computers are able to destroy most, if not absolutely all conventional cryptosystems that are widely used in practice, specifically, systems based on the problem of factoring integers (e.g., RSA). Some cryptosystems like RSA system with 4 000- bit keys are considered useful to protect classic computers from attacks, but probably absolutely useless against attacks on quantum computers. One of the alternatives are post-quantum systems, systems based on lattices. These systems are known for high security levels based on the worst-case hardness. They are based on the complexity of the problems grids, the main of which is the problem of the shortest vector (SVP). In fact, we consider the approximate option when we find a lattice vector, with the length of a(n) times more than the shortest nonzero vector. ±(n) is the approximation coefficient, n is the lattice size. The best known algorithm for grids problems is LLL algorithm. This algorithm needs polynomial time with approximation factor 2°^a In 1987, Schnorr extended LLL algorithm and improved this approximation ratio, but he increased the performance of the algorithm. Schnorr replaced core of LLL algorithm by blocks of larger size. We analyze the advantages and disadvantages of the lattice based crypto systems. We consider the attacks on these systems and propose defenses against these attacks. These defenses decrease the efficiency of the systems and make the systems inefficient. Cryptosystems based on NTRU allow to implement a directional encryption as well as the digital signature, so it is possible to build a public key infrastructure, which will be fully based on the NTRU cryptosystem. It makes this cryptosystem very important for practical use. So in the article we analyze whether NTRU can be implemented in practice. From our results we can conclude that crypto-system NTRU has such advantages as faster encryption and decryption of the messages, faster key generation and cryptographic resistance compared to RSA The main advantage of this cryptographic system is resistance to quantum computer attacks. Thus, it can be argued that the crypto system NTRU is prospective. But it is also evident from these results that the key in NTRU system is bigger than in RSA that causes loss of efficiency. It should be also noted that the size of the signature in NTRU is not constant. It is also necessary to use concrete parameters for NTRU safety. It is also worth to note that even the right formed signature does not always pass the verification. In the article we also check the safety of NTRUsign without perturbation techniques before it has lost its efficiency in different threat models and show that the system is not secure in CPA model. So, we show that despite the fact that lattice-based cryptosystems for post-quantum period are proposed, the attacks on them are still fixed, and they are not effective enough. Thus, for the creation and implementation of safe and effective lattice-based post-quantum cryptosystems, it is necessary to conduct quite a big work.