Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions (extended abstract)

We study a generalization of the compact knapsack problem for arbitrary rings: given ring elements and a target value , find coefficients (where is a subset of of size ) such that . The computational complexity of this problem depends on the choice of the ring and set of coefficients . This problem is known to be solvable in quasi polynomial time when is the ring of the integers and is the set of small integers . We show that if is an appropriately chosen ring of modular polynomials and is the subset of polynomials with small coefficients, then the compact knapsack problem is as hard to solve on the average as the worst case instance of approximating the covering radius (or the length of the shortest vector, or various other well known lattice problems) of any cyclic lattice within a polynomial factor. Our proof adapts, to the cyclic lattice setting, techniques initially developed by Ajtai for the case of general lattices.