Paper 2020/1276

Lattice-based Key Sharing Schemes - A Survey

Prasanna Ravi, James Howe, Anupam Chattopadhyay, and Shivam Bhasin

Abstract

Public key cryptography is an indispensable component used in almost all of our present day digital infrastructure. However, most if not all of it is predominantly built upon hardness guarantees of number theoretic problems that can be broken by large scale quantum computers in the future. Sensing the imminent threat from continued advances in quantum computing, NIST has recently initiated a global level standardization process for quantum resistant public-key cryptographic primitives such as public key encryption, digital signatures and key encapsulation mechanisms. While the process received proposals from various categories of post-quantum cryptography, lattice-based cryptography features most prominently among all the submissions. Lattice-based cryptography offers a very attractive alternative to traditional public-key cryptography mainly due to the variety of lattice-based schemes offering varying flavors of security and efficiency guarantees. In this paper, we survey the evolution of lattice-based key sharing schemes (public key encryption and key encapsulation schemes) and cover various aspects ranging from theoretical security guarantees, general algorithmic frameworks, practical implementation aspects and physical attack security, with special focus on lattice-based key sharing schemes competing in the NIST's standardization process. Please note that our work is focussed on the results available from the second round of the NIST's standardization process while the standardization process has progressed to the third and final round at the time of publishing this document.

Note: Accepted at ACM Computing Surveys dated August 2020.