Non-injectivity and knapsacks

• Autorzy: Koskinen J.A.
• Języki publikacji: EN

Abstrakty

EN

This paper is a cryptographically motivated study of the knapsack, its subset sum function and its inverse relation, the decipherment function. The novelty is that the subset sum function is not assumed to be injective. Instead, various forms of ``jectivity'' are introduced, distinguished by the amount of subsets that are allowed to have the same sum. Besides charting several general properties of knapsacks and the functions the paper reports on experiments that looked for dense knapsacks. Also a concrete construction of a relatively dense easily decipherable knapsack is presented.

Słowa kluczowe

EN

knapsack; subset sum; cryptography; non-injectivity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 38, Nr 1,2
• Strony: 163--180
• Opis fizyczny: bibliogr. 11 poz.

Twórcy

autor

Koskinen J.A.

• Department of Information Technology, Tampere University of Technology, 33101 Tampere, Finland,