Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Knapsack cryptosystems built on NP-hard instance   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.

5
The categories of this paper are: gr-qc
18
The categories of this paper are: econ
29
The categories of this paper are: funct-an
35
The categories of this paper are: mtrl-th
8
The categories of this paper are: hep-ex
14
The categories of this paper are: math-ph
13
The categories of this paper are: quant-ph
22
The categories of this paper are: chao-dyn
28
The categories of this paper are: alg-geom
0
The categories of this paper are: hep-ph
23
The categories of this paper are: solv-int
7
The categories of this paper are: hep-th
24
The categories of this paper are: dg-ga
3
The categories of this paper are: physics
17
The categories of this paper are: q-fin
16
The categories of this paper are: stat