Collision-Free Hashing from Lattice Problems

DOI10.1007/978-3-642-22670-0_5zbMath1343.94055OpenAlexW1576470039MaRDI QIDQ3088173

Oded Goldreich, Shai Halevi, Shafi Goldwasser

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1721.1/121244

zbMATH Keywords

integer latticesone-way functionsworst-case to average-case reductionscollision-resistent hashing

Mathematics Subject Classification ID

Cryptography (94A60) Lattices and convex bodies (number-theoretic aspects) (11H06)

Related Items (25)

\textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments ⋮ Efficient proof composition for verifiable computation ⋮ Quantum algorithms for variants of average-case lattice problems via filtering ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ The Phase Transition of Discrepancy in Random Hypergraphs ⋮ Succinct vector, polynomial, and functional commitments from lattices ⋮ Efficient laconic cryptography from learning with errors ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption ⋮ The gap is sensitive to size of preimages: collapsing property doesn't go beyond quantum collision-resistance for preimages bounded hash functions ⋮ Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors ⋮ The hunting of the SNARK ⋮ Lattice-based timed cryptography ⋮ Lattice-based completely non-malleable public-key encryption in the standard model ⋮ New Constructions for Secure Hash Functions ⋮ Generating shorter bases for hard random lattices ⋮ Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack ⋮ Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ An LWE-based verifiable threshold secret sharing scheme ⋮ A relation of primal--dual lattices and the complexity of shortest lattice vector problem ⋮ How to Prove Knowledge of Small Secrets ⋮ Sharing privacy protected and statistically sound clinical research data using outsourced data storage ⋮ Unnamed Item ⋮ A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor

Cites Work

• Unnamed Item
• Factoring polynomials with rational coefficients
• Universal classes of hash functions
• A Pseudorandom Generator from any One-way Function
• On the Existence of Pseudorandom Generators
• A more efficient algorithm for lattice basis reduction

This page was built for publication: Collision-Free Hashing from Lattice Problems