Collision-Free Hashing from Lattice Problems

By Oded Goldreich, Shafi Goldwasser, Shai Halevi. 1996

How researchers see this paper

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

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “We optimistically estimate that each hash computation requires only 300 multiplication gates, using a subset-sum hash function [2, 17, 67, 77], and we ignore the cost of computing the Valid circuit in the SNARK.”
Verifying computations with state (2013, methodology): “While that might be disconcerting, Pantry’s goal is to establish that a remote execution is consistent with an expressed computation; program verification is a complementary concern (§1).”
Classical hardness of learning with errors (2013, background): “The SIS problem has been the foundation for oneway [3] and collision-resistant hash functions [19], identification schemes [35, 27, 22], and digital signatures [18, 15, 11, 33, 28].”
On Ideal Lattices and Learning with Errors over Rings (2010, unknown): “As a search problem (without unique solution), SIS has been the foundation for one-way [2] and collision-resistant hash functions [15], identification schemes [25, 18, 17], and digital signatures [13, 8].”
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions (2002, background): “Finally, and this is probably the most surprising of the differences, we are unable to prove that the compact knapsack function is collision resistant, as done in [14, 24] for general lattices.”
Worst-case to average-case reductions based on Gaussian measures (2004, methodology): “The reduction: In this paper, as in previous work [2, 10, 7, 14, 15, 17], we consider the problem of reducing worstcase instances of approximating lattice problems (e.”
Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, methodology): “We base collision-resistant hashing on subset-sum functions [2,50], chosen to have an especially compact representation as arithmetic circuits over the zk-SNARK’s “native field”.”
Lossy trapdoor functions and their applications (2008, background): “Both primitives are implied by the worst-case hardness of standard lattice problems (see, e.g., [1, 25]).”
New lattice based cryptographic constructions (2003, background): “In [7], it was shown that under the same assumptions one can obtain collision resistant hash functions.”
Trapdoors for hard lattices and new cryptographic constructions (2008, background): “” Until very recently, the known constructions of such primitives were limited mainly to one-way and collision-resistant hash functions [3, 27, 17, 37, 40] and public-key encryption [5, 51, 52].”
Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices (2006, background): “In his groundbreaking result, Ajtai first constructed a one-way function [1], which was later observed to also be collisionresistant [11].”
SWIFFT: A Modest Proposal for FFT Hashing (2008, background): “Ajtai’s work and subsequent improvements [11,6,17,19] do not lead to very efficient implementations, mostly because of the huge size of the function description and slow evaluation time”
Generating Shorter Bases for Hard Random Lattices (2009, background): “This family of ‘hard random lattices’ has since been used as the foundation for several important cryptographic primitives, including one-way and collision-resistant hash functions, public-key encryption, digital signatures, and identity-based encryption (see, for example, [4, 7, 11, 20]).”
Lattice-Based Cryptography (2006, background): “[21] improved on Ajtai’s result by constructing a stronger cryptographic primitive known as a family of collision resistant hash functions.”
Foundations of Cryptography: Volume 1, Basic Tools (2001, unknown): “[101]): If certain computational problems regarding integer lattices are hard in the worst case, then one-way functions exist.”