## Background
### NIZK in the Random Oracle Model  
We can remove the interaction between \(\mathcal{P}\) and \(\mathcal{V}\) by replacing the challenge \(\text{chal}\) with a hash value \(H(\text{stmt},\text{com})\) computed by the prover, where \(H\) is a hash function modeled as a random oracle. By applying the Fiat-Shamir paradigm [13], we can transform an interactive protocol \((\mathcal{P},\mathcal{V})\) into a non-interactive proof system \((\mathcal{P}^{H},\mathcal{V}^{H})\). Syntax  
Let \(\mathcal{L}:=\{\text{stmt}:\exists\text{wt}\text{ such that }R(\text{stmt},\text{wt})=1\}\) is an NP-language defined by a binary relation \(R\), and \(H\) is a hash function (modeled as a random oracle). A non-interactive proof system \((\mathcal{P}^{H},\mathcal{V}^{H})\) for \(\mathcal{L}\) consists of two algorithms. The proving algorithm \(\pi\stackrel{{\mathcal{S}}}{{\leftarrow}}\mathcal{P}^{H}(\text{ stmt},\text{wt})\) takes as input a statement \(\text{stmt}\) and a witness \(\text{wt}\) such that \(R(\text{stmt},\text{wt})=1\) and outputs a proof \(\pi\). The verification algorithm \(\mathcal{V}^{H}(\text{stmt},\)\(\pi)\in\{0,1\}\) takes as input a statement \(\text{stmt}\) and a proof \(\pi\) and outputs \(1\) (true) or \(0\) (false). We refer here to the zero-knowledge simulator \(\mathcal{S}\) of a non-interactive zero-knowledge proof system [14] defined in the explicitly programmable random oracle model [20]. As a stateful algorithm, the simulator \(\mathcal{S}\) can operate in two modes: \((h_{i},st)\leftarrow\mathcal{S}(1,st,q_{i})\) deals with answering random oracle queries such that \(h_{i}=H(q_{i})\), while \((\pi,st)\leftarrow\mathcal{S}(2,st,\text{stmt})\) simulates the proof. Note that calls to \(\mathcal{S}(1,\cdots)\) and \(\mathcal{S}(2,\cdots)\) share the common state \(st\), which is updated after each operation. **Definition 1** (Unbounded Non-Interactive Zero-Knowledge [14]). : _Let \(\mathcal{L}\) be an NP-language. Let \((\mathcal{S}_{1},\mathcal{S}_{2})\) denote the oracles such that \(\mathcal{S}_{1}(q_{i})\) returns the first output of \((h_{i},st)\leftarrow\mathcal{S}(1,st,q_{i})\) and \(\mathcal{S}_{2}(\text{stmt},\text{wt})\) returns the first output of \((\pi,st)\leftarrow\mathcal{S}(2,st,\text{stmt})\) if \((\text{stmt},\text{wt})\in\mathcal{R}_{\mathcal{L}}\). We say a protocol \((\mathcal{P}^{H},\mathcal{V}^{H})\) is an NIZK proof for language \(\mathcal{L}\) in the random oracle model if there exists a PPT simulator \(\mathcal{S}\) such that for all PPT distinguishers \(\mathcal{D}\), the advantage \(\epsilon_{\mathcal{ZK}}\) such that_  
\[\epsilon_{\mathcal{ZK}}(\lambda)=\big{|}\Pr[1\leftarrow\mathcal{D}^{H(\cdot), \mathcal{P}^{H}(\cdot)}(\lambda)]-\Pr[1\leftarrow\mathcal{D}^{\mathcal{S}_{1}( \cdot),\mathcal{S}_{2}(\cdot)}(\lambda)]\big{|}\]is negligible, where both \(\mathcal{P}\) and \(\mathcal{S}_{2}\) oracles output \(\bot\) if \((\mathsf{stmt},\mathsf{wit})\
eq\mathcal{R}_{\mathcal{L}}\)._  
**Definition 2** (Unbounded Simulation Soundness [14]). : _Let \(\mathcal{L}\) be an NP-language. Consider a proof system \((\mathcal{P}^{H},\mathcal{V}^{H})\) for \(\mathcal{L}\) with zero-knowledge simulator \(\mathcal{S}\). Let \((\mathcal{S}_{1},\mathcal{S}_{2}^{\prime})\) denote the oracle such that \(\mathcal{S}_{1}(q_{i})\) returns the first output of \((h_{i},st)\leftarrow\mathcal{S}(1,st,q_{i})\) and \(\mathcal{S}_{2}^{\prime}\) returns the first output of \((\pi,st)\leftarrow\mathcal{S}(2,st,\mathsf{stmt})\).