Paper 2023/1500

Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with Errors

Susumu Kiyoshima, NTT Social Informatics Laboratories

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].

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2023
Contact author(s)
susumu kiyoshima @ ntt com
2023-10-03: approved
2023-10-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Susumu Kiyoshima},
      title = {Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1500},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.