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

By Daniele Micciancio. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., 2002

390 citations recorded by the source corpus.

Abstract.We investigate the average-case complexity of a generalization of the compact knapsack problem to arbitrary rings: given m (random) ring elements a1,..., am ∈ R and a (random) target value b ∈ R, find coefficients x1, ..., xm ∈ S (where S is an appropriately chosen subset of R) such that ∑ ai · xi = 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={\mathbb{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 = ω(1) with arbitrarily slow growth rate, solving our generalized compact knapsack problems on the average is at least as hard as the worst-case instance of various approximation problems over cyclic lattices. Specific worst-case 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 n1+∈ almost linear in the dimension of the lattice. Our results yield very efficient and provably secure one-way functions (based on worst-case 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 worst-case and average-case complexity of various lattice problems over cyclic and quasi-cyclic lattices.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/7a39aa21686e908238335be385c6e1590dc81942

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Generalized Compact Knapsacks Are Collision Resistant (2006, background): “For any n-dimensional lattice Λ , positive reals (cid:15) < (log n ) − 2log n , s > 2 η (cid:15) (Λ) , and polynomials c, z ∈ R [ x ] of degree less than n , 3 Generalized compact knapsacks and ideal lattices In [15], Micciancio introduced the following generalization of the compact knapsack problem”
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, background): “See the representative works [32, 37, 28, 30, 44, 31] for more details on these functions and their security foundations.”
Faster exponential time algorithms for the shortest vector problem (2010, background): “An interesting feature common to all sieve algorithms is that they can be slightly optimized to take advantage of the structure of certain lattices used in practical cryptographic constructions, like the NTRU lattices [11], or the cyclic lattices of [18].”
Fully homomorphic encryption using ideal lattices (2009, result): “Cryptographic work on ideal lattices includes NTRU [25] and more recent work [ 41 , 32, 33, 48, 49].”
Worst-case to average-case reductions for module lattices (2014, methodology): “To circumvent this inherent inefficiency, Micciancio [21,23] — inspired from the efficient NTRU encryption scheme [15] that can itself be interpreted in terms of lattices — initiated an approach that consists in changing the SIS and LWE problems to variants involving structured matrices.”
Bonsai Trees, or How to Delegate a Lattice Basis (2010, positive): “Fortunately, the principles of bonsai trees may be applied equally well using analogous hard problems and tools for cyclic/ideal lattices (developed in, e.g., [Mic07, PR06, LM06, PR07, SSTX09, LPR10]).”
Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices (2006, background): “where each xi is restricted to some large subset S R. This generalization was proposed by Micciancio, who suggested a specific choice of the ring R and subset S for which inverting the function (for random a,x) is at least as hard as solving certain worst-case problems on cyclic lattices [ 14 ].”
On Ideal Lattices and Learning with Errors over Rings (2010, methodology): “Influenced by the heuristic design of the NTRU cryptosystem [16], Micciancio [ 23 ] proposed a “compact,” efficient one-way function using a ring-based variant of SIS that he showed to be at least as hard as worst-case problems on cyclic lattices.”
Multi-bit Cryptosystems Based on Lattice Problems (2006, background): “[25] Daniele Micciancio.”
SWIFFT: A Modest Proposal for FFT Hashing (2008, methodology): “A first step toward bridging the gap between theoretical constructions and practical functions was taken by Micciancio [13], who proposed using lattices with special structure (namely, cyclic lattices) and showed how they lead to cryptographic functions that have provable worst-case hardness and sti”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “Clearly, the above key sizes are still too large for many applications, but this is a consequence of the quadratic overhead inherent to the use “standard” LWE . By using the compact “ring-based” variant of LWE and cryptosystem from [22] (which is related to the heuristic NTRU scheme [18] and the the”
An Efficient and Parallel Gaussian Sampler for Lattices (2010, neutral): “, [16, 21, 14]).”
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (2009, background): “This result was later extended to give constructions of collision-resistant hash functions by either restricting the domain [29] or changing the ring [18] in Micciancio's scheme.”
New lattice based cryptographic constructions (2003, background): “In another paper [14], Micciancio improved the efficiency of the hash function by using cyclic lattices.”