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.