[Cryptography] quantum computers & crypto

[Jerry Leichter]

> What I recall is what Grover's algorithm is proven optimal in the general case in terms of how fast a quantum algorithm can find a solution for a search problem. Improving on the lower bound requires finding an exploitable mathematical structure in the problem (in AES, that is).
Be careful here.  Breaking AES is *not* exactly a search problem, especially once you consider the case that multiple solutions are possible.  So it's by no means clear that what you can and cannot do.

> Any attempts to apply additional clever tests just mean you do more of the work in each cycle on the quantum computer itself to filter out vad candidates (with more qubits required accordingly), rather than just testing each and every candidate output on a classical computer.
If I recast the problem from:  "Given P, C find K such that C=AES(K,P)" to "Given {Pi,Ci} for i = 1 to N, find K such that for all i, Ci=AES(K,Pi)", the *form* of the problem is exactly as much of a search problem as the original one was; it just has a more complex matching oracle.  It *probably* has effectively the same complexity as the original problem did.
                                                        -- Jerry