Cryptology ePrint Archive: Report 2021/788

Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs

Yael Tauman Kalai and Vinod Vaikuntanathan and Rachel Yun Zhang

Abstract: We instantiate Kilian's protocol with a computationally non-signaling PCP (Brakerski, Holmgren, and Kalai, STOC 2017) and a somewhere statistically binding hash family (Hubacek and Wichs, ITCS 2015). Observing that the first two messages of Kilian's protocol, instantiated with these primitives, is a sound instantiation of the BMW heuristic (Kalai, Raz, and Rothblum, STOC 2013), we show how to efficiently convert any succinct non-interactive argument (SNARG) for BatchNP into a SNARG for any language that has a non-signaling PCP, including any deterministic language and any language in NTISP, using a somewhere statistically binding hash family.

We also 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).

- We show that Kilian's protocol, instantiated in the above way, is an SSS argument.

- Secondly, we 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. This provides a straightforward proof that Kilian's protocol, instantiated as above, is post-quantum sound under the post-quantum hardness of LWE (though we emphasize that a computationally non-signaling PCP is known to exist only for deterministic languages and for specific subclasses of non-deterministic languages such as NTISP, but not for all of NP).

- We put forward a natural conjecture that constant-round SSS arguments can be soundly converted into non-interactive arguments via the Fiat-Shamir transformation. We argue that SSS arguments evade the current Fiat-Shamir counterexamples, including the one for Kilian's protocol (Bartusek, Bronfman, Holmgren, Ma and Rothblum, TCC 2019) by requiring additional properties from both the hash family and the PCP.

Category / Keywords: foundations / SNARG, post-quantum, Fiat-Shamir, Kilian, non-signaling

Date: received 10 Jun 2021, last revised 20 Jul 2021

Contact author: yael at microsoft com, vinodv at csail mit edu, rachelyz at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20210720:172441 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]