Kilian's Protocol and Beyond: On Constructions and Limitations of Succinct Arguments

Succinct non-interactive arguments (SNARGs) are a fundamental primitive in modern cryptography, enabling a prover to convince a verifier of an NP statement with a proof far shorter than the witness. The most common route to SNARGs is via succinct interactive arguments, and the paradigmatic such construction is Kilian's protocol, which combines a probabilistically checkable proof (PCP) with a vector commitment scheme. This thesis investigates Kilian's protocol along three complementary axes: how tightly we can analyze its security, how broadly we can generalize it, and whether the resulting SNARGs can be realized without idealized models.

Security analysis of Kilian's protocol. We establish the tightest known bounds on the security of Kilian's protocol in the standard model, via both strict-time and expected-time reductions; prior analyses cover only the strict-time setting and either incur large overheads or have non-trivial restrictions. How far can these bounds be pushed? Kilian's protocol shares striking structural similarities with sigma protocols, exemplified by Schnorr's protocol for discrete logarithm, whose standard-model security remains poorly understood despite extensive study. Perhaps surprisingly, we show that significantly improving our bounds would imply improving Schnorr's security analysis beyond the state-of-the-art, partly explaining the inherent difficulty of obtaining tight bounds.

Fiat--Shamir security in the random oracle model. Moving from analysis to construction, we propose the Funky protocol, a generalization of Kilian's protocol in the functional interactive oracle proof (FIOP) and functional commitment (FC) framework that unifies many known interactive arguments. A standard SNARG paradigm builds a public-coin succinct interactive argument and applies the Fiat--Shamir transformation in the random oracle model. We close a key security gap in this paradigm: the Funky protocol satisfies state-restoration security whenever the FIOP is state-restoration sound and the FC scheme satisfies a natural state-restoration variant of function binding, so that the Fiat--Shamir transformation yields a secure SNARG in the random oracle model.

SNARGs in the plain model. We show that the Micali SNARG, which applies the Fiat--Shamir transformation to the Kilian's protocol, can be securely instantiated in the standard model via a new interaction between two primitives: a PCP with a property we term shadow soundness, and a vector commitment with function statistical binding. Every language in NP admits a shadow PCP in NC; combining it with a function-statistically-binding vector commitment for NC yields a secure SNARG under sub-exponential LWE. This is the first concrete validation of the Micali blueprint in the standard model, and refutes "universal"attacks on the framework by exhibiting concrete sound instantiations.