Re: Anyone seen the 'quantum cryptanalysis' thread on sci.crypt?

[Jim Hart <hart@chaos.bsu.edu>]

An important question that arises out of this -- do there exist one way
trapdoor functions that are not in BQP, the class of problems solved
in polynomial time by a quantum computer.  In other words, we need
a function where the forward direction and trapdoor inverse are in P, 
but the normal inverse is harder than factorization and discrete 
logarithm, which are in BQP.

If so, then public key cryptography can persist into the era of
the quantym computer; such P/non-BQP trapdoor inverses would be 
the next genration of public key.

Jim Hart
hart@chaos.bsu.edu