On breaking generalized knapsack public key cryptosystems

1 January 1983

conference paper
Published by Association for Computing Machinery (ACM)

p. 402-412
https://doi.org/10.1145/800061.808771

Abstract

In this paper new methods, generalizing those of Shamir, are presented for attacking generalizations of the basic system. It is shown how these methods may be applied to the Graham-Shamir public-key crypto-system [2], and the iterated Merkle-Hellman public-key cryptosystem. We are unable to present a rigorous proof that the attacks presented here are effective. However, in the case of the Graham-Shamir system, the methods have been implemented and have performed well in tests. The method of attack uses recent results of Lenstra, Lenstra, and Lovasz [5]. The cryptanalytic problem is treated as a lattice problem rather than a linear programming one as in Shamir's result.

Keywords

KNAPSACK PUBLIC KEY CRYPTOSYSTEMS
ITERATED MERKLE-HELLMAN PUBLIC-KEY CRYPTOSYSTEM
GRAHAM-SHAMIR SYSTEM
LINEAR PROGRAMMING
RIGOROUS PROOF
GRAHAM-SHAMIR PUBLIC-KEY CRYPTO-SYSTEM
CRYPTANALYTIC PROBLEM
PAPER NEW METHOD
LATTICE PROBLEM
RECENT RESULT
BASIC SYSTEM
FILES
PUBLIC KEY
RANDOM ACCESS
LINEAR PROGRAM

This publication has 0 references indexed in Scilit: