Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

The authors investigate the average-case complexity of a generalization of the compact knapsack problem to arbitrary rings: given m (random) ring elements a1,. .., am 2 R and a (Random) target value b 2 R, find coefficients x1,. .., xm ε S (where S is an appropriately chosen subset of R) such that ∑ai ? xi = b. They consider compact versions of the generalized knapsack where the set S is large and the number of weights m is small. Most variants of this problem considered in the past (e.g., when R = Z is the ring of the integers) can be easily solved in polynomial time even in the worst case.