International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Correlation Intractability and SNARGs from Sub-exponential DDH

Authors:
Arka Rai Choudhuri , NTT Research
Sanjam Garg , NTT Research & UC Berkeley
Abhishek Jain , Johns Hopkins University
Zhengzhong Jin , MIT
Jiaheng Zhang , UC Berkley
Download:
DOI: 10.1007/978-3-031-38551-3_20 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
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. We obtain our results by following the correlation-intractability framework for secure instantiation of the Fiat-Shamir paradigm. The centerpiece of our results and of independent interest is a new construction of correlation-intractable hash functions for ``small input'' product relations verifiable in TC0, based on sub-exponential DDH.
BibTeX
@inproceedings{crypto-2023-33243,
  title={Correlation Intractability and SNARGs from Sub-exponential DDH},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38551-3_20},
  author={Arka Rai Choudhuri and Sanjam Garg and Abhishek Jain and Zhengzhong Jin and Jiaheng Zhang},
  year=2023
}