Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

By Chris Peikert, Alon Rosen. Theory of Cryptography Conference, 2006

331 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/c21b587b1f4245369c00ba6e3f6aa479a227e04b

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

Citations in the corpus

Efficient Public Key Encryption Based on Ideal Lattices (2009, background): “Subsequently, Lyubashevsky and Micciancio [17] and independently Peikert and Rosen [29] showed how to modify Micciancio’s function to construct an efficient and provably secure collision resistant hash function.”
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.”
Worst-case to average-case reductions for module lattices (2014, background): “The R-SIS problem was concurrently introduced in [36] and [18].”
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.”
On Ideal Lattices and Learning with Errors over Rings (2010, methodology): “Later, Peikert and Rosen [PR06] and Lyubashevsky and Micciancio [LM06] independently showed that a modiﬁed ring-SIS problem is as hard as worst-case problems on ideal lattices (a generalization of cyclic lattices), which led to constructions of collision-resistant hash functions with practical…”
Trapdoors for hard lattices and new cryptographic constructions (2008, background): “, cyclic) lattices, as in prior works [38, 46, 35, 47, 36].”
Lattice Signatures Without Trapdoors (2012, result): “These results are special cases of more general results about the discrete Normal distribution over arbitrary lattices from [6, 31, 37].”
Generalized Compact Knapsacks Are Collision Resistant (2006, neutral): “Concurrently with, and independently from our work, Peikert and Rosen [19] have shown (using very similar techniques) that the one-way function in [15] is not collision resistant and showed how to construct collision resistant hash functions based on the hardness of ﬁnding the shortest vector for…”
Multi-bit Cryptosystems Based on Lattice Problems (2006, background): “attractive property of the average-case /worst-case connection has been also studied from a theoretical point of view [2, 27, 25, 32].”
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]).”
Making NTRU as Secure as Worst-Case Problems over Ideal Lattices (2011, background): “Peikert, Rosen, Lyubashevsky and Micciancio [30, 19] later suggested to change the ring to Zq[x]/Φ with a Φ that is irreducible over the rationals, sparse, and with small coe cients (e.”
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (2009, methodology): “It’s not hard to see that for polynomials v,w ∈ Zp[x]/〈xn + 1〉, the following relation holds: ‖vw‖∞ ≤ ‖v‖∞‖w‖1 ≤ n‖v‖∞‖w‖∞ (x + 1)-cyclic lattices are a particular class of lattices that received attention because one can construct efficient and provably secure cryptographic primitives based on the ”
Lattice-Based Cryptography (2006, background): “Finally, in more recent work [26, 27], the hash function of [25] was modified, preserving the efficiency and achieving the stronger security property of collision resistance.”
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].”
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM (2017, methodology): “Based on the idea from the NTRU cryptosystem [43] of working with elements over polynomial rings rather than over the integers, and following a series of works on this topic [54, 56, 61, 68], Lyubashevsky et al.”
Classical hardness of learning with errors (2013, background): “In addition, this leads to the ﬁrst hardness proof for the Ring-SIS problem [LM06, PR06] with exponential modulus under the hardness of general lattice problems, via the standard LWE -to- SIS reduction.”