Paper 2004/286
Generalized compact knapsacks, cyclic lattices, and efficient oneway functions from worstcase complexity assumptions
Daniele Micciancio
Abstract
We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 + ... + a_m*x_m = b. We 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. We propose a new choice of the ring R and subset S that yields generalized compact knapsacks that are seemingly very hard to solve on the average, even for very small values of m. Namely, we prove that for any unbounded function m = omega(1) with arbitrarily slow growth rate, solving our generalized compact knapsack problems on the average is at least as hard as the worstcase instance of various approximation problems over cyclic lattices. Specific worstcase lattice problems considered in this paper are the shortest independent vector problem SIVP and the guaranteed distance decoding problem GDD (a variant of the closest vector problem, CVP) for approximation factors n^{1+epsilon} almost linear in the dimension of the lattice. Our results yield very efficient and provably secure oneway functions (based on worstcase complexity assumptions) with key size and time complexity almost linear in the security parameter n. Previous constructions with similar security guarantees required quadratic key size and computation time. Our results can also be formulated as a connection between the worstcase and averagecase complexity of various lattice problems over cyclic and quasicyclic lattices.
Metadata
 Available format(s)
 PDF PS
 Category
 Foundations
 Publication info
 Published elsewhere. A preliminary version of this paper appears in Proc. of FOCS 2002
 Keywords
 compact knapsackoneway functionslattice techniquescomplexity theorycyclic latticesaveragecaseworstcase connection
 Contact author(s)
 daniele @ cs ucsd edu
 History
 20041103: received
 Short URL
 https://ia.cr/2004/286
 License

CC BY
BibTeX
@misc{cryptoeprint:2004/286, author = {Daniele Micciancio}, title = {Generalized compact knapsacks, cyclic lattices, and efficient oneway functions from worstcase complexity assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2004/286}, year = {2004}, note = {\url{https://eprint.iacr.org/2004/286}}, url = {https://eprint.iacr.org/2004/286} }