Recent Advances in Lattice-Based Cryptography

Lattice theory was first introduced to cryptography as a cryptanalysis tool to analyze knapsack and RSA cryptosystem. In 1997, Ajtai and Dwork constructed the first lattice cryptography: Ajtai-Dwork; and then in 1998, NTRU is appeared. Since factorization and discrete logarithm based cryptography was the mainstream, lattice-based cryptography has not received enough attention. Until 2009, Gentry constructed the first fully homomorphic encryption, which led to a wide of development of lattice cryptography. In 2015, Peikert made a summary of the development of lattice cryptography in “A decade of lattice cryptography”. Also in 2015, NIST released “Report on post-quantum cryptography”. According to the report, due to the rapid development of quantum computation technology, the existing standard of public key cryptography in quantum computing will be no longer safe. At the same time, NIST has launched a worldwide collection of quantum cryptography algorithms. As a classic quantum-resistant cryptography, lattice-based cryptography is known as the most promising competitor. Therefore, lattice cryptography has attracted much attention in recent years, and a lot of excellent results have been appeared. In this paper, we summarize the main results of lattice cryptography for the past two years, which consist of zero-knowledge proofs, encryption, signature and key exchange; and at last, we outlook the development trend of lattice-based cryptography.