Re:The year in post-quantum crypto [video]
by PQfanboy on Sunday December 30, 2018 @07:29PM
(#18792188)
Thank you for your perspective.
I should've been more specific: is it at all likely that Grover's will enable faster/feasible search of "quantum algorithm space" (?) or crypto_algo_classical_implementations-space? Or are we limited by number of qubits and QEC for the foreseeable future?
... Quantum Algorithm Zoo: http://math.nist.gov/quantum/zoo/
I think 2027 is beyond optimistic. We still haven't solved quantum storage (in fact, there's a strong argument that it might not be physically possible since you'd likely need 4-dimensional media to store passively-error-correcting qubits) or any other number of fairly fundamental issues before we can actually run CrackPrivateKey().
> Will Grover's algorithm find a more efficient approach?
Grover's algorithm is the optimum speedup for problems of its form ("brute force" searches), and it gives a square-root speedup. So doubling keys solves post-quantum for Grover's algorithm.
Shor's algorithm gives an exponential speedup, and so is going to always be a better speedup.