# Real world performance of (still theoretical) Grover's Algorithm

Grover's Algorithm is a quantum algorithm for searching "black box" functions and could be used to reduce the search space for things like symmetric ciphers and hashes by as much as half (quadratic speedup). This would effectively reduce e.g. SHA-256 to 128 bits or AES-128 to 64 bits.

... in theory, of course. Nobody's built a QC that can run Grover's Algorithm yet and I doubt one will exist that can do it for anything other than toy problems for quite a while.

That being said I have a question about how Grover's algorithm works.

My understanding is that in Grover's algorithm there is a classical step in which the classical function must be evaluated for a given point to test if that point is the correct answer.

If that's the case, could you practically limit the performance of a post-quantum search by designing an intentionally expensive and inefficient algorithm? I'm thinking of some of the memory-hard compound hash monstrosities like CryptoNight that are used in the cryptocurrency world as block hash / mining functions. Would a slow complicated memory-hard algorithm effectively limit the performance of Grover's algorithm in the real world by making each iteration terribly slow? So even if you get quadratic speedup, 2^64 or 2^128 searches of something that takes 250ms of classical compute time per search would still take an absurd amount of time.

Thoughts?

• If you require $2^{128}$ searches (e.g. against AES-256, actually, any practical attack by Grover's on AES-256 will require far more searches), why do you believe that's not enough? Why do you think we need to make it more expensive for the legitimate users? – poncho Feb 6 '18 at 20:47
• I'm thinking of shorter things like AES-128 or a 128-bit compound hash. It would be impractical to brute force 2^128 in any reasonable amount of time on classical hardware (unless you wanted to spend absurd amounts on ASICs) but I'm wondering about future quantum hardware. – Adam Ierymenko Feb 6 '18 at 21:39
• It's a theoretical question since nothing capable of running Grover's Algorithm for anything beyond maybe a toy problem exists. – Adam Ierymenko Feb 6 '18 at 21:39
• It's faster to just use AES-256 than to make AES-128 slow enough. Since there are hash functions of sufficient length and symmetric ciphers of sufficient key size I'm not sure what the point would be. – SAI Peregrinus Feb 6 '18 at 23:04
• Rather than a slow AES-128, the practitioner wanting a relatively short key (so as to be memorable) will use password-based, memory-hard key derivation to generate a 256-bit key for AES-256. Good luck to Grover's algorithm with Balloon and the intricacies of what makes a password memorable.. That actually goes in the direction of the question. – fgrieu Feb 7 '18 at 7:32