ACTUALLY, quantum computing does more than just halve the effective key length. With classical computing, the resources required to attack a given key grow exponentially with key length. (a 128-bit key has 2^128 possibilities, 129 has 2^129, etc. etc. you all know this...) With quantum computing, however, the complexity of an attack grows only polynomially. Hence a MUCH MUCH more agreeable time frame for brute force attacks. Good stuff, eh? ~SAM
From: "Trei, Peter" <ptrei@rsasecurity.com> Date: Wed, 16 Oct 2002 14:50:03 -0400 To: David Howe <DaveHowe@gmx.co.uk>, "Email List: Cypherpunks" <cypherpunks@lne.com>, "'David E. Weekly'" <david@weekly.org> Subject: RE: One time pads
David E. Weekly[SMTP:david@weekly.org]
Naive question here, but what if you made multiple one time pads (XORing them all together to get your "true key") and then sent the different pads via different mechanisms (one via FedEx, one via secure courier, one via your best friend)? Unless *all* were compromised, the combined key would still be secure.
As for PKI being secure for 20,000 years, it sure as hell won't be if those million-qubit prototypes turn out to be worth their salt. Think more like 5-10 years. In fact, just about everything except for OTP solutions will be totally, totally fucked. Which means that you should start thinking about using OTP *now* if you have secrets you'd like to keep past when an adversary of yours might have access to a quantum computer. I'd put 50 years as an upper bound on that, 5 years as a lower.
-d
Not quite right. My understanding is that quantum computing can effectively halve the length of a symmettric key, but that does not take it down to zero.
Thus, a 256 bit key would, in a QC world, be as secure as a 128 bit key today, which is to say, pretty good.
It's the asymmetric algorithms which have problems.
Peter
At 09:20 PM 10/16/2002 -0400, Sam Ritchie wrote:
ACTUALLY, quantum computing does more than just halve the effective key length. With classical computing, the resources required to attack a given key grow exponentially with key length. (a 128-bit key has 2^128 possibilities, 129 has 2^129, etc. etc. you all know this...) With quantum computing, however, the complexity of an attack grows only polynomially. Hence a MUCH MUCH more agreeable time frame for brute force attacks. Good stuff, eh?
The speed of quantum computing depends on the algorithm - it's generally believed that for some problems, like factoring, you can hypothetically get a hypothetically-precise-enough quantum computer to resolve in polynomial time instead of exponential, subject to a variety of caveats I don't pretend to understand, but for many other problems they're only cutting the effective number of bits in half (which is still exponentially faster than brute-force, but not *enough* exponentially faster), and for other problems they may not be a match at all. So Peter Trei's assertion that it's really only a big impact on asymmetric cryptosystems, and a much smaller impact on symmetric, is one layer deeper description than yours, and it's something that does still leave us with practical ways to use cryptography that don't include briefcases and handcuffs. Myself, I'd rather hang out at Delphi waiting for the stoned babe to give out the correct answers.... :-) ("If you use the right key, a great kingdom will fall...")
participants (2)
-
Bill Stewart -
Sam Ritchie