quantum chip built
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 Alten
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography