Abstract
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