quantum chip built

Michael Cordover mjec at mjec.net
Fri Jan 13 11:04:33 EST 2006

John Denker wrote:
> alex at alten.org wrote:
>> From what I understand simple quantum computers can easily brute-force 
>> attack RSA keys or other
>> types of PK keys.  
> My understanding is that quantum computers cannot "easily" do anything.

Au contraire, quantum computers can easily perform prime factoring or 
perform discrete logarithms - this is Shor's algorithm and has been 
known for more than a decade.  The difficulty is in making a QC.

>> Is ECC at risk too?  And are we at risk in 10, 20 or 30 years from now?

ECC is also at risk because it relies on the difficulty of discrete 
logarithms which are victim to a quantum attack.  Are we at risk in 10, 
20 or 30 years?  Well, as John said, it's hard to say.  The first 
working 2 qbit computers were demonstrated in 1998, then 3 qbits in the 
same year.  7 qbits were demonstrated in 2000.  8 in December 2005.  As 
you can see, adding a qbit is pretty hard.  In order to factor a 1024 
bit modulus you'd need a 1024 bit QC.  Perhaps if there were some sudden 
breakthrough it'd be a danger in a decade - but this is the same as the 
risk of a sudden classical breakthrough: low.

My assessment: nothing to worry about for now or in the immediate 
future. A key valid for 20 years will face much greater dangers from 
expanding classical computer power, weak implementations, social 
engineering etc.  The "quantum chip" is just a new housing, not anything 
that puts RSA or ECC at risk.


Michael Cordover

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list