Cryptology ePrint Archive: Report 2008/106
Knapsack cryptosystems built on NP-hard instances
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.
Category / Keywords: public-key cryptography /
Publication Info: knapsack, lattice techniques
Date: received 10 Mar 2008
Contact author: laurent evain at univ-angers fr
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Note: 20 pages
Version: 20080312:130732 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]