Re: Quantum slip - Quantum conspiracy

From: William Whyte (wwhyte251_at_yahoo.com)
Date: 05/23/05 

Date: 23 May 2005 06:51:41 -0700

> RSA is toast, DH is toast, ECC I'm not sure of but without the
knowledge I'd still bet it's toast, Ntru almost certainly toast, in
short I can't think of a single PKI algorithm that I believe would be
safe. RSA and DH are done in by Shor's algorithm.

ECDL and standard DL are both broken by Shor in similar ways. The best
paper about this is "Shor's discrete logarithm quantum algorithm for
Elliptic Curves" by John Proos and Christof Zalka, available from
http://www.cacr.math.uwaterloo.ca/ techreports/2003/corr2003-06.ps. To
solve ECDL over 160-bit prime fields you need a 1000-qubit computer; to
solve RSA-1024 (and presumably DL over 1024-bit fields) you need a
2000-qubit computer. So you can look on ECC as slightly more vulnerable
than RSA or DH/DSA, or you can look on ECC, RSA and DH/DSA as being
essentially equally vulnerable.

As far as NTRU goes, Christoph Ludwig
(http://www.cdc.informatik.tu-darmstadt.de/mitarbeiter/cludwig.html)
has published a paper with a quantum algorithm that claims to
square-root the running times for lattice reduction relative to a
specific algorithm due to Claus Schnorr. We at NTRU don't dispute the
square-rooting part of his result (though we do dispute other aspects
of his paper, which we think is based on a misunderstanding of the
effectiveness of Schnorr's algorithm -- see
http://eprint.iacr.org/2005/104 for more details). Even with this
result, running times for NTRU lattice reduction remain fully
exponential.

To the best of my knowledge, there are no quantum algorithms that
significantly improve breaking times for HFE-based cryptosystems, such
as the QUARTZ and SFLASH signature schemes.

Relevant Pages

  • Re: Public Key Encryption: The Weakest Link
    ... we'll call this the RSA number because they are the most likely ... going that close to the line with ECC, and you'll find that in anything I ... 256-bit ECC key should cover a 128-bit symm, I'd still recommend 512 though ... NTRU, I honestly haven't kept up on it, the constraints I work in very often ...
    (sci.crypt)
  • Re: Why hasnt NTRU gained more penetration?
    ... I am not a big fan of the quantum ideologues claiming that quantum will end RSA and ECC, but was intrigued by the key size arguments. ... Why has NTRU not made similar progress as ECC? ... quantum algorithm that makes solving NTRU trivial. ...
    (sci.crypt)
  • Re: Why hasnt NTRU gained more penetration?
    ... I am not a big fan of the quantum ideologues claiming that quantum will end RSA and ECC, but was intrigued by the key size arguments. ... Why has NTRU not made similar progress as ECC? ...
    (sci.crypt)
  • Re: Why hasnt NTRU gained more penetration?
    ... I am not a big fan of the quantum ideologues claiming that quantum will end RSA and ECC, but was intrigued by the key size arguments. ... Why has NTRU not made similar progress as ECC? ... quantum algorithm that makes solving NTRU trivial. ...
    (sci.crypt)
  • Re: IEEE 802.11 security (public key encryption?)
    ... using WEP, I would chose Ntru. ... IEEE 802.11 security (public key encryption?) ... S and A) discovered the RSA system only on their 42nd attempt. ... PS Cryptographers propose and cryptanalysts dispose. ...
    (Security-Basics)