Quantum cryptanalysis of hidden linear forms
Authors: D. Boneh and R. Lipton
Abstract:
Recently there has been a great deal of interest in the power of
``Quantum Computers''. The driving force is the recent
beautiful
result of Shor that shows that discrete log and factoring are solvable
in random quantum polynomial time. We use a method similar to
Shor's
to obtain a general theorem about quantum polynomial time. We show
that any cryptosystem based on what we refer to as a `hidden linear
form'
can be broken in quantum polynomial time.
Our results imply that the discrete log problem is doable in quantum
polynomial time over any group including Galois fields and elliptic
curves. Finally, we introduce the notion of `junk bits' which are
helpful
when performing classical computations that are not injective.
Reference:
In Proceedings of Crypto '95, Lecture Notes in Computer Science, Vol. 963, Springer-Verlag, pp. 424--437, 1995
Full paper: PDF [first posted 11/1997 ]