International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

SNARGs for P from Sub-exponential DDH and QR

Authors:
James Hulett , University of Illinois Urbana-Champaign
Ruta Jawale , University of Illinois Urbana-Champaign
Dakshita Khurana , University of Illinois Urbana-Champaign
Akshayaram Srinivasan , Tata Institute of Fundamental Research
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: We obtain publicly verifiable Succinct Non-Interactive Arguments (SNARGs) for arbitrary deterministic computations and bounded space non-deterministic computation from well-studied group-based assumptions. In particular, assuming the sub-exponential hardness of the Decisional Diffie-Hellman (DDH) and Quadratic Residuosity (QR) assumptions, we obtain the following results, where n denotes the length of the instance: 1. A SNARG for any language that can be decided in non-deterministic time T and space S with communication complexity and verifier runtime(n+S)·T^{o(1)}. 2. A SNARG for any language that can be decided in deterministic time T with communication complexity n·T^{o(1)} and verifier runtime n·T^{o(1)}.
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31928,
  title={SNARGs for P from Sub-exponential DDH and QR},
  publisher={Springer-Verlag},
  author={James Hulett and Ruta Jawale and Dakshita Khurana and Akshayaram Srinivasan},
  year=2022
}