Post-quantum cryptography
Encyclopedia
Post-quantum cryptography refers to research on cryptographic primitive
s (usually public-key cryptosystems) that are not breakable using quantum computer
s. This term came about because most currently popular public-key cryptosystems rely on the integer factorization problem or discrete logarithm problem, both of which would be easily solvable on large enough quantum computers using Shor's algorithm
. Even though current publicly known experimental quantum computing is nowhere near powerful enough to attack real cryptosystems, many cryptographers are researching new algorithms, in case quantum computing becomes a threat in the future. This work is popularized by the PQCrypto conference
series since 2006.
In contrast, most current symmetric cryptography (symmetric ciphers and hash function
s) is secure from quantum computers. The quantum Grover's algorithm
can speed up attacks against symmetric ciphers, but this can be counteracted by increasing key size. Thus post-quantum cryptography does not focus on symmetric algorithms.
Post-quantum cryptography is also unrelated to quantum cryptography
, which refers to using quantum phenomena to achieve secrecy.
Currently post-quantum cryptography is mostly focused on four different approaches:
Cryptographic primitive
Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build computer security systems. These routines include, but are not limited to, one-way hash functions and encryption functions.- Rationale :...
s (usually public-key cryptosystems) that are not breakable using quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
s. This term came about because most currently popular public-key cryptosystems rely on the integer factorization problem or discrete logarithm problem, both of which would be easily solvable on large enough quantum computers using Shor's algorithm
Shor's algorithm
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...
. Even though current publicly known experimental quantum computing is nowhere near powerful enough to attack real cryptosystems, many cryptographers are researching new algorithms, in case quantum computing becomes a threat in the future. This work is popularized by the PQCrypto conference
Academic conference
An academic conference or symposium is a conference for researchers to present and discuss their work. Together with academic or scientific journals, conferences provide an important channel for exchange of information between researchers.-Overview:Conferences are usually composed of various...
series since 2006.
In contrast, most current symmetric cryptography (symmetric ciphers and hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
s) is secure from quantum computers. The quantum Grover's algorithm
Grover's algorithm
Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....
can speed up attacks against symmetric ciphers, but this can be counteracted by increasing key size. Thus post-quantum cryptography does not focus on symmetric algorithms.
Post-quantum cryptography is also unrelated to quantum cryptography
Quantum cryptography
Quantum key distribution uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages...
, which refers to using quantum phenomena to achieve secrecy.
Currently post-quantum cryptography is mostly focused on four different approaches:
- Lattice-based cryptography such as NTRUNTRUNTRU is an asymmetric cryptosystem. It has two characteristics that make it interesting as an alternative to RSA and Elliptic Curve Cryptography; speed and quantum computing resistance. There are two NTRU based algorithms: NTRUEncrypt and NTRUSign...
and GGHGGH encryption schemeThe Goldreich–Goldwasser–Halevi lattice-based cryptosystem is an asymmetric cryptosystem based on lattices. There is also a GGH signature scheme.... - Multivariate cryptographyMultivariate CryptographyMultivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over finite fields. In certain cases those polynomials could be defined over both a ground and an extension field. If the polynomials have the degree two, we talk about...
such as Unbalanced Oil and VinegarUnbalanced Oil and VinegarThe Unbalanced Oil and Vinegar scheme is a modified version of the Oil and Vinegar scheme designed by J. Patarin. Both are Digital signature schemes, used in Cryptography. They belong to the group of multivariate cryptography. The security of this signature scheme is based on an NP-hard... - Hash-based signatures such as Lamport signatures and Merkle signature schemeMerkle signature schemeThe Merkle signature scheme is a digital signature scheme based on hash trees and one-time signatures such as the Lamport signature scheme. It was developed by Ralph Merkle in the late 70s and is an alternative to traditional digital signatures such as the Digital Signature Algorithm or RSA...
- Code-based cryptography that relies on error-correcting codes, such as McEliece encryptionMcEliece cryptosystemIn cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process...
and Niederreiter signaturesNiederreiter cryptosystemIn cryptography, the Niederreiter cryptosystem is a variation of the McEliece Cryptosystem developed in 1986 by Harald Niederreiter. It applies the same idea to the parity check matrix H of a linear code....