Re: The effects of quantum computers

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

Date: 26 Sep 2005 06:48:24 -0700

D. J. Bernstein wrote:
> Adam O'Brien wrote:
> > Are other types of asymmetric algorithms susceptible to QC's?
>
> Christoph Ludwig has a paper combining Schnorr's random-sampling
> lattice-reduction algorithm with Grover's algorithm to attack NTRU. Of
> course, Grover's algorithm isn't as scary as Shor's algorithm, but the
> NTRU key sizes will need to be increased.

Ludwig claims to square-root the time needed to reduce NTRU lattices --
it's a speed-up but the time is still fully exponential. We dispute
some of his analysis: see
http://www.ntru.com/cryptolab/articles.htm#2005_2. Briefly, he claims
to square-root the time of Schnorr's RSR, and therefore that NTRU
keysizes need to be doubled. However:

a) NTRU breaking times are obtained not from RSR but from the BKZ
reduction algorithm, which appears experimentally to be faster at the
NTRU's recommended lattice dimensions.

b) He square-roots the worst-case running time. However, in practice,
the actual running time of lattice reduction algorithms is much less
than the worst-case running time. It's not clear that the quantum
algorithm proposed will square-root actual running times.

Having said that, we don't dispute that NTRU key sizes will probably
need to be increased in a post-QC world. It's just a question of how
much.

Relevant Pages

  • Re: New algorithm for the isomorphism of graphs
    ... complicated algorithm works better (avoids backtracking entirely, ... indexed variable, assigning a value to a variable, or comparing two ... so, once you "big O" it, you end up with a running time of 1. ... in polynomial time. ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... complicated algorithm works better (avoids backtracking entirely, ... indexed variable, assigning a value to a variable, or comparing two ... so, once you "big O" it, you end up with a running time of 1. ... in polynomial time. ...
    (sci.math)
  • Re: Merging mixed data sets
    ... > which will swap the data members, usually 3 for begin and size ... algorithm is not strongly dependant on random element access ... the running time of the whole algorithm is O). ...
    (comp.lang.cpp)
  • Re: need to write a pseudocode
    ... David C. Ullrich wrote: ... altitude varies because ... I don't know what it means to write an algorithm in O. ... If we said that the _running time_ for the algorithm was O ...
    (sci.math)
  • Re: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... graphs which are "pathological", so most of the time, you can solve NP- ... This is also why the average running time is not a good measure; ... isomorphism problem, where you only look at graphs with at most 400 ...
    (sci.math)