Post-quantum cryptography

This approach includes cryptographic systems such as learning with errors, ring learning with errors (ring-LWE),[9][10][11] the ring learning with errors key exchange and the ring learning with errors signature, the older NTRU or GGH encryption schemes, and the newer NTRU signature and BLISS signatures.[12] Some of these schemes like NTRU encryption have been studied for many years without anyone finding a feasible attack. Others like the ring-LWE algorithms have proofs that their security reduces to a worst-case problem.[13] The Post Quantum Cryptography Study Group sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU be studied for standardization rather than the NTRU algorithm.[14][15] At that time, NTRU was still patented. Studies have indicated that NTRU may have more secure properties than other lattice based algorithms.[16]

This includes cryptographic systems such as the Rainbow (Unbalanced Oil and Vinegar) scheme which is based on the difficulty of solving systems of multivariate equations. Various attempts to build secure multivariate equation encryption schemes have failed. However, multivariate signature schemes like Rainbow could provide the basis for a quantum secure digital signature.[17] There is a patent on the Rainbow Signature Scheme.

This includes cryptographic systems such as Lamport signatures and the Merkle signature scheme and the newer XMSS[18] and SPHINCS[19] schemes. Hash based digital signatures were invented in the late 1970s by Ralph Merkle and have been studied ever since as an interesting alternative to number-theoretic digital signatures like RSA and DSA. Their primary drawback is that for any hash-based public key, there is a limit on the number of signatures that can be signed using the corresponding set of private keys. This fact had reduced interest in these signatures until interest was revived due to the desire for cryptography that was resistant to attack by quantum computers. There appear to be no patents on the Merkle signature scheme and there exist many non-patented hash functions that could be used with these schemes. The stateful hash-based signature scheme XMSS developed by a team of researchers under the direction of Johannes Buchmann is described in RFC 8391.[20] Note that all the above schemes are one-time or bounded-time signatures, Moni Naor and Moti Yung invented UOWHF hashing in 1989 and designed a signature based on hashing (the Naor-Yung scheme)[21] which can be unlimited-time in use (the first such signature that does not require trapdoor properties).

This includes cryptographic systems which rely on error-correcting codes, such as the McEliece and Niederreiter encryption algorithms and the related Courtois, Finiasz and Sendrier Signature scheme. The original McEliece signature using random Goppa codes has withstood scrutiny for over 30 years. However, many variants of the McEliece scheme, which seek to introduce more structure into the code used in order to reduce the size of the keys, have been shown to be insecure.[22] The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended the McEliece public key encryption system as a candidate for long term protection against attacks by quantum computers.[14]

This cryptographic system relies on the properties of supersingular elliptic curves and supersingular isogeny graphs to create a Diffie-Hellman replacement with forward secrecy.[23] This cryptographic system uses the well studied mathematics of supersingular elliptic curves to create a Diffie-Hellman like key exchange that can serve as a straightforward quantum computing resistant replacement for the Diffie-Hellman and elliptic curve Diffie–Hellman key exchange methods that are in widespread use today. Because it works much like existing Diffie–Hellman implementations, it offers forward secrecy which is viewed as important both to prevent mass surveillance by governments but also to protect against the compromise of long term keys through failures.[24] In 2012, researchers Sun, Tian and Wang of the Chinese State Key Lab for Integrated Service Networks and Xidian University, extended the work of De Feo, Jao, and Plut to create quantum secure digital signatures based on supersingular elliptic curve isogenies.[25] There are no patents covering this cryptographic system.

Provided one uses sufficiently large key sizes, the symmetric key cryptographic systems like AES and SNOW 3G are already resistant to attack by a quantum computer.[26] Further, key management systems and protocols that use symmetric key cryptography instead of public key cryptography like Kerberos and the 3GPP Mobile Network Authentication Structure are also inherently secure against attack by a quantum computer. Given its widespread deployment in the world already, some researchers recommend expanded use of Kerberos-like symmetric key management as an efficient way to get post quantum cryptography today.[27]

In some versions of Ring-LWE there is a security reduction to the shortest-vector problem (SVP) in a lattice as a lower bound on the security. The SVP is known to be NP-hard.[28] Specific ring-LWE systems that have provable security reductions include a variant of Lyubashevsky's ring-LWE signatures defined in a paper by Güneysu, Lyubashevsky, and Pöppelmann.[10] The GLYPH signature scheme is a variant of the Güneysu, Lyubashevsky, and Pöppelmann (GLP) signature which takes into account research results that have come after the publication of the GLP signature in 2012. Another Ring-LWE signature is Ring-TESLA.[29] There also exists a "derandomized variant" of LWE, called Learning with Rounding (LWR), which yields " improved speedup (by eliminating sampling small errors from a Gaussian-like distribution with deterministic errors) and bandwidth."[30] While LWE utilizes the addition of a small error to conceal the lower bits, LWR utilizes rounding for the same purpose.

The security of the NTRU encryption scheme and the BLISS[12] signature is believed to be related to, but not provably reducible to, the Closest Vector Problem (CVP) in a Lattice. The CVP is known to be NP-hard. The Post Quantum Cryptography Study Group sponsored by the European Commission suggested that the Stehle–Steinfeld variant of NTRU which does have a security reduction be studied for long term use instead of the original NTRU algorithm.[14]

Unbalanced Oil and Vinegar signature schemes are asymmetric cryptographic primitives based on multivariate polynomials over a finite field ${\displaystyle \mathbb {F} }$. Bulygin, Petzoldt and Buchmann have shown a reduction of generic multivariate quadratic UOV systems to the NP-Hard Multivariate Quadratic Equation Solving problem.[31]

