On the (In) security of Kilian-Based SNARGs

摘要

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 NP, based on collision resistant hash functions (CRHF) and probabilistically checkable proofs (PCPs). 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., SNARKs and STARKs). In this work, we show significant obstacles to establishing soundness of (what we refer to as) the "Fiat-Shamir-Kilian-Micali" (FSKM) protocol. More specifically: