[insanitybit]

It's also unclear (to me, perhaps not to others!) if the conversion from O(2^n) -> O(2^n/2) means it will be faster in practice on quantum hardware.

https://eprint.iacr.org/2017/811

> Reassessing Grover's Algorithm

The proposal of this paper is that Grover's does not mean we need to double the size of symmetric keys to account for QM but that just a few extra bits are enough to prevent it from being efficient.

Of course, there may be new QM algorithms that don't suffer and, again, it's best to start preparing now and not later. But I think it's noteworthy for the discussion about quantum preparedness.

[mthiim]

This conversion O(2^n) -> O(2^n/2) only applies to Grover's algorithm which can be used to break symmetric crypto (AES etc.). This is not the usual concern in the context of quantum computers because it just corresponds to halving the key space (in bits) which you can protect against by doubling the key size. So use AES-256 instead of AES-128. And the benefit by Grovers can only be had once. And as the paper you link to point out, maybe even that benefit is in question.

However, the main concern with quantum computers vs cryptography is Shor's algorithm which works on RSA and ECC. Shor's has the potential to take the problem from exponential (or at least close to exponential but sub, in the case of RSA) to polynomial O(n^3) which is much more powerful (essentially taking a log of the running time!). That is still assuming, of course, that workable quantum computers of required since will appear and that all the associated problems with that (noisy qbits etc.) are solved. Other challenges could also show up (difficulties scaling for longer computations, more passes through quantum gates, larger super-positions or even that the quantum laws governing e.g. probability amplitudes don't hold with full accuracy at such scales).

[insanitybit]

Yeah, my point was more that there's a lot of "this QM version of the algorithm destroys that crypto scheme" when it may be a lot more nuanced. I used Grover's as an example of that - on its face Grover's implies that you need to double the key size to be safe but there's reason to believe that that's not true in practice. I assume that may be the case with Shor's as well.

The best thing to do is to layer them, as is standard.