3 ms·
This is hard to answer because many quantum algorithms useful for cryptanalysis have probably not been discovered yet. See, for example, the debacle surrounding
by pbsd 11y ago
This is hard to answer because many quantum algorithms useful for cryptanalysis have probably not been discovered yet. See, for example, the debacle surrounding Soliloquoy [1], an algorithm that despite being based on the hardness of lattice reduction has a fast quantum algorithm.
Anyway, a quantum-resistant algorithm is usually meant to be one that resists the exponential speedup given by Shor's algorithm and its variants. In other words, a quantum-resistant algorithm can't be based on the hardness of integer factorization, discrete logarithms on any abelian group, class groups, and so on (i.e. all instances of the Abelian hidden subgroup problem).
The leading candidates for such hard problems are decoding a random linear code (McEliece), shortest/closest vector finding in a lattice (NTRU, GGH, [R]LWE, ...), multivariate equation system solving (HFE and friends), and in the specific case of digital signatures one-way functions (Merkle Tree signatures).
[1] http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Syste...