4 ms·
It is [1]. Quantum computers, using Shor's algorithm, polynomially break any specialization of the abelian hidden subgroup problem; see [2] for a fairly complet
by pbsd 13y ago
It is [1]. Quantum computers, using Shor's algorithm, polynomially break any specialization of the abelian hidden subgroup problem; see [2] for a fairly complete list.
Whatever reason to prefer elliptic curves over integer factorization or discrete log-based schemes must be classical.
[1] http://arxiv.org/abs/quantph/0301141 http://arxiv.org/abs/quantph/0301141
[2] http://pqcrypto.org/quantum.html http://pqcrypto.org/quantum.html
- sillysaurus 13y agoOh. Then which (if any) algorithm is currently believed to be safe from quantum computing? I think I was thinking of lattice-based cryptography.
- tptacek 13y agoThere's a bunch of them. There's no known quantum algorithm for quickly decoding binary linear codes, so McEliece is one. The Clostest Vector Problem in linear algebra is another trapdoor that may be QC-resistent. You didn't ask, but it's worth saying: block ciphers, stream ciphers and hash functions aren't thought to be fundamentally threatened by QC the way IFP and DLP number theoretic cryptosystems are.