Welcome to the resource topic for 2023/1500
Title:
Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with Errors
Authors: Susumu Kiyoshima
Abstract:A succinct non-interactive argument (SNARG) is called holographic if the verifier runs in time sub-linear in the input length when given oracle access to an encoding of the input. We present holographic SNARGs for P and Batch-NP under the learning with errors (LWE) assumption. Our holographic SNARG for P has a verifier that runs in time \mathsf{poly}(\lambda, \log T, \log n) for T-time computations and n-bit inputs (\lambda is the security parameter), while our holographic SNARG for Batch-NP has a verifier that runs in time \mathsf{poly}(\lambda, T, \log k) for k instances of T-time computations. Before this work, constructions with the same asymptotic efficiency were known in the designated-verifier setting or under the sub-exponential hardness of the LWE assumption. We obtain our holographic SNARGs (in the public-verification setting under the polynomial hardness of the LWE assumption) by constructing holographic SNARGs for certain hash computations and then applying known/trivial transformations.
As an application, we use our holographic SNARGs to weaken the assumption needed for a recent public-coin 3-round zero-knowledge (ZK) argument [Kiyoshima, CRYPTO 2022]. Specifically, we use our holographic SNARGs to show that a public-coin 3-round ZK argument exists under the same assumptions as the state-of-the-art private-coin 3-round ZK argument [Bitansky et al., STOC 2018].
ePrint: https://eprint.iacr.org/2023/1500
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 .