[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