Knapsack cryptosystems built on NP-hard instances

Laurent Evain

Paper 2008/106

Knapsack cryptosystems built on NP-hard instances

Laurent Evain

Abstract

We construct three public key knapsack cryptosystems. Standard knapsack cryptosystems hide easy instances of the knapsack problem and have been broken. The systems considered in the article face this problem: They hide a random (possibly hard) instance of the knapsack problem. We provide both complexity results (size of the key, time needed to encypher/decypher...) and experimental results. Security results are given for the second cryptosystem ( the fastest one and the one with the shortest key). Probabilistic polynomial reductions show that finding the private key is as difficult as factorizing a product of two primes. We also consider heuristic attacks. First, the density of the cryptosystem can be chosen arbitrarily close to one, discarding low density attacks. Finally, we consider explicit heuristic attacks based on the LLL algorithm and we prove that with respect to these attacks, the public key is as secure as a random key.

Note: 20 pages

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. knapsack, lattice techniques
Contact author(s): laurent evain @ univ-angers fr
History: 2008-03-12: received
Short URL: https://ia.cr/2008/106
License: CC BY

BibTeX

@misc{cryptoeprint:2008/106,
      author = {Laurent Evain},
      title = {Knapsack cryptosystems built on {NP}-hard instances},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/106},
      year = {2008},
      url = {https://eprint.iacr.org/2008/106}
}