Post-Quantum Cryptography

Overview

The major public-key cryptography schemes, such as RSA, DSA, and ECDSA, which are used today on the Internet and in blockchain applications, are based on algorithms that are vulnerable to quantum attacks and can easily be broken by Shor’s algorithm if an adversary is in possession of a large-scale quantum computer.

Thus, it’s a crucial task to identify quantum-safe cryptographic primitives that might serve as the basis for post-quantum algorithms for digital signing in future public-key infrastructures. There are numerous references, reports, and recommendations to post-quantum cryptography from various standard institutions, such as NISTLily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner, and Daniel Smith-Tone. Report on post-quantum cryptography. Technical report, April 2016. and ETSIEuropean Telecommunications Standards Institute. Quantum safe cryptography and security. Technical report, June 2015. ETSI White Paper No.8. Consequently, there is a number of classes of algorithms that are believed to be resistant to attacks from both classical and quantum computers.

Code-based cryptography

The major example of code-based cryptography is McEliece’s (1978)Robert J. McEliece. A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report, 44:114-16, January 1978 . public-key encryption system, whose security is based on the hardness of decoding general linear codes. The cryptosystem has barely been used in real applications since the public keys are represented by large matrices, which yields to extremely large key sizes. However, the McEliece cryptosystem is believed to be quantum-resistant since it’s not vulnerable to Shor’s algorithm.

Lattice-based cryptography

Lattice-based cryptography has received a lot of attention for postquantum approaches as they offer efficient implementations and as they have very strong security proofs. A lattice $\mathcal{L}$ of $\mathcal{R}^{n}$ is a discrete subgroup of $\mathcal{R}^{n}$, or more formally (Daniele Micciancio (2011)Daniele Micciancio. Lattice-Based Cryptography, pages 713-15. Boston, MA, 2011 . Springer US.):

Lattice

A lattice $\mathcal{L}$ is a set that can be expressed by the sum of integer multiples of vectors, i.e.,

$$\mathcal{L}\left(b_{1}, \ldots, b_{n}\right)=\left\{\sum_{i=1}^{n} x_{i} b_{i}: x_{i} \in \mathbb{Z} \text { for } 1 \leq i \leq n\right\}$$

of $n$ linearly independent vectors $b_{1}, \ldots, b_{n} \in \mathbb{R}^{n}$, which form the basis of the lattice.

Lattice-based systems rely on lattice problems, which are known to be NP-hard, such as the Shortest Vector Problem (SVP), where the problem is to find the shortest nonzero vector in the lattice. This problem is considered to be hard in both classical and quantum computation models. Hoffstein, Pipher, and Silverman (1998)Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In Proceedings of the Third International Symposium on Algorithmic Number Theory, ANTS-III, pages 267-88, Berlin, Heidelberg, 1998. Springer-Verlag. proposed the first practical lattice-based public-key cryptosystem, named NTRU, which is based on the SVP in a lattice. The system allows both encryption and digital signatures. The most efficient lattice-based signature scheme is the Bimodal Lattice Signature Scheme (BLISS) (Léo Ducas et al. (2013)Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. Lattice signatures and bimodal Gaussians. Cryptology ePrint Archive, Report 2013/383, 2013. https://eprint.iacr.org/2013/383.).

Hash-based cryptography

Hash-based signature schemes offer many advantages since their security only relies on the one-wayness of hash functions $H$, whose security is very well understood. Furthermore, it’s well-known that cryptographic hash functions are hard to invert, also for quantum computers, since Grover’s algorithm only yields a quadratic speed-up. For example, Amy et al. (2016)Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, and John Schanck. Estimating the cost of generic quantum preimage attacks on SHA-2 and SHA-3. Cryptology ePrint Archive, Report 2016/992, 2016. https://eprint.iacr. org/2016/992. have shown that the SHA-2 and SHA-3 hash functions are quantum-resistant, as a preimage attack of Grover’s search algorithm against SHA-256 and SHA3-256 leads to a total cost of about $2^{166}$ logical qubit-cycles while requiring $2^{12.6}$ or $2^{20}$ qubits, respectively. Hash-based signature schemes offer fast signing and verification operations and are easy to implement. We give a brief introduction to hash-based cryptosystems in this lesson.

Multivariate polynomial cryptography

The security of multivariate public-key cryptosystems (MPKC) is based on the assumption of the hardness of solving systems of multivariate nonlinear equations, usually polynomials, over a finite field. The signature scheme SFLASH, which is based on the Matsumoto-Imai scheme, was accepted as a security standard by the New European Schemes for Signature, Integrity, and Encryption (NESSIE) in 2003, but was subsequently completely broken by Dubois et al. (2007)Vivien Dubois, Pierre-Alain Fouque, Adi Shamir, and Jacques Stern. Practical cryptanalysis of SFLASH. In CRYPTO, volume 4622 of Lecture Notes in Computer Science, pages 1-12. Berlin, 2007. Springer.. Given a public key, the attack required about one second to forge a signature for any message. Actually, the most promising signature scheme is Rainbow, which was proposed by Ding and Schmidt (2005)Jintai Ding and Dieter Schmidt. Rainbow, a new multivariable polynomial signature scheme. In Proceedings of the Third International Conference on Applied Cryptography and Network Security, ACNS’05, pages 164-75, Berlin, Heidelberg, 2005. SpringerVerlag..