Correlation Intractability and SNARGs from Sub-exponential DDH
Arka Rai Choudhuri, Sanjam Garg, Abhishek Jain, Zhengzhong Jin, Jiaheng Zhang
2023Year
49Citations
4Top-tier citations
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.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 3021a5ff-a43d-4f1a-871f-1cd1188537f9Cited by top-tier papers4
- Adaptively-Sound Succinct Arguments for NP from Indistinguishability ObfuscationBrent Waters, David J. WuSTOC 2024 · 18 citations
- A New Approach for Non-Interactive Zero-Knowledge from Learning with ErrorsBrent WatersSTOC 2024 · 13 citations
- Non-interactive Zero-Knowledge from Non-interactive Batch ArgumentsJeffrey Champion, David J. WuCRYPTO 2023 · 9 citations
- Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)Lijie Chen, Ron D. Rothblum, Roei TellSTOC 2025 · 2 citations
Builds on14
- Bulletproofs: Short Proofs for Confidential Transactions and MoreBenedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra et al.S&P 2018 · 1,285 citations
- SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWERuta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Yun ZhangSTOC 2021 · 61 citations
- Non-interactive Batch Arguments for NP from Standard AssumptionsArka Rai Choudhuri, Abhishek Jain, Zhengzhong JinCRYPTO 2021 · 57 citations
- NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable RelationsZvika Brakerski, Venkata Koppula, Tamer MourCRYPTO 2020 · 52 citations
- Rate-1 Non-Interactive Arguments for Batch-NP and ApplicationsLalita Devadas, Rishab Goyal, Yael Kalai, Vinod VaikuntanathanFOCS 2022 · 49 citations
Related papers
- SNARGs and PPAD Hardness from the Decisional Diffie-Hellman AssumptionYael Tauman Kalai, Alex Lombardi, Vinod VaikuntanathanEUROCRYPT 2023 · 15 citations
- SNARGs for from LWEArka Rai Choudhuri, Abhishek Jain, Zhengzhong JinFOCS 2021 · 62 citations
- Non-interactive Zero Knowledge from Sub-exponential DDHAbhishek Jain, Zhengzhong JinEUROCRYPT 2021 · 49 citations
- SNARGs for P from Sub-exponential DDH and QRJames Hulett, Ruta Jawale, Dakshita Khurana, Akshayaram SrinivasanEUROCRYPT 2022 · 41 citations
- SNARGs under LWE via Propositional ProofsZhengzhong Jin, Yael Kalai, Alex Lombardi, Vinod VaikuntanathanSTOC 2024 · 6 citations
