Generalized Compact Knapsacks Are Collision Resistant

By Vadim Lyubashevsky, Daniele Micciancio. International Colloquium on Automata, Languages and Programming, 2006

389 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/353989647d2f76abd61a50fa8cc133574db1bcca

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 Computer Vision and Pattern Recognition

Citations in the corpus

Making NTRU as Secure as Worst-Case Problems over Ideal Lattices (2011, background): “Peikert, Rosen, Lyubashevsky and Micciancio [43, 24] later suggested to change the ring to Zq[x]/Φ with a Φ that is irreducible over the rationals, sparse, and with small coe cients (e.”
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (2012, methodology): “Next we will present two key facts in the RLWEf,q,χ setting defined above, which are needed for our key exchange scheme [12,16,17,21].”
GGHLite: More Efficient Multilinear Maps from Ideal Lattices (2014, background): “, in [12]) to bound the smoothing parameter of ideal lattices.”
Efficient Public Key Encryption Based on Ideal Lattices (2009, methodology): “The approximation factors in [17] are given in terms of the infinity norm.”
On Ideal Lattices and Learning with Errors over Rings (2010, methodology): “Then, invoking prior worst-case hardness results for ring-SIS [20], they conclude that ring-LWE is hard under a worst-case quantum assumption.”
Homomorphic Signatures for Polynomial Functions (2011, methodology): “Ideal lattices also appear in the lattice-based public key encryption schemes of Stehle et al. [37] and Lyubashevsky, Peikert, and Regev [26] and in the hash functions of Lyubashevsky and Micciancio [25].”
Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices (2006, result): “Here we show how to find collisions in the compact knapsack function when S = [0, D]n for some D = pΘ(1), for which Micciancio proved that the function was one-way (under suitable assumptions).”
Trapdoors for hard lattices and new cryptographic constructions (2008, background): “, cyclic) lattices, as in prior works [38, 46, 35, 47, 36].”
Bonsai Trees, or How to Delegate a Lattice Basis (2010, background): “, [33,35,36,44,45,52]), with little to no essential changes to the proofs.”
A Toolkit for Ring-LWE Cryptography (2013, background): “The growth can be quantified by the “expansion factor” [23] of Φm(X), which unfortunately can be very large, up to n in the case of highly composite m [12].”
Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, background): “17 Recent works [1,26,70,72,86] use a small modulus and larger dimension, but our “native” modulus is already a large one.”
Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages (2011, methodology): “Starting with the work of Micciancio [28], there has been an ongoing effort [31, 23, 32, 25, 24] to come up with very efficient constructions of various cryptographic primitives whose security can formally be reduced to the hardness of short-vector problems in ideal lattices.”
Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems (2012, background): “This has changed since the introduction of cyclic and ideal lattices [27] and related computationally hard problems like Ring-SIS [32, 23, 25] and Ring-LWE [26] which enabled the constructions of a great variety of theoretically elegant and efficient cryptographic primitives.”
Lattice Signatures and Bimodal Gaussians (2013, methodology): “In 2006, a ring variant of SIS was introduced independently by Peikert and Rosen [30] and Lyubashevsky and Micciancio [25].”
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (2009, methodology): “The works of [29,18], showed a reduction from the worstcase problem of finding short vectors in algebraic lattices to finding collisions in hash functions.”