13 - Insecurity of the knapsack one-time pad

Summary

O'Connor proposed an approximation to the one-time pad which has similarities to the knapsack cryptosystems, but which he hoped would circumvent the low density attacks on these systems. In this report it will be shown the method proposed is insecure, being susceptible to attacks based on the short lattice vector algorithm.

Introduction

Public key cryptosystems based on the knapsack trapdoor have been considered insecure since a polynomial time algorithm was found for breaking instances of the code. In particular, the Lenstra, Lenstra and Lovasz algorithm for producing short basis vectors of a lattice has proved useful in attacking the diophantine approximation problems which arise in attempts to break the codes. O'Connor [3] has proposed an interesting variant of the knapsack cryptosystem. Unfortunately, as will be shown, the diophantine equations associated with the system fall to the short basis vector attack. All instances of the proposed system that have been generated to test the system have been broken. It seems that there are many sets of parameters that will generate any instance of the code, and it is too easy to find such a set.