| >> 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. There is little basis for any real estimates here. First off, you should probably think of current qbit construction techniques as analogous to transistors. If you looked at "number of transistors in a computer" and didn't know that IC's were on the way, you would make much smaller estimates
as to the sizes of practical machines in 1980, much less 2006. But more fundamentally, qbits don't necessarily scale linearly. Yes, current algorithms may need some number of qbits to deal with a key of n bits, but the tradeoff between time and "q-space" is not known. (Then again, the tradeoff between time and space for *conventional* computation isn't known, except for some particular algorithms.) I believe there's a result that if any of some broad class of quantum computations can be done using n qbits, it can also be done with just one (plus conventional bits). | 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. I'm not sure I would be tHat confident. There are too many unknowns - and quantum computation has gone from "neat theoretical idea, but there's no possible way it could actually be done because of <many plausible-sounding arguments>" to "well, yes, it can be done for a small number of bits but they can't really scale it" in a very short period of time. -- Jerry | Regards, | | Michael Cordover | -- | http://mine.mjec.net/ | | --------------------------------------------------------------------- | The Cryptography Mailing List | Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] | --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]