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