[Cryptography] information, Shannon, and quantum mechanics

Jerry Leichter leichter at lrw.com
Fri Feb 27 10:59:47 EST 2015


On Feb 26, 2015, at 10:25 PM, Viktor Dukhovni <cryptography at dukhovni.org> wrote:
>> A while back on this list, I pointed out that if you wanted to break a
>> K-bit key by brute force in 100 years, at the least, you needed to perform
>> 2^K bit flips just to generate the possibilities....  I later asked a physicist I knew, and he did a more accurate estimate.
>> It turns out that this hypersphere could do about 2^315 bit flips - and
>> store about 2^315 bits of information.  So AES-256 "can be broken in
>> principle" in 100 years by brute force - but you don't need to make the
>> keys all that much larger to eliminate that possibility.  :-)
> IIRC Quantum computers (Grover's algorithm) are hypothesized to
> reduce the classical $2^n$ search time for brute-forcing symmetric
> keys to $2^{n/2}$.  Not sure how that plays into the analysis, but
> perhaps the estimates you quote assume that the attack is essentially
> classical?
I've asked myself the same question.

The guy I spoke to about this works in this field, and I told him why I was asking the question.  So if Grover's Algorithm would affect the answer, I suspect he would have told me.  Then again, he just may not have thought about it in a general context while answering a particular question.

The next time I have the chance, I'll ask for clarification.  My guess at the moment is that Grover's Algorithm doesn't actually help you here, but it's just that, a guess.  http://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf contains a nice discussion of Grover's Algorithm, including some discussion of cryptographic implementations.  I've skimmed it, but it's not the kind of thing that can be understood without a close reading.  I don't know whether it will answer the question at hand.  One thing it makes clear is that Grover's Algorithm is only useful if you can convert your classical query into a quantum oracle "efficiently enough".  If you can't evaluating that query will end up dominating the cost of the overall computation, and you'll lose your apparent speedup.  It's not clear - it may not be known - if you can construct a classical encryption function that cannot be translated into an efficient quantum oracle.

Note that the underlying point - that there's an "in principle" limitation that is based on limits on computation in the physical universe, and that we are actually approaching those limits in some cases - doesn't change, even if the numbers get larger.
                                                        -- Jerry



More information about the cryptography mailing list