1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – poncho Feb 6 '18 at 20:47
  • $\begingroup$ 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. $\endgroup$ – Adam Ierymenko Feb 6 '18 at 21:39
  • $\begingroup$ It's a theoretical question since nothing capable of running Grover's Algorithm for anything beyond maybe a toy problem exists. $\endgroup$ – Adam Ierymenko Feb 6 '18 at 21:39
  • $\begingroup$ 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. $\endgroup$ – SAI Peregrinus Feb 6 '18 at 23:04
  • $\begingroup$ 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. $\endgroup$ – fgrieu Feb 7 '18 at 7:32
4
$\begingroup$

You are right. Indeed, Grover's algorithm has to evaluate the function that is attacked in each iteration (actually the algorithm complexity measure in which you get the square root speed-up is query complexity). And of course, if you make that function more expensive you also make an attack more expensive -- classical as well as quantum. However, here we are switching from asymptotic statements to exact statements. These tend to depend on the exact architecture of a device. E.g., many functions will have different speed on different CPUs even if the clock speed is the same. The problem is that we do not yet know which architecture a future quantum computer will have.

The common thing in research papers is to measure exact complexity of quantum algorithms in terms of T-gate depth. However, this makes two assumptions. First, that the gate set used will be CNOT, T, and second, that T gates dominate execution time (which in this setting is pretty likely). This makes it hard to determine which kind of functions will be especially slow on a quantum computer.

Moreover, also the relation between cost of memory compared to cost of execution time is still open for quantum computers. Hence, it is not clear if a memory-hard function is better than a function that is slow, independent of the available memory. There exist architectures for qubits where keeping state is a lot easier than manipulating it. In these cases the bottleneck would probably be speed, not memory. However, this is all just a look into a crystal ball..., at most confined guessing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.