|
|
|
Given a Sum and a set of Weights, find the Weights which were used to generate the Sum. The values of the weights are then encrypted in the sum. The system relies on the existence of a class of knapsack problems which can be solved trivially (those in which the weights are separated such that they can be ``peeled off'' one at a time using a Greedy-like algorithm), and transformations which convert the trivial problem to a difficult one and vice versa. Modular multiplication is used as the Trapdoor Function. The simple knapsack system was broken by Shamir in 1982, the Graham-Shamir system by Adleman, and the iterated knapsack by Ernie Brickell in 1984.
References
Coppersmith, D. ``Knapsack Used in Factoring.'' §4.6 in
Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath).
New York: Springer-Verlag, pp. 117-119, 1987.
Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 163-166, 1985.