Welcome to the resource topic for 2021/808
Title:
SNARGs for \mathcal{P} from LWE
Authors: Arka Rai Choudhuri, Abhishek Jain, Zhengzhong Jin
Abstract:We provide the first construction of a succinct non-interactive argument (SNARG) for all polynomial time deterministic computations based on standard assumptions. For T steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in T. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC’21]. Along the way, we also provide the first construction of non-interactive batch arguments for \mathsf{NP} based solely on the LWE assumption.
ePrint: https://eprint.iacr.org/2021/808
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .