A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem

Abstract

The cryptographic security of the Merkle-Hellman cryptosystem has been a major open problem since 1976. In this paper we show that the basic variant of this cryptosystem, in which the elements of the public key are modular multiples of a superincreasing sequence, is breakable in polynomial time.