Correlation Intractability and SNARGs from Sub-exponential DDH
summary
Construction of SNARGs for Batch-NP and P from the sub-exponential Decisional Diffie–Hellman assumption, achieving poly-logarithmic proof sizes and a CIH for TC^0 verifiable product relations; core claim is a reduction from sub-exponential DDH to correlation intractable hashes for “small-input” product relations, via an interactive-to-noninteractive hashing protocol that composes linear operations across rounds and then round-collapses using complexity leveraging. Hash evaluation runs in roughly n^{O(log log n)}, the scheme supports Fiat–Shamir on parallel repetition, and yields SNARGs with succinct proofs under the stated hardness.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:21SNARG: Succinct Non-Interactive ARGument
- 3:33Understand the Power of Diffie-Hellman
- 6:56Correlation Intractable Hash (CIH)
- 8:17Recall: Fiat-Shamir via CIH
- 23:12Background: CIH for Searchable Relations
- 27:12CIH for Searchable Relations (Cont.)
- 31:14Our Goal: CIH for Verifiable Product Relations
- 33:34Handling Multiple Bad Challenges
- 39:56Our CIH Construction
related talks
01h 15mProofs - Theory
01h 07mBatch Arguments for NP and SNARGs for P from LWE
01h 08mTowards SNARGs for NP from Standard Assumptions
53mA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP
29mCorrelation-Intractable Hash Functions via Shift-Hiding
58mSNARGs for P/poly from SIS
01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristic
49mSubquadratic SNARGs in the Random Oracle Model