quantum chip built

[leichter_jerrold at emc.com]

| >> 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
majordomo at metzdowd.com
| 

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