Correlation Intractability and SNARGs from Sub-exponential DDH

Arka Rai Choudhuri; Sanjam Garg; Abhishek Jain; Zhengzhong Jin; Jiaheng Zhang

Paper 2022/1486

Correlation Intractability and SNARGs from Sub-exponential DDH

Arka Rai Choudhuri

, NTT Research

Sanjam Garg, University of California, Berkeley, NTT Research

Abhishek Jain, Johns Hopkins University

Zhengzhong Jin, Massachusetts Institute of Technology

Jiaheng Zhang, University of California, Berkeley

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 $\mathsf{TC}^0$, based on sub-exponential DDH.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: SNARGs Delegation Schemes Correlation Intractable Hash Functions Fiat-Shamir
Contact author(s): arkarai choudhuri @ gmail com
sanjamg @ berkeley edu
abhishek @ cs jhu edu
zzjin @ mit edu
jiaheng_zhang @ berkeley edu
History: 2022-10-30: approved; 2022-10-28: received; See all versions
Short URL: https://ia.cr/2022/1486
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1486,
      author = {Arka Rai Choudhuri and Sanjam Garg and Abhishek Jain and Zhengzhong Jin and Jiaheng Zhang},
      title = {Correlation Intractability and {SNARGs} from Sub-exponential {DDH}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1486},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1486}
}