Paper 2022/1486 Original: eprint.iacr.org/2022/1486 ↗
Correlation Intractability and SNARGs from Sub-exponential DDH
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.
- History
- 2022-10-28: last updated
- 2022-10-28: published
- Short URL
- https://ia.cr/2022/1486
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}