Post quantum cryptography: lattice based cryptography and analysis of NTRU public key cryptosystem
In 1994, Peter Shor has developed a quantum algorithm for integer factorization and the discrete logarithm problem, known as Shor's algorithm. This was a great finding in the quantum field, given that it makes essentially all currently used cryptographic constructions (such as RSA and ECC) easily breakable by a quantum computer. Since quantum computers are believed to phisically exist in the next few years, these encryption schemes will be no longer reliable, making the encrypted data compromised. It is thus of crucial importance to build and analyze new quantum resistant cryptographic schemes. These new cryptographic constructions should be efficient and secure enough to be used in practice and standardized for a large number of years, replacing the current ones if needed. In the last year, NIST (National Institute of Standards and Technology, from U.S. Department of Commerce) has announced its quest of finding such quantum resistant cryptographic constructions. The NTRU encryption scheme, developed by Jeffrey Hoffstein, Jill Pipher and Joseph Silverman (the same Silverman famous for his work on elliptic curves) in the 90's, presented in 1996 and published in 1998, is an example of a quantum resistant proposal. Although it is not supported with a theoretical security proof, the scrutiny done since its presentation until now reveal that NTRU is secure and is a good successor for replacing the current constructions currently in use. It is a fact that there already exist some classical cryptosystems that are quantum resistant. The McEliece cryptosystem (1978) is an example of such a quantum resistant construction, but it is not good to be used in practice. The theory behind the NTRU cryptosystem is very simple, therefore easy to understand, and NTRU can be very easily implemented and put in practice: both private and public keys are easy and quickly computable, having O(N) length, making a clear difference between the length O(N2) of other cryptosystems considered as fast, and encrypting and decrypting with NTRU takes O(N2) operations, which makes it considerably faster than RSA and ECC. To date, NTRU remains secure against both classical and quantum computers. The most effective attacks on NTRU are based on lattices, namely using lattice reduction algorithms, which goal is to find very short vectors in a lattice. One can apply the LLL algorithm (1982) of Arjen Lenstra, Hendrik Lenstra and Laszlo Lovasz, which is recognized as a very important achievement in many areas of mathematics. It runs in polynomial time, but has an exponential approximation factor. This algorithm was improved over time. The most important improvement is due to Schnorr (1987) who introduced the Blockwise Korkine Zolotarev algorithm, also known as BKZ algorithm, which is to date the best lattice reduction algorithm to be put in practice. In 2011, Yuanmi Chen and Phong Q. Nguyen improved the BKZ algorithm, revising lattice security estimates, and created the BKZ simulation algorithm, permitting to predict both