Re:Quantum Attack on Public-Key Algorithm
by tptacek on Friday December 05, 2014 @05:44PM
(#8707359)
The subtext of Schneier's post is that a lattice encryption scheme was found vulnerable to a QC algorithm, which is meaningful because lattice encryption schemes are seen as a promising post-quantum crypto scheme --- that is, a scheme that would, unlike RSA (IFP), DH (DLP) and ECC (ECDLP), remain secure even if it becomes feasible to deploy large-scale quantum computers.
Two things worth knowing:
* There are multiple hard lattice problems in number theory (the paper refers to one of them in the conclusion). And other lattice schemes have been found vulnerable, to non-quantum attacks.
* There are multiple hard problems not involving integer lattices that are believed to be hard for quantum computers. McEliece, for instance, is another well-known candidate for post-quantum public key crypto, and it's based on linear codes, not lattices. Lamport signatures[1] realize public key crypto purely from hash functions (which aren't hugely weakened by QC.) A good intro to these issues:
Two things worth knowing:
* There are multiple hard lattice problems in number theory (the paper refers to one of them in the conclusion). And other lattice schemes have been found vulnerable, to non-quantum attacks.
* There are multiple hard problems not involving integer lattices that are believed to be hard for quantum computers. McEliece, for instance, is another well-known candidate for post-quantum public key crypto, and it's based on linear codes, not lattices. Lamport signatures[1] realize public key crypto purely from hash functions (which aren't hugely weakened by QC.) A good intro to these issues:
http://pqcrypto.org/www.springer.com/cda/content/document/cd...
Nick Weaver's "what if all trapdoors are vulnerable to QC" comment seems a little premature.
[1]: http://en.wikipedia.org/wiki/Lamport_signature