quantum chip built

Whyte, William WWhyte at ntru.com
Tue Jan 17 08:51:21 EST 2006

> >From what I understand simple quantum computers can easily 
> brute-force attack RSA keys or other types of PK keys.  Is 
> ECC at risk too?  And are we at risk in 10, 20 or 30 years from now?  

Quantum computers break RSA, cryptosystems based on discrete log 
over finite fields, and cryptosystems based on discrete log over
elliptic curves, where "break" means "reduce to polynomial time".

The best description of the ECC variant of Shor's quantum algorithm
is in Proos and Zalka's "Shor's discrete logarithm quantum algorithm
for elliptic curves", http://arxiv.org/abs/quant-ph/0301141. They
estimate that ~1000 qubits are needed to break a 160-bit ECC key
(as opposed to ~2000 qubits for a 1024-bit RSA key).

NTRU and HFE-based schemes (such as QUARTZ and SFLASH) aren't currently 
known to be broken by quantum algorithms -- there are proposed quantum
algorithms that may square-root the time to break NTRU, but this isn't
a reduction to polynomial time. I don't know if anyone's looked at
quantum computers as applied to HFE.



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

More information about the cryptography mailing list