Paper 2021/788

Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs

Yael Tauman Kalai, Vinod Vaikuntanathan, and Rachel Yun Zhang


The main conceptual contribution of this paper is a unification of two leading paradigms for constructing succinct argument systems, namely Kilian's protocol and the BMW (Biehl-Meyer-Wetzel) heuristic. We define the notion of a multi-extractable somewhere statistically binding (meSSB) hash family, an extension of the notion of somewhere statistically binding hash functions (Hubacek and Wichs, ITCS 2015), and construct it from LWE. We show that when instantiating Kilian's protocol with a meSSB hash family, the first two messages are simply an instantiation of the BMW heuristic. Therefore, if we also instantiate it with a PCP for which the BMW heuristic is sound, e.g., a computational non-signaling PCP, then the first two messages of the Kilian protocol is a sound instantiation of the BMW heuristic. This leads us to two technical results. First, we show how to efficiently convert any succinct non-interactive argument (SNARG) for BatchNP into a SNARG for any language that has a computational non-signaling PCP. Put together with the recent and independent result of Choudhuri, Jain and Jin (Eprint 2021/808) which constructs a SNARG for BatchNP from LWE, we get a SNARG for any language that has a computational non-signaling PCP, including any language in P, but also any language in NTISP (non-deterministic bounded space), from LWE. Second, we introduce the notion of a somewhere statistically sound (SSS) interactive argument, which is a hybrid between a statistically sound proof and a computationally sound proof (a.k.a. an argument), and * prove that Kilian's protocol, instantiated as above, is an SSS argument; * show that the soundness of SSS arguments can be proved in a straight-line manner, implying that they are also post-quantum sound if the underlying assumption is post-quantum secure; and * conjecture that constant-round SSS arguments can be soundly converted into non-interactive arguments via the Fiat-Shamir transformation.

Available format(s)
Publication info
Contact author(s)
yael @ microsoft com
vinodv @ csail mit edu
rachelyz @ mit edu
2021-08-19: last of 6 revisions
2021-06-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yael Tauman Kalai and Vinod Vaikuntanathan and Rachel Yun Zhang},
      title = {Somewhere Statistical Soundness, Post-Quantum Security, and {SNARGs}},
      howpublished = {Cryptology ePrint Archive, Paper 2021/788},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.