Quantum Attacks on Knapsack Cryptosystems

Quantum computers exploit qunatum parallelism and interference to outperform many classical algorithms and solve previously difficult number theory problems, making them the next major weapon in cryptanalysts' attempts to crack current classical encryption schemes. When a practical quantum computer is eventually produced, which cryptosystems will remain secure? We examine cryptosystems based on the knapsack, or subset-sum, problem in number theory.  The problem can be stated as: Given a set B of integers, what subset (if any) sums to the integer S? We focus on H. W. Lenstra's Powerline system of encryption, which can be reduced to a Chor-Rivest knapsack cryptosystem by a solution of the discrete logarithm problem. Exploiting the strengths of quantum computing, we will write a quantum algorithm designed to solve the Powerline system more quickly than possible with current classical methods of attack. Although a full-scale quantum computer does not yet exist, we will test the efficiency of our algorithms by modeling quantum attacks on the Powerline system using a small-scale classical simulation. Our algorithms will demonstrate quantum computing's application to cryptography and help in the search for a post-quantum-computing method of securing information.

Faculty Advisor: Wim Van Dam