quantum chip built

Alex Alten alex at alten.org
Fri Jan 13 18:12:48 EST 2006

At 03:04 AM 1/14/2006 +1100, Michael Cordover wrote:
>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.

Hmm, extrapolating forward...

1998 = 2 qubits
2005 = 8 qubits  (a 4x increase in 7 years)
2013 = 32 qubits?
2020 = 128 qubits?
2027 = 512 qubits?
2034 = 2048 qubits?

So, say, somewhere between 20 to 30 years from now current RSA moduli may 
be at risk from the Shor's algorithm.

Is that a reasonable assumption?

If so, would ECC (moduli) also be at risk within this time frame?

- Alex


- Alex Alten

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

More information about the cryptography mailing list