Name
Abstract | ||
|---|---|---|
In view of the known difficulty in solving NP-hard problems, a natural question is whether there exist cryptosystems which are NP-hard to crack. In Section I we display two such systems which are based on the knapsack problem. However, the first one, which is highly "linear" has been shown by Lempel to be almost always easy to crack. This shows that NP-hardness of a cryptosystem is not enough. Also, it provides the only natural problem we know of, which is NP-hard and yet almost always easy to solve. The second system is a form of a "double knapsack" and so far has resisted the cryptanalysis efforts. |
Year | DOI | Venue |
|---|---|---|
1980 | 10.1007/3-540-10003-2_71 | ICALP |
Keywords | Field | DocType |
knapsack problem,np hard problem | Discrete mathematics,Combinatorics,Computer science,Generalized assignment problem,Cryptanalysis,Cryptosystem,Continuous knapsack problem,Knapsack problem,Almost surely,Completeness (statistics),Polynomial-time approximation scheme | Conference |
ISBN | Citations | PageRank |
3-540-10003-2 | 21 | 14.60 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| shimon even | 1 | 2873 | 981.78 |
| Yacov Yacobi | 2 | 704 | 133.71 |