Unlocking Cryptography: Correlation Intractability & SNARGs from Sub-Exponential DDH 🔐

Zhengzhong Jin (MIT)
Correlation Intractability and SNARGs from Sub-exponential DDH
Minimal Complexity Assumptions for Cryptography

We provide the first constructions of SNARGs for Batch-NP and P based solely on the sub-exponential Decisional Diffie Hellman (DDH) assumption. Our schemes achieve poly-logarithmic proof sizes.

Central to our results and of independent interest is a new construction of correlation-intractable hash functions for “small input” product relations verifiable in TC^0, based on sub-exponential DDH.

Joint work with Arka Rai Choudhuri, Sanjam Garg, Abhishek Jain, and Jiaheng Zhang