Integer programming and cryptography

DOI10.1007/BF03024123MaRDI QIDQ799477zbMATH OpenFDO

Authors H. W. jun. Lenstra

Publication date 1984

Published in The Mathematical Intelligencer (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF03024123

zbMATH Keywords

cryptographyinteger coordinatesinteger linear programming problempolynomial-time algorithmtriangle in the plane

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Integer programming (90C10) Applications of mathematical programming (90C90) Cryptography (94A60) Theory of error-correcting codes and error-detecting codes (94B99)

Review text

Several years ago it was shown that there exists a polynomial-time algorithm for the integer linear programming problem with a fixed number of variables [see the author, Math. Oper. Res. 8, 538-548 (1983; Zbl 0524.90067)]. The present paper explains the basic idea behind this algorithm by considering the problem how to decide whether a given triangle in the plane contains a point with integer coordinates. In addition, the paper describes how A. Shamir applied the integer programming algorithm in order to break the cryptographic system proposed by R. C. Merkle and M. E. Hellman [see \textit{A. Shamir}, Proc. 23rd IEEE Symp. Found. Computer Sci., 145-152 (1982)].

Recommendations

• scientific article; zbMATH DE number 3865148
• A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
• Solving low density knapsacks
• A critical analysis of the security of knapsack public-key algorithms
• Solving low-density subset sum problems

Cites work

• A new linear programming algorithm - better or worse than the simplex method?
• Cryptology: The mathematics of secure communication
• Factoring polynomials with rational coefficients
• Hiding information and signatures in trapdoor knapsacks
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables

Cited in

(2)

• Lower time bounds for integer programming with two variables
• On the reduction of a random basis

This page was built for publication: Integer programming and cryptography

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799477)