gotchaMinor
What is the difference between classical crypto and post-quantum crypto?
Viewed 0 times
theclassicalwhatdifferencecryptobetweenpostandquantum
Problem
Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be needed to change?
Solution
Summary of this paper providing a (partial) answer.
There are two kinds of traditional public-key cryptographic methods: those based on integer factorization, and those based on the discrete logarithm, including elliptic-curve-based methods. These models are believed to be hard in the classical models, but have been shown that neither is hard in the quantum model.
Although Grover developed a quantum algorithm providing quadratic speedup for searching, Bennet, Bernstein, Brassard and Vazirani showed that the quantum model couldn't allow exponential speedup for search problems. This suggests symmetric encryption algorithms, one-way functions and cryptographic hashes should resist quantum-based attacks. The focus, then, should be on developing secure public-key methods.
Lamport signatures may provide a one-time signature mechanism secure against quantum attacks. Lattice problems may form the basis for public-key methods which are resistant to quantum attacks; in particular, the NP-Hard shortest-vector and closest-vector problems are attractive. For both the classical and quantum models, these problems are believed to be hard for lattices of high dimension. The NTRU family of cryptographic algorithms, based on lattice problems, may provide a practical means of achieving public-key cryptography resistant to quantum attacks. Another problem which might serve as a basis for secure public key methods is the syndrome decoding problem. The McEliece encryption system is based on this problem, and variants may provide a way forward.
There are two kinds of traditional public-key cryptographic methods: those based on integer factorization, and those based on the discrete logarithm, including elliptic-curve-based methods. These models are believed to be hard in the classical models, but have been shown that neither is hard in the quantum model.
Although Grover developed a quantum algorithm providing quadratic speedup for searching, Bennet, Bernstein, Brassard and Vazirani showed that the quantum model couldn't allow exponential speedup for search problems. This suggests symmetric encryption algorithms, one-way functions and cryptographic hashes should resist quantum-based attacks. The focus, then, should be on developing secure public-key methods.
Lamport signatures may provide a one-time signature mechanism secure against quantum attacks. Lattice problems may form the basis for public-key methods which are resistant to quantum attacks; in particular, the NP-Hard shortest-vector and closest-vector problems are attractive. For both the classical and quantum models, these problems are believed to be hard for lattices of high dimension. The NTRU family of cryptographic algorithms, based on lattice problems, may provide a practical means of achieving public-key cryptography resistant to quantum attacks. Another problem which might serve as a basis for secure public key methods is the syndrome decoding problem. The McEliece encryption system is based on this problem, and variants may provide a way forward.
Context
StackExchange Computer Science Q#1595, answer score: 6
Revisions (0)
No revisions yet.