[19636] in cryptography@c2.net mail archive
Re: quantum chip built
daemon@ATHENA.MIT.EDU (Michael Cordover)
Tue Jan 17 10:15:44 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sat, 14 Jan 2006 03:04:33 +1100
From: Michael Cordover <mjec@mjec.net>
To: John Denker <jsd@av8n.com>, alex@alten.org,
cryptography@metzdowd.com
In-Reply-To: <43C7C4A3.6080008@av8n.com>
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.
Regards,
Michael Cordover
--
http://mine.mjec.net/
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