In 2005, Luis Garcia proved that there was a security reduction of Merkle Hash Tree signatures to the security of the underlying hash function. Garcia showed in his paper that if computationally one-way hash functions exist then the Merkle Hash Tree signature is provably secure.[32]

Therefore, if one used a hash function with a provable reduction of security to a known hard problem one would have a provable security reduction of the Merkle tree signature to that known hard problem.[33]

The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended use of Merkle signature scheme for long term security protection against quantum computers.[14]

The McEliece Encryption System has a security reduction to the Syndrome Decoding Problem (SDP). The SDP is known to be NP-hard[34] The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended the use of this cryptography for long term protection against attack by a quantum computer.[14]

In 2016, Wang proposed a random linear code encryption scheme RLCE[35] which is based on McEliece schemes. RLCE scheme can be constructed using any linear code such as Reed-Solomon code by inserting random columns in the underlying linear code generator matrix.

Security is related to the problem of constructing an isogeny between two supersingular curves with the same number of points. The most recent investigation of the difficulty of this problem is by Delfs and Galbraith indicates that this problem is as hard as the inventors of the key exchange suggest that it is.[36] There is no security reduction to a known NP-hard problem.

The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The basic idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper[46] appeared in 2012 after a provisional patent application was filed in 2012.

In 2014, Peikert[47] presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional 1 bit signal for rounding in Ding's construction is also utilized. For somewhat greater than 128 bits of security, Singh presents a set of parameters which have 6956-bit public keys for the Peikert's scheme.[48] The corresponding private key would be roughly 14,000 bits.

In 2015, an authenticated key exchange with provable forward security following the same basic idea of Ding's was presented at Eurocrypt 2015,[49] which is an extension of the HMQV[50] construction in Crypto2005. The parameters for different security levels from 80 bits to 350 bits, along with the corresponding key sizes are provided in the paper.[49]

For 128 bits of security in NTRU, Hirschhorn, Hoffstein, Howgrave-Graham and Whyte, recommend using a public key represented as a degree 613 polynomial with coefficients ${\displaystyle {\bmod {\left(2^{10}\right)}}}$. This results in a public key of 6130 bits. The corresponding private key would be 6743 bits.[37]

For 128 bits of security and the smallest signature size in a Rainbow multivariate quadratic equation signature scheme, Petzoldt, Bulygin and Buchmann, recommend using equations in ${\displaystyle \mathbb {F} _{31}}$ with a public key size of just over 991,000 bits, a private key of just over 740,000 bits and digital signatures which are 424 bits in length.[38]

In order to get 128 bits of security for hash based signatures to sign 1 million messages using the fractal Merkle tree method of Naor Shenhav and Wool the public and private key sizes are roughly 36,000 bits in length.[51]

For 128 bits of security in a McEliece scheme, The European Commissions Post Quantum Cryptography Study group recommends using a binary Goppa code of length at least ${\displaystyle n=6960}$ and dimension at least ${\displaystyle k=5413}$, and capable of correcting ${\displaystyle t=119}$ errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes ${\displaystyle k\times (n-k)=8373911}$ bits. The corresponding private key, which consists of the code support with ${\displaystyle n=6960}$ elements from ${\displaystyle GF(2^{13})}$ and a generator polynomial of with ${\displaystyle t=119}$ coefficients from ${\displaystyle GF(2^{13})}$, will be 92,027 bits in length[14]

The group is also investigating the use of Quasi-cyclic MDPC codes of length at least ${\displaystyle n=2^{16}+6=65542}$ and dimension at least ${\displaystyle k=2^{15}+3=32771}$, and capable of correcting ${\displaystyle t=264}$ errors. With these parameters the public key for the McEliece system will be the first row of a systematic generator matrix whose non-identity part takes ${\displaystyle k=32771}$ bits. The private key, a quasi-cyclic parity-check matrix with ${\displaystyle d=274}$ nonzero entries on a column (or twice as much on a row), takes no more than ${\displaystyle d\times 16=4384}$ bits when represented as the coordinates of the nonzero entries on the first row.

Barreto et al. recommend using a binary Goppa code of length at least ${\displaystyle n=3307}$ and dimension at least ${\displaystyle k=2515}$, and capable of correcting ${\displaystyle t=66}$ errors. With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes ${\displaystyle k\times (n-k)=1991880}$ bits.[52] The corresponding private key, which consists of the code support with ${\displaystyle n=3307}$ elements from ${\displaystyle GF(2^{12})}$ and a generator polynomial of with ${\displaystyle t=66}$ coefficients from ${\displaystyle GF(2^{12})}$, will be 40,476 bits in length.

For 128 bits of security in the supersingular isogeny Diffie-Hellman (SIDH) method, De Feo, Jao and Plut recommend using a supersingular curve modulo a 768-bit prime. If one uses elliptic curve point compression the public key will need to be no more than 8x768 or 6144 bits in length.[53] A March 2016 paper by authors Azarderakhsh, Jao, Kalach, Koziel, and Leonardi showed how to cut the number of bits transmitted in half, which was further improved by authors Costello, Jao, Longa, Naehrig, Renes and Urbanik resulting in a compressed-key version of the SIDH protocol with public keys only 2640 bits in size.[45] This makes the number of bits transmitted roughly equivalent to the non-quantum secure RSA and Diffie-Hellman at the same classical security level.[54]

As a general rule, for 128 bits of security in a symmetric-key-based system, one can safely use key sizes of 256 bits. The best quantum attack against generic symmetric-key systems is an application of Grover's algorithm, which requires work proportional to the square root of the size of the key space. To transmit an encrypted key to a device that possesses the symmetric key necessary to decrypt that key requires roughly 256 bits as well. It is clear that symmetric-key systems offer the smallest key sizes for post-quantum cryptography.