Correlation-Intractable Hash Functions via Shift-Hiding

on YouTube ↗29m

" summary

Gives a simple self-reduction showing that a shift-hiding PRF that is one-way on the zero output yields correlation-intractable hash families for many relations, turning the general f case into the trivial zero case. Constructs concrete instantiations from shift-hiding shiftable functions built from LWE to get multi-input CI for shifted linear relations, and from indistinguishability obfuscation plus standard assumptions to handle broader shifted output relations; proofs reduce inversion to CIS/LWE assumptions.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 2:15Applications of CI
3. 5:49Correlation Intractability
4. 8:33Multi-Input Case?
5. 9:56This Work
6. 11:25Results: Shifted Linear Relations
7. 13:01Results: General Shifted Relations
8. 15:11Shift-Hiding Shiftable Functions [PS18]
9. 17:29Key Lemma
10. 22:21One-Wayness of the SHSF
11. 27:19Conclusion

" related talks

• 44mCorrelation Intractability and SNARGs from Sub-exponential DDHZhengzhong Jin · Minimal Complexity Assumptions for Cryptography 2023
• 46mQuantum pseudorandomness in Algorithmica, and its implications to cryptography and complexityLuowen Qian · Minimal Complexity Assumptions for Cryptography 2023
• 52mHash-based Folding SchemesWilliam Wang · Proofs (Simons Institute)
• 37mCircularity Based IO, Part 2Boaz Barak · Simons Institute Workshop: New Developments in Obfuscation
• 49mCollision-Resistance from Multi-Collision-ResistanceRon D. Rothblum · Minimal Complexity Assumptions for Cryptography 2023
• 33mA New Approach for Non-Interactive Zero-Knowledge from Learning with ErrorsBrent Waters · Proofs (Simons Institute)
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020