From: Michael Nielsen (mnielsen@theory.caltech.edu)
Date: Sat Jul 10 1999 - 05:02:05 MDT
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
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:04:26 MST