International Association
for Cryptologic Research

The Fiat-Shamir transform is an incredibly powerful technique that uses a suitable hash function to reduce the interaction of general public-coin protocols. Unfortunately, there are known counterexamples showing that this methodology may not be sound (no matter what concrete hash function is used). Still, these counterexamples are somewhat unsatisfying, as the underlying protocols were specifically tailored to make Fiat-Shamir fail. This raises the question of whether this transform is sound when applied to natural protocols.One of the most important protocols for which we would like to reduce interaction is Kilian’s four-message argument system for all of $$\mathsf {NP}$$ , based on collision resistant hash functions ( $$\mathsf {CRHF}$$ ) and probabilistically checkable proofs ( $$\mathsf {PCP}$$ s). Indeed, an application of the Fiat-Shamir transform to Kilian’s protocol is at the heart of both theoretical results (e.g., Micali’s CS proofs) as well as leading practical approaches of highly efficient non-interactive proof-systems (e.g., $$\mathsf {SNARK}$$ s and $$\mathsf {STARK}$$ s).In this work, we show significant obstacles to establishing soundness of (what we refer to as) the “Fiat-Shamir-Kilian-Micali” ( $$\mathsf {FSKM}$$ ) protocol. More specifically:We construct a (contrived) $$\mathsf {CRHF}$$ for which $$\mathsf {FSKM}$$ is unsound for a very large class of $$\mathsf {PCP}$$ s and for any Fiat-Shamir hash function. The collision-resistance of our $$\mathsf {CRHF}$$ relies on very strong but plausible cryptographic assumptions. The statement is “tight” in the following sense: any $$\mathsf {PCP}$$ outside the scope of our result trivially implies a $$\mathsf {SNARK}$$ , eliminating the need for $$\mathsf {FSKM}$$ in the first place.Second, we consider a known extension of Kilian’s protocol to an interactive variant of $$\mathsf {PCP}$$ s called probabilistically checkable interactive proofs ( $$\mathsf {PCIP})$$ (also known as interactive oracle proofs or $$\mathsf {IOP}$$ s). We construct a particular (contrived) $$\mathsf {PCIP}$$ for $$\mathsf {NP}$$ for which the $$\mathsf {FSKM}$$ protocol is unsound no matter what $$\mathsf {CRHF}$$ and Fiat-Shamir hash function is used. This result is unconditional (i.e., does not rely on any cryptographic assumptions). Put together, our results show that the soundness of $$\mathsf {FSKM}$$ must rely on some special structure of both the $$\mathsf {CRHF}$$ and $$\mathsf {PCP}$$ that underlie Kilian’s protocol. We believe these negative results may cast light on how to securely instantiate the $$\mathsf {FSKM}$$ protocol by a synergistic choice of the $$\mathsf {PCP}$$ , $$\mathsf {CRHF}$$ , and Fiat-Shamir hash function.