The Cryptographic Security of Compact Knapsacks.

Abstract

In 1978, Merkle and Hellman introduced a knapsack-based public-key cryptosystem, which received widespread attention. The two major open problems concerning this cryptosystem are: (1) Security: How difficult are the Merkle-Hellman knapsacks? (2) Efficiency: Can the huge key size be reduced? In this paper we analyze the cryptographic security of knapsack problems with small keys, develop a new (non-enumerative) type of algorithm for solving them, and use the algorithm to show that under certain assumptions it is as difficult to find the hidden trapdoors in Merkle-Hellman knapsacks as it is to solve general knapsack problems. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1980
Accession Number
ADA084456

Entities

People

  • Adi Shamir

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Cryptography
  • Equations
  • Generators
  • Inequalities
  • Integrals
  • Number Theory
  • Numbers
  • Polynomials
  • Prime Numbers
  • Probability
  • Random Variables
  • Rational Numbers
  • Real Numbers
  • Security
  • Theorems

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Cybersecurity.
  • Educational Psychology
  • Inertial Navigation Systems.