quantum chip built

[Michael Cordover]

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.

Regards,

Michael Cordover
-- 
http://mine.mjec.net/

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