Collision-Resistance from Multi-Collision-Resistance
summary
Shows a non-blackbox transformation that turns a moderately shrinking 3‑MCRH (and separately 4‑MCRH) into a collision‑resistant hash family by using the attacker as an oracle, but the resulting CRH is infinitely-often secure and non‑constructive. Key parameters: 3→2 requires roughly >n/2 bits shrinkage, 4→2 works with ≈n/6 shrinkage; general t→t′ tradeoffs use Reed‑Solomon list‑decodability to bound packed polynomials. Builds candidate constructions, handles partial‑domain failures by random shifts, and proves the existence of a working CRH though it cannot be explicitly extracted.
AI-written summary · about
chapters (17)
- 0:00Intro
- 2:38Multi-Collision-Resistant Hashing
- 3:59Shrinkage for MCRH?
- 5:08Multi-Collision Resistant Hashing
- 5:30Prior Work
- 7:27CRH vs MCRH
- 8:28Main Result
- 14:41Crypto 101
- 18:02Reprecussions
- 22:19Use A to find larger collision for hЄH
- 26:30A 4-way collision?
- 28:05The family G
- 28:53A 3-way collision!
- 30:05Shrinkage?
- 31:40A new CRH
- 37:31Dealing with Imperfections
- 43:54Open Questions
related talks
29mCorrelation-Intractable Hash Functions via Shift-Hiding
49mSubquadratic SNARGs in the Random Oracle Model
51mMultilinear Maps and Attacks II
01h 06mObfuscation: Past, Present, and Possible Futures
01h 17mCrypto + Meta-complexity 2
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
32mPeeking into the Future: MPC Resilient to Super-Rushing Adversaries
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics