Correlation Intractability and 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