[Cryptography] quantum computers & crypto

[Jerry Leichter]

> Another way to state the same thing is that a symmetric cipher with key of N bits is N/2-bits quantum-safe. This is because they're only vulnerable to Grover's algorithm, which is the quantum search algorithm.
> 
> So yeah, if you (e.g.) use AES-256, it's got quantum security of 128 bits.
BTW, to the limited degree I understand this, it's a *really* worst-case estimate.  To actually get the speedup, you need an oracle that can tell you if you've "guessed right."  To be useful, the oracle has to itself be implemented as a quantum computation - i.e., on a mixed state:  If you first measure, then use a classical implementation of the oracle (i.e., you first measure, then try out the key you get using a classical implementation of AES), you've lost your advantage.

Exactly what searches allow you to construct such an oracle is a very non-trivial question.  I don't think we know if it's possible for AES.  If it is possible, it could well require a huge number of quantum gates - i.e., the naive approach would be to essentially replicate a classical implementation using quantum gates, but that's so far beyond anything we can imagine doing today as to not be worth worrying about.  Of course there might be a better approach; I don't believe we know.
                                                        -- Jerry