[Cryptography] information, Shannon, and quantum mechanics

[Viktor Dukhovni]

On Wed, Feb 25, 2015 at 11:57:52PM -0500, Jerry Leichter 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.  "In 100 years" means
> your computation has to take place in a hypersphere in space-time of radius
> 100 light years, by 100 years time.  (This is a gross over-estimate:  If
> you want the answer to come back to *you*, the spatial size is limited to
> 50 light years.  But let's be generous.)  I had done a back-of-the-envelope
> estimate and came up with a QM limit for K of somewhere between 128 and
> 256.  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?

-- 
	Viktor.