Paper 2026/1167

Provably-Secure NIZKs From Multi-Round Oracle Proofs

Abstract

We study the security of the Fiat-Shamir transformation when applied to multi-round oracle proofs in the standard model, showing that Interactive Oracle Proofs (IOPs) can be transformed via Fiat-Shamir into Non-interactive Zero-knowledge (NIZK) arguments. We obtain our result in two steps. First, we show that instantiating Kilian's transformation with an IOP satisfying a mild Zero-Knowledge (ZK) property called semi-Honest-Verifier ZK (semi-HVZK), and a commitment scheme that is extractable and equivocal, yields a ZK argument. We then obtain provably-secure NIZK arguments from our interactive ZK arguments by instantiating Fiat-Shamir with a Correlation-Intractable Hash (CIH) function. The second step involves carefully defining an appropriate "bad relation" for which CIHs are known to exist. Existence of CIH for our bad relation requires the underlying semi-HVZK IOP to have an additional "doom checkability" property which we introduce. Roughly, doom checkability guarantees that one can efficiently check whether a non-empty partial IOP transcript is "doomed" in the sense that it will lead the verifier to reject. We then show that IOPs based on the "MPC in the Head" paradigm are doom checkable. Our results show that the Fiat-Shamir paradigm can be applied to semi-HVZK IOPs to yield provably-secure NIZKs. This extends similar results known for single-round IOPs (i.e., Probabilistically Checkable Proofs) and interactive proofs (IPs), and establishes the soundness of this method. Along the way, we also prove composition theorems for semi-HVZK IOPs, which might be of independent interest, and use them to improve the soundness error of linear-time IOPs and interactive arguments from the literature.