Article

Breaking iterated knapsacks

Author:

Proceedings of CRYPTO 84 on Advances in cryptology

Pages 342 - 358

Published: 23 August 1985 Publication History

Abstract

This paper presents an outline of an attack that we have used successfully to break iterated knapsacks. Although we do not provide a proof that the attack almost always works, we do provide some heuristic arguments. We also give a detailed description of the examples we have broken.

References

[1]

L. Adleman, "On Breaking the Iterated Merkle-Hellman Public Key Cryptosystem," Advances in Cryptology , Proceedings of Crypto 82, Plenum Press 1983, 303-308.

Google Scholar

[2]

E. F. Brickell, "Solving Low-Density Knapsacks," to appear in Advances in Cryptology , Proceedings of Crypto 83, Plenun Press.

Google Scholar

[3]

E. F. Brickell, J. C. Lagarias and A. M. Odlyzko, Evaluation of Adleman's Attack on Multiply Iterated Knapsacks (Abstract), to appear in Advances in Cryptology , Proceedings of Crypto 83, Plenum Press.

Google Scholar

[4]

E. F. Brickell and G. J. Simmons, "A Status Report on Knapsack Based Public Key Cryptosystems," Congressus Numerantium 37 (1983), 3-72.

Google Scholar

[5]

Y. Desmedt, J. Vandewalle, R. Govaerts, "A Critical Analysis of the Security of Knapsack Public Key Algorithms, preprint.

Google Scholar

[6]

J. C. Lagarias, "Simultaneous Diophantine Approximation of Rationals by Rationals, preprint.

Google Scholar

[7]

J. C. Lagarias, "Knapsack Public Key Cryptosystems and Diophantine Approximation," to appear in Advances in Cryptology , Proceedings of Crypto 83, Plenum Press.

Google Scholar

[8]

J. C. Lagarias and A. M. Odlyzko, "Solving Low-Density Subset Sum Problems, Proc. 24th Annual IEEE Symposium on Foundations of Computer Science (1983), 1-10.

Digital Library

Google Scholar

[9]

A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz, "Factoring Polynomials with Rational Coefficients," Math. Annalen , 261 (1982), 515-534.

Google Scholar

[10]

R. Merkle and M. Hellman, "Hiding Information and Signatures in Trapdoor Knapsacks," IEEE Trans. Information Theory IT-24 (1978), 525-530.

Google Scholar

[11]

A. M. Odlyzko, "Cryptanalytic Attacks on the Multiplicative Knapsack Cryptosystem and on Shamir's Fast Signature Scheme," preprint.

Google Scholar

[12]

M. Petit, "Etude mathematique de certains systemes de cipherement: les sacs a dos," doctor's these, Universite de Rennes, France.

Google Scholar

[13]

A. Shamir, "A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem," Proc. 23rd Annual Symposium on Foundations of Computer Science (1982), 145-152.

Crossref

Google Scholar

[14]

A. Shamir, "The strongest knapsack-based cryptosystem," presented at Crypto 82.

Google Scholar

Cited By

View all

Aggarwal DChen YKumar RLi ZStephens-Davidowitz NMarx D(2021)Dimension-preserving reductions between SVP and CVP in different p-normsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458209(2444-2462)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458209
Aggarwal DDadush DRegev OStephens-Davidowitz NServedio RRubinfeld R(2015)Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian SamplingProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746606(733-742)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746606
Lee M(2013)Improved cryptanalysis of a knapsack-based probabilistic encryption schemeInformation Sciences: an International Journal10.1016/j.ins.2012.07.063222(779-783)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ins.2012.07.063
Show More Cited By

Index Terms

Breaking iterated knapsacks

Recommendations

Multistart Iterated Tabu Search for Bandwidth Coloring Problem

This paper presents a Multistart Iterated Tabu Search (MITS) algorithm for solving Bandwidth Coloring Problem (BCP) and Bandwidth MultiColoring Problem (BMCP). The proposed MITS algorithm exhibits several distinguishing features, such as integrating an ...
Interactive Knapsacks

The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete problems, interactive knapsack heuristic decision problem (IKHD), interactive knapsack decision problem (IKD) and multidimensional ...
Interactive Knapsacks

The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete problems, interactive knapsack heuristic decision problem (IKHD), interactive knapsack decision problem (IKD) and multidimensional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Proceedings of CRYPTO 84 on Advances in cryptology

August 1985

491 pages

ISBN:0387156585

Editors:
G R Blakley,
David Chaum

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 August 1985

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Aggarwal DChen YKumar RLi ZStephens-Davidowitz NMarx D(2021)Dimension-preserving reductions between SVP and CVP in different p-normsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458209(2444-2462)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458209
Aggarwal DDadush DRegev OStephens-Davidowitz NServedio RRubinfeld R(2015)Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian SamplingProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746606(733-742)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746606
Lee M(2013)Improved cryptanalysis of a knapsack-based probabilistic encryption schemeInformation Sciences: an International Journal10.1016/j.ins.2012.07.063222(779-783)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.ins.2012.07.063
Koblitz N(2012)Crypto galore!The Multivariate Algorithmic Revolution and Beyond10.5555/2344236.2344240(39-50)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2344236.2344240
Herold GMeurer A(2012)New attacks for knapsack based cryptosystemsProceedings of the 8th international conference on Security and Cryptography for Networks10.1007/978-3-642-32928-9_18(326-342)Online publication date: 5-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32928-9_18
Encinas LMasqué JDios A(2009)Analysis of the efficiency of the Chor-Rivest cryptosystem implementation in a safe-parameter rangeInformation Sciences: an International Journal10.1016/j.ins.2009.08.030179:24(4219-4226)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.ins.2009.08.030
Micciancio D(2007)Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way FunctionsComputational Complexity10.1007/s00037-007-0234-916:4(365-411)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1007/s00037-007-0234-9
Johnson D(2005)The NP-completeness columnACM Transactions on Algorithms10.1145/1077464.10774761:1(160-176)Online publication date: 1-Jul-2005
https://dl.acm.org/doi/10.1145/1077464.1077476
Jiang ZSun XWang Y(2005)Security analysis and improvement of a double-trapdoor encryption schemeApplied Mathematics and Computation10.1016/j.amc.2004.10.026169:1(41-50)Online publication date: 1-Oct-2005
https://dl.acm.org/doi/10.1016/j.amc.2004.10.026
Joux AStern J(1998)Lattice ReductionJournal of Cryptology10.1007/s00145990004211:3(161-185)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1007/s001459900042
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Multistart Iterated Tabu Search for Bandwidth Coloring Problem

Interactive Knapsacks

Interactive Knapsacks

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations