Paper 2026/1679

Critical-Round Special Soundness for Multi-Round Proofs

Abstract

Multi-round public-coin proof systems have progressed rapidly, yet their simulators and extractors are rarely used as building blocks in other protocols, unlike those of 3-move $\Sigma$-protocols. Prior work [Abe et al., Eurocrypt~'26] addressed the simulator side with critical-round zero-knowledge. In this paper, we address the extractor side and introduce critical-round special soundness (CRSS): a witness is extractable from a small critical subtree of transcripts that branches only from one round, while the full tree of transcripts serves only as a fall-back that outputs a solution to a hardness assumption. We first establish an extract-or-extend theorem that bounds the failure probability of the critical extractor even when the critical-round challenges are chosen by the adversary, and then show that KKW-style MPC-in-the-head proofs, KZG-compiled polynomial IOPs including Plonk, and Protogalaxy satisfy CRSS. We also give a corresponding tree-extraction result for the sumcheck sub-protocol of Spartan. We present three applications: a hash-based witness sharing scheme that verifiably secret-shares an NP witness without interaction among recipients, the first offline trapdoor-extractable trapdoor commitment from a multi-round proof, where a trapdoor is extracted immediately upon a double opening, and a parameter improvement for the multi-round Fischlin transform [Rotem-Tessaro, Crypto~'25] that reduces the prover's complexity in practice.