[19641] in cryptography@c2.net mail archive
Re: quantum chip built
daemon@ATHENA.MIT.EDU (Alex Alten)
Tue Jan 17 10:18:35 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Fri, 13 Jan 2006 15:12:48 -0800
To: Michael Cordover <mjec@mjec.net>, John Denker <jsd@av8n.com>,
cryptography@metzdowd.com
From: Alex Alten <alex@alten.org>
In-Reply-To: <43C7CF91.9070705@mjec.net>
At 03:04 AM 1/14/2006 +1100, Michael Cordover wrote:
>John Denker wrote:
>>alex@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
possibly
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@metzdowd.com
