  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.
