Quantum computational attack on two diophantine cryptosystems

A computing paradigm based on the principles of quantum physics was first suggested in the early 1980s by Benioff and Feynman and formalized thereafter by Deustch. Since that time, Shor introduced specific polynomial-time quantum algorithms to solve the factoring and discrete logarithm problems and Grover presented a quantum database search algorithm with quadratic improvement over classical search. Shor's method has been generalized to the problem of finding a hidden subgroup within an abelian group G and is intimately connected to the Fourier transform on G. Grover's method is fundamentally different and has a decidedly geometric flavor.; Quantum algorithms offer an inherently parallel structure, which derives from the quantum physical notion of superposition, whereby particles are thought to exist simultaneously in various states, subject to some probability amplitude distribution. In terms of the computing paradigm, we can think of an n-bit quantum register as simultaneously holding all possible 2 n values, again subject to some probability distribution on the values. The power of quantum parallelism, in essence, is that a function can be evaluated simultaneously rather than sequentially on all points in a large space.; The interest in quantum computing and algorithms is stimulated largely by the promise of tractable solutions to problems believed to be intractable within the classical computing model. Among these are those problems underlying all modern encryption schemes, including the two examined here: the NTRU and Chor-Rivest cryptosystems. The most widely used classical technique to attack these systems is lattice basis reduction. The approach taken here is quite different. These problems are treated as inherently generic: find one of some special elements within an unsorted database. Grover's algorithm is then applied in this context.; The basic mathematical notions for the quantum computing paradigm are introduced, followed by a detailed description of Grover's algorithm. The NTRU and Chor-Rivest cryptosystems are then presented, with discussions of conventional attacks and how Grover's algorithm may be applied to these problems.