Paper 2026/2708

Beyond Standard Indifferentiability: Simulator Properties for Fiat-Shamir Security

Abstract

The Fiat-Shamir transform converts public-coin interactive arguments into non-interactive arguments (NARGs). Its security is typically analyzed in the random-oracle model, while implementations instantiate the random oracle with structured hash constructions. Standard indifferentiability is the natural abstraction for justifying this replacement. Chiesa and Orru (TCC ’25), however, showed that standard indifferentiability does not generally preserve the information and reset behavior needed by common Fiat-Shamir extraction arguments, and proposed stronger notions of indifferentiability to bridge this gap. We show that standard indifferentiability can nevertheless be retained as the oracle-replacement abstraction. For knowledge soundness, we give generic transfer theorems for three extraction interfaces: proof-only straight-line extraction follows from standard indifferentiability alone; transcript-dependent extraction additionally requires transcript reconstruction; and rewinding extraction requires reconstruction for rewinding, preserving simulator behavior across invocations with the same hidden randomness. Our results apply to worst-case polynomial-time extractors. Moreover, we show that the rewinding requirement is inherent: assuming discrete-logarithm hardness, we construct a perfectly indifferentiable construction and fixed prover admitting error-free rewinding extraction in the ideal world, while every polynomial-time construction-world extractor succeeds only with negligible probability. We instantiate our framework for tagged prefix-free Merkle-Damgard and a fixed-output permutation sponge. The former admits exact transcript and rewinding reconstruction, while the latter admits exact transcript reconstruction and rewinding reconstruction with negligible statistical error incurred only once, independently of the number of restarts. For zero knowledge, we give a semantic formulation where one persistent simulator jointly generates the proof and public-oracle interaction. Here, standard indifferentiability alone yields a generic transfer theorem, requiring neither reconstruction property and incurring only the indifferentiability error. Thus standard indifferentiability provides a common oracle-replacement abstraction for knowledge soundness and semantic zero knowledge, with extraction-specific requirements isolated as separate simulator properties.