On Thu, 8 Jul 1999 eugene.leitl@lrz.uni-muenchen.de wrote:
> From: bradbury@aeiveos.com (Robert J. Bradbury)
>
> Question: Does anyone know if there is an encryption
> methodology that will work if QC cracks the factoring problem?
I don't have a lot of expertise on these issues, but here's a few comments: the public-key crypto algorithms I understand are all based on the discrete logarithm, knapsack, or factoring problems. All of these problems will be soluble if quantum computers become available. (Discrete log is also being used over elliptic curves; quantum computers can certainly break some such schemes, but those schemes are still in a state of flux.)
(At least some of the knapsack based algorithms are breakable classically.)
There is another class of schemes whose security is based on the "shortest vector in a lattice problem". I don't understand these schemes at all. Variants of the this problem are known to be NP-complete; I haven't understood the proof yet, however. I gather that the security of these schemes is still quite open to question.
Michael Nielsen
Ph: 626 395 8431 Email: mnielsen@theory.caltech.edu
Fax: 626 793 9506 Web: http://www.theory.caltech.edu/~mnielsen/index.html