Non-Injectivity and Knapsacks

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.