Non-Injectivity and Knapsacks

Article type: Research Article

Authors: Koskinen, Jukka A.

Affiliations: Department of Information Technology, Tampere University of Technology, Tampere, Finland. jak@cs.tut.fi

Note: [] Address for correspondence: Tampere University of Technology, P.O.Box 553, FIN-33101 Tampere, Finland.

Abstract: 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.

Keywords: Knapsack, subset sum, cryptography, non-injectivity

DOI: 10.3233/FI-1999-381213

Journal: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 163-180, 1999