Black-Box (and Fast) Non-malleable Zero Knowledge

Non-malleable zero-knowledge argument systems [8] (NMZK) can be built by relying solely on one-way functions (OWFs) with only four rounds of communication [6], precisely as it is known for zero-knowledge (ZK) arguments [2].

However, when considering also the black-box use of the underlying cryptographic primitives the situation is very different. Indeed, while ZK arguments can be achieved in 5 (resp., 4) rounds relying on the black-box use of one-way functions (resp. 1-1 one-way functions) [14, 18], the gap in case of non-malleability is substantial since no construction is known, regardless of the round complexity and of the used primitive. It is particularly that, instead, non-malleable commitments based on the black-box use of one-way functions exist even in constant rounds [11] (and only in 4 rounds with black-box use of 1-1 one-way functions [5]). Still, according to [19], black-box constructions^{Footnote 1} of NMZK arguments from non-malleable commitments are (surprisingly) not known.

The Prior Attempt of [16]. In [16], Jain and Pandey focus on the difficult problem of constructing black-box NMZK arguments, even when relying on constant-round black-box non-malleable commitment schemes. They succeed in showing a black-box construction for argument systems that is secure w.r.t. a partial notion of non-malleability, commonly referred to as simulation soundness. Furthermore, in the introduction of their work, they discuss the hardness of obtaining black-box NMZK and informally suggest a generic construction that uses black-box non-malleable commitments. However, they note that all proof approaches they explored were unsuccessful, leading them to abandon the protocol, therefore leaving open the question of the existence of a black-box NMZK argument system (even under the assumption of black-box non-malleable commitments).

Open Problem. The state of the art leaves the following questions open.

Can we construct NMZK argument systems by only relying on the black-box use of cryptographic primitives? Can we construct them in constant rounds? Can we rely on one-way functions only?

Motivated by the theoretical interest and practical relevance of designing non-malleable schemes, we investigate the efficiency of NMZK arguments with restrictions on the available cryptographic primitives. Specifically, we focus on the recent non-black-box NMZK argument system of [20] based on one-way functions, which introduces new techniques to achieve efficiency while living in Minicrypt. The work of [20] relies on (and actually is affected by) the need of multiple executions of Ligero [1] to prove statements about computations performed during their protocol. The overhead due to multiple runs of Ligero highly dominates the overall amount of computations of their protocol and strongly affects its round complexity. This motivates the following additional open question:

If we are living in Minicrypt, can we still construct an efficient NMZK argument system therefore reducing or even avoiding the use of expensive generic ZK arguments (like Ligero)?

1.1 Our Contribution

In this work we provide a positive answer to all the above questions. We show the first NMZK argument system that only requires black-box use of cryptographic primitives. Moreover, our construction only needs one-way functions and can be instantiated in a (small) constant number of rounds. Our protocol outperforms previous work in terms of both efficiency and assumptions. In addition, it exhibits better concrete efficiency in Minicrypt when considering results described in [20]. In fact, we establish the following result.

Theorem

(informal). Assuming OWFs, there exists a 10-round (resp. 9-round) NMZK argument system that makes black-box use of OWFs (resp., 1-1 OWFs) only. Moreover, the protocol admits an efficient instantiation in Minicrypt.

We prove the above theorem by presenting a protocol \(\varPi _\textsf{NM}\) which can be viewed as a compiler from 3-round public-coin special honest-verifier zero-knowledge (SHVZK) \(\varPi _{\textsf{SHVZK}}\) to NMZK. Interestingly, \(\varPi _\textsf{NM}\) can be seen as a concrete, specific and optimized instantiation of the generic approach proposed and discarded in [16]. We manage to bypass the obstacles that stopped [16] with a highly non-trivial proof approach. Moreover, an additional major contribution of our work is in particular due to way we manage to obtain an efficient construction. Indeed, since known constructions of black-box non-malleable commitments are not efficient enough, we embark on an even more challenging task requiring as a subprotocol a commitment scheme that enjoys a weaker form of non-malleability. Thanks to the lighter security requirement but higher efficiency of this building block (that however introduces various other challenges to tackle in our security proofs), we will provide an efficient instantiation based on the black-box use of OWFs. [10, 26] already proposed a weakening of non-malleable commitments to achieve a black-box extractable commitment scheme from any OWF. These commitments are used to obtain round efficient multi-party computation protocols with black-box access to 1-1 OWFs. The commitment proposed in [26] has a logarithmic number of rounds, while [10] proposed a notion called non-malleability w.r.t. replacement that provides security only against synchronizing adversaries. As explained later in Sect. 1.2, our resulting scheme \(\varPi _{\textsf{NM}}\) is significantly simpler than the protocol given by Kim et al. in [20], which we will denote by \(\varPi _{{\textsf{KLP}}}\) hereafter. The protocol \(\varPi _{{\textsf{KLP}}}\) relies on symmetric cryptographic primitives and along the way the authors designed a new primitive, called instance-based non-malleable commitment (IB-NMC), which can be seen as an efficient instantiation of the non-malleable commitment scheme of [3, 12]. Indeed, they construct their IB-NMC scheme by modifying the scheme from [3, 12], denoted as \(\varPi _{\textsf{BGRRV}}\). This scheme itself comprises a three-round commit phase followed by a proof phase used to demonstrate the consistency of the commit phase. \(\varPi _{{\textsf{KLP}}}\) instantiates \(\varPi _{\textsf{BGRRV}}\) by employing, as the proof phase, an adapted version of the OR-composition protocol introduced by [7], applied to two instances of the Ligero protocol [1]. However, since Ligero is not a \(\varSigma \)-protocol, [20] needs to instantiate a variant of the OR-composition of argument systems, incurring an additional cost in both computations and communication. Consequently, the main drawbacks that limit the efficiency of \(\varPi _{{\textsf{KLP}}}\) are the large round complexity and the cost of running Ligero multiple times. A crude (i.e., without trying to parallelize subprotocols as this would require a new security analysis) calculation of the number of rounds required by \(\varPi _{{\textsf{KLP}}}\) indicates that 4 rounds are needed for the commitment phase, more than 20 rounds are required for the proof phase and the OR composition, and an additional 4 rounds must be exchanged to fix a trapdoor statement for the prover and verifier. We refer the reader to [20] for a full description of \(\varPi _{{\textsf{KLP}}}\).

We deviate from the approach of \(\varPi _{{\textsf{KLP}}}\) since we manage to use a subprotocol of the non-malleable commitment schemes of [3, 12] that is associated to a special and partial extractor. It is special because it has some extraction capabilities against a man-in-the-middle (MiM) without rewinding the honest sender; it is partial because the quality of the extraction is not as good as that provided by an extractor of a classical extractable commitment scheme.

The subprotocol of the non-malleable commitment scheme of \(\varPi _{\textsf{BGRRV}}\) that we will use consists only of the first 3 rounds of their commit phase and that we denote by \(\varPi ^{3R}_{\textsf{BGRRV}}\). This choice enables us to circumvent the complex and expensive computations of \(\varPi _{{\textsf{KLP}}}\), as these computations are due to the subsequent rounds (from the 4th round onwards) of the commit phase of \(\varPi _{\textsf{BGRRV}}\).

The special and partial extractor, given a transcript where the MiM mauls a commitment of a message m producing a well-formed commitment of a related message \(\tilde{m}\), succeeds in polynomial time and with non-negligible probability in extracting \(\tilde{m}\) without rewinding the honest sender. For simplicity, in this introduction we will refer to the property of a commitment scheme of admitting such a special and partial extractor as weak non-malleability^{Footnote 2}. We stress that in the formal part of the paper we will not explicitly define weak non-malleability; instead, we will formally refer to the existence of the above special and partial extractor introduced in [3, 12] and used in our work. The subprotocol \(\varPi ^{3R}_{\textsf{BGRRV}}\) by itself is not an extractable commitment scheme in the classical sense^{Footnote 3} since the special and partial extractor can fail with non-negligible probability in extracting the committed message on well-formed transcripts that can be sampled with non-negligible probability.

Our construction will require also classical extractability from such commitment scheme. Indeed, the simulator must be sure to obtain the actual message committed by the adversary. Therefore, we add a classical extractable commitment scheme \(\varPi _{\textsf{3Ext}}\) to \(\varPi ^{3R}_{\textsf{BGRRV}}\) obtaining a 5-round commitment scheme that is both extractable in the classical sense and weak non-malleable (i.e., it admits a specific and partial extractor that works against a MiM adversary).

Looking ahead, for generic statements, the computations required by our protocol mainly consist of three components: 1) One run of a classical 3-round public-coin SHVZK (e.g., ZKBoo/ZKB\(++\) introduced by  [4, 9] or \(\varSigma \)-protocols like Schnorr’s protocol [25]); 2) One run of a 3-round extractable commitment scheme \(\varPi _{\textsf{3Ext}}\); 3) One run of the weak-non-malleable commitment scheme \(\varPi ^{3R}_{\textsf{BGRRV}}\). Notice that both \(\varPi _{\textsf{3Ext}}\) and \(\varPi ^{3R}_{\textsf{BGRRV}}\) require black-box use of any one-way function only, and have been used and efficiently instantiated in [3, 20].

The efficiency of our protocol depends on the particular instantiation of the 3-round public-coin honest-verifier zero-knowledge \(\varPi _{\textsf{SHVZK}}\). More concretely, if \(\varPi _{\textsf{SHVZK}}\) is ZKBoo/ZKB++, then when proving the preimage of a SHA-256 output, the cost of our construction is dominated by a single run of ZKBoo/ZKB++ on this statement; instead, to prove the same claim on a SHA-256 output, the protocol of [20] adds several executions of Ligero [1] to prove other statements^{Footnote 4}. When proving for instance knowledge of a discrete logarithm using Schnorr’s protocol, the cost of running our scheme is dominated by \(\varPi _{\textsf{3Ext}}\) and \(\varPi ^{3R}_{\textsf{BGRRV}}\) and we can completely avoid expensive tools like ZKBoo/ZKB++/Ligero. In contrast, the construction of [20] would still require, in addition to \(\varPi _{\textsf{3Ext}}\) and \(\varPi _{\textsf{BGRRV}}\), multiple executions of Ligero on various statements that in turn impose to run the prover of Ligero in some cases and the special honest-verifier zero-knowledge simulator of Ligero in other cases. As shown in [20], the costs for these runs of Ligero strongly dominate all other costs.

Finally, without specific optimizations, we notice that our construction requires at most 9 rounds while the one of [20] requires more than 20 rounds. We give a detailed comparison in terms of efficiency between our scheme \(\varPi _{\textsf{NM}}\) and \(\varPi _{{\textsf{KLP}}}\) in Sect. 1.3. In particular, we show that to verify one instance of a SHA-256 preimage with 40-bit of statistical security, our scheme requires less than 100ms for the prover and less than 5MB of communication. This represents a \(15\times \) improvement in computation time and a \(4\times \) improvement in communication over \(\varPi _{{\textsf{KLP}}}\) which requires 20MB of communication and 1680ms of running time for the same circuit and security level. Finally, it is natural to expect that our significantly better round complexity would highly speed up the execution of the protocol when run on the Internet.

1.2 Overview of Techniques

We first propose a simple but insecure protocol, explaining why it fails. This is instrumental to better understand our more elaborated construction and its security properties.

A Naïve Protocol. We start with a 3-round public-coin special honest-verifier zero-knowledge (SHVZK) proof of knowledge \(\varPi _{\textsf{SHVZK}}\) for \(x \in \mathcal {L}\), where x is the common input and \((\pi _1,\pi _2,\pi _3)\) is the transcript of an execution of \(\varPi _{\textsf{SHVZK}}\). The classical approach to make such a protocol secure against malicious verifiers consists of allowing the simulator (that does not know the witness for x) to decide the challenge \(\pi _2\) of the transcript \((\pi _1,\pi _2,\pi _3)\) upfront. This can be achieved by computing \(\pi _2\) as the xor of two sub-challenges \(c_0\) and \(c_1\) obtained as follows. The former, \(c_0\), is chosen by the verifier and committed through an extractable commitment scheme \(\varPi _{\textsf{3Ext}}\) right after \(\pi _1\) is played; the latter, \(c_1\), is chosen and sent by the prover right after the commitment phase of \(\varPi _{\textsf{3Ext}}\) is over. The opening to \(c_0\) is played right after \(c_1\) is sent. After receiving the opening to \(c_0\) the prover can compute and send \(\pi _3\) to the verifier. In this way, the simulator will be able to decide the challenge \(\pi _2\) by running the extractor of \(\varPi _{\textsf{3Ext}}\) and computing \(c_1\) adaptively (i.e., \(c_1=\pi _2 \oplus c_0\)).

While the exchange of messages just described provides zero knowledge, all the above components are obviously malleable and therefore the protocol as it is can not be a NMZK argument. A well known approach for proving non-malleability consists of showing an even stronger property called simulation-extractability. According to this stronger notion, it is required to show an efficient simulator that can extract a witness for the statement proved by the adversary in a so-called right session, while the adversary is receiving a simulated proof acting as a verifier (in a so-called left session). Such approach would allow claiming that the protocol satisfies simulation-extractability, which clearly implies non-malleability^{Footnote 5}. The extraction of a witness for the instance proved by the adversary is in theory possible by running the proof of knowledge extractor of \(\varPi _{\textsf{SHVZK}}\). Unfortunately, this approach fails as we explain in the next paragraph.

Failure of the Extractor While Simulating. For simplicity, we will use \(\gamma \) to denote a message played in a round of the left session (where the adversary \(\textsf{A}_{\textsf{MiM}}\) acts as the verifier) and \(\tilde{\gamma }\) to denote the message corresponding to the same round of \(\gamma \) that is played in the right session (where \(\textsf{A}_{\textsf{MiM}}\) acts as the prover). We assume that \(\varPi _{\textsf{SHVZK}}\) is associated with a canonical extractor that, starting from an accepting transcript \((\tilde{\pi }_1,\tilde{\pi }_2,\tilde{\pi }_3)\) through rewinds, tries to obtain a constant number of additional pairs \((\tilde{\pi }_2^i,\tilde{\pi }_3^i)\), so that \((\tilde{\pi }_1,\tilde{\pi }_2^i,\tilde{\pi }_3^i)\) is also accepting and values \(\tilde{\pi }_2^i\) are all distinct with respect to each other and to \(\tilde{\pi }_2\). We need to argue that the above extractor is successful, even in the event where in the left session we are simulating the messages of \(\varPi _{\textsf{SHVZK}}\). In particular, note that the simulator decides the challenge \(\pi _2\) (used to run the SHVZK simulator of \(\varPi _{\textsf{SHVZK}}\) to obtain \((\pi _1,\pi _2,\pi _2)\)) and will force \(\pi _2\) in all the simulated transcripts as described above. In order to force the challenge \(\pi _2\), the simulator does the following. Upon receiving the extractable commitment, it extracts the underlying message (let us say \(c_0\)) and sends \( c_1=c_0\oplus \pi _2\) to the receiver (the adversary in this case).

Since all components of the above protocol are malleable, an adversary could mimic what the simulator does and, in turn, the adversary could manage to force the same value \(\tilde{\pi }_2\) in all the runs (i.e., \(\tilde{\pi }_2^i=\tilde{\pi }_2\)) invoked by the extractor on the right session, thus preventing the completion of the extraction.

Our NMZK Argument \(\boldsymbol{\varPi _\textsf{NM}}\) via Our Commitment Scheme \(\boldsymbol{\varPi _{\mathsf {5\textsf{Ext}}}}\). To solve the above malleability issue, we design our NMZK argument \(\varPi _\textsf{NM}\) replacing the extractable commitment scheme \(\varPi _{\textsf{3Ext}}\) used by the verifier to send the commitment of a share \(\tilde{c}_0\) of \(\tilde{\pi }_2\) with a new commitment scheme with special properties. Specifically, we start with scheme given by the first three rounds of \(\varPi _{\textsf{BGRRV}}\) [3], which we denote by \(\varPi _{\textsf{BGRRV}}^{3R}\). This is a 3-round commitment scheme that has the special and partial extractor discussed earlier and we informally call weak non-malleability the corresponding property.

Note that \(\varPi _{\textsf{BGRRV}}^{3R}\) is not an extractable commitment in the classical sense and this limitation would hurt the simulator. As such, we will enhance \(\varPi _{\textsf{BGRRV}}^{3R}\) by adding also a run of \(\varPi _{\textsf{3Ext}}\) to it, so that the resulting 5-round commitment scheme, that we denote with \(\varPi _{\mathsf {5\textsf{Ext}}}\), is both extractable in the classical sense and enjoys the special and partial extractability property (we refer the reader to the next paragraph for a more detailed description of \(\varPi _{\mathsf {5\textsf{Ext}}}\)).

We can now return to the previous attempt of relying on the canonical extractor of \(\varPi _{\textsf{SHVZK}}\). While trying to obtain an additional accepting transcript \(\tilde{\pi }_1,\tilde{\pi }_2',\tilde{\pi }_3'\) with a new \(\tilde{\pi }_2'\), a new sub-challenge \(\tilde{c}_0'\) will be played (recall that the extractor of \(\varPi _\textsf{NM}\) acts as a verifier, and as such, it can sample \(\tilde{c}_0'\)). In more detail, the extractor of \(\varPi _\textsf{NM}\) completes a full execution on the right session committing via \(\varPi _{\mathsf {5\textsf{Ext}}}\) to a random string \(\tilde{c}_0\). Upon collecting the accepting transcript \(\tilde{\pi }_1,\tilde{\pi }_2,\tilde{\pi }_3\) (we recall that \(\tilde{\pi }_2=\tilde{c}_0 \oplus \tilde{c}_1\)), the extractor of \(\varPi _\textsf{NM}\) rewinds the adversary and changes the message committed via \(\varPi _{\mathsf {5\textsf{Ext}}}\), from \(\tilde{c}_0\) to a new random \(\tilde{c}_0'\), and completes this execution collecting the new transcript \(\tilde{\pi }_1,\tilde{\pi }_2',\tilde{\pi }_3'\). We need to argue that \(\tilde{\pi }_2'\ne \tilde{\pi }_2\), as this would allow the extractor of \(\varPi _\textsf{NM}\) to invoke the underlying extractor of \(\varPi _{\textsf{SHVZK}}\), enabling the extraction of the witness for the statement proven in the right session by \(\textsf{A}_{\textsf{MiM}}\).

The event where the MiM \(\textsf{A}_{\textsf{MiM}}\) of \(\varPi _\textsf{NM}\) manages with non-negligible probability to choose the sub-challenge \(\tilde{c}_1'\) so that \(\tilde{\pi }_2'=\tilde{c}_0' \oplus \tilde{c}_1'=\tilde{\pi }_2\) (i.e., the challenge of \(\varPi _{\textsf{SHVZK}}\) does not change during the rewinds) can now be leveraged to contradict the hiding of \(\varPi _{\mathsf {5\textsf{Ext}}}\) using its weak non-malleability (i.e., relying on the existence of a special and partial extractor that outputs with non-negligible probability the message committed by a MiM without rewinding the honest sender). Indeed, we will show that the above successful \(\textsf{A}_{\textsf{MiM}}\) can be embedded in a successful MiM of \(\varPi _{\mathsf {5\textsf{Ext}}}\) and this let us rely on the special and partial extractor.

The reduction to the hiding of \(\varPi _{\mathsf {5\textsf{Ext}}}\) includes a few values such as \(\pi _1,\pi _2,\tilde{\pi }_1,\tilde{\pi }_2\) that ensure that in the end, with non-negligible probability, it will happen that \(\tilde{c}_1'\) is such that \(\tilde{\pi }_2'=\tilde{c}_0' \oplus \tilde{c}_1'=\tilde{\pi }_2\). Notice that \(\pi _1\) and \(\tilde{\pi }_1\) are known before \(\varPi _{\mathsf {5\textsf{Ext}}}\) on the right session starts, and the pair \((\pi _2,\tilde{\pi }_2)\) exists by contradiction since otherwise, the adversary would force the same challenge in the right session with negligible probability only, in which case we would not even need this reduction.

The reduction itself runs a modified experiment that does not use the extractor of the classical extractability property of \(\varPi _{\mathsf {5\textsf{Ext}}}\), but it uses instead the special and partial extractor associated to the weak non-malleability of \(\varPi _{\mathsf {5\textsf{Ext}}}\). Moreover, the reduction stops the execution of \(\varPi _\textsf{NM}\) when the adversary sends \(\tilde{c}_1\) since this provides enough information to break the hiding of \(\varPi _{\mathsf {5\textsf{Ext}}}\).

The goal of forcing a specific value for \(\pi _2\) on the left will be achieved by attempting an extraction of \(c_0\) through the special and partial extractor of \(\varPi _{\mathsf {5\textsf{Ext}}}\). While this partial extractor is not guaranteed to succeed with overwhelming probability, it outputs the correct \(c_0\) with non-negligible probability, and this is sufficient for our purposes. The reduction embeds \(\textsf{A}_{\textsf{MiM}}\) and starts its interaction with the challenger of the hiding of \(\varPi _{\mathsf {5\textsf{Ext}}}\), picking the two different challenge messages \(m_0,m_1\) that are two random \(\lambda \)-bit strings. The challenger now samples a bit \(b\leftarrow \{0,1\}\) and commits to \(m_b\). The reduction now acts as a proxy between the messages generated by the challenger and those generated by \(\textsf{A}_{\textsf{MiM}}\) with respect to \(\varPi _{\mathsf {5\textsf{Ext}}}\). Upon receiving \(\tilde{c}_1'\) from the adversary, the reduction computes \(\tilde{\pi }_2\oplus \tilde{c}_1'=\textsf{candidate}\). We now observe the following. We assumed that, conditioned on \(\pi _2\) being the challenge on the left, with non-negligible probability \(\textsf{A}_{\textsf{MiM}}\) manages to send a value \(\tilde{c}_1'\), such that the xor of \(\tilde{c}_1'\) with the message committed by the challenger via \(\varPi _{\mathsf {5\textsf{Ext}}}\) is equal to \(\tilde{\pi }_2\). Notice that \(\pi _2\) will be the actual challenge of \(\varPi \) in the left session with non-negligible probability since the partial extractor succeeds extracting \(c_0\) with non-negligible probability. In turn, this will imply that also \(\widetilde{\pi }^2\) will be the challenge of \(\varPi \) in the right session and thus, \(\textsf{candidate}\), with non-negligible probability, represents the message committed by the challenger of hiding (i.e., \(m_b=\textsf{candidate}\)). Note that \(\textsf{candidate}\) may, (still with non-negligible but not overwhelming probability) differ from both \(m_0\) and \(m_1\). In this case (i.e., \(\textsf{candidate}\) is neither equal to \(m_0\) nor \(m_1\)), the reduction will make a random guess. Note that whenever \(\textsf{candidate}\) is instead equal to \(m_{b'}\) (with \(b'\in \{0,1\}\)), the reduction is sure that \(b'=b\). This is because \(m_0\) and \(m_1\) are two random strings unknown to \(\textsf{A}_{\textsf{MiM}}\), hence, the probability that the challenger is committing to \(m_b\), and we instead obtain \(\textsf{candidate}=m_{1-b}\) is negligible (i.e., the adversary can only hope to guess \(m_{1-b}\), as \(m_{1-b}\) does not appear in the view of the adversary, but this is going to be negligible when the message space is large enough). For these reasons, we can then conclude that our reduction is successful.

Summing up, we rely on the classical extractability property of a commitment scheme to obtain a transcript that is indistinguishable from a real game. Next, we rely on the classical witness extraction procedure consisting of changing \(\tilde{\pi }_2\) on the right while forcing the same \(\pi _2\) on the left, and if this succeeds, the simulator-extractor ends adding to the above transcript also a correct witness. If the simulator-extractor fails, then through hybrid games we can show that the failure of the simulator-extractor can be reduced to an adversary breaking the hiding of \(\varPi _{\mathsf {5\textsf{Ext}}}\). This reduction will use the weak non-malleability of \(\varPi _{\mathsf {5\textsf{Ext}}}\).

Finally, we observe that a crucial reason why weak-non-malleability of the commitment scheme suffices is that a successful adversary of \(\varPi _\textsf{NM}\) must complete the right session committing and correctly opening the commitment. Therefore a malleability attack producing a badly-formed commitment (that is a commitment for which the special and partial extractor would fail) would not correspond to a succeeding adversary in our NMZK argument system.

Making \(\boldsymbol{\varPi _{\textsf{BGRRV}}^{3R}}\) Extractable Obtaining \(\boldsymbol{\varPi _{\mathsf {5\textsf{Ext}}}}\). In the above discussion we have assumed that \(\varPi _{\mathsf {5\textsf{Ext}}}\) is weak-non-malleable, and enjoys classical extractability. By classical extractability here we mean that, given an initial transcript of \(\varPi _{\mathsf {5\textsf{Ext}}}\), generated from an interaction between a corrupted sender and an honest receiver, it is possible to rewind the sender to obtain a message m, such that if the commitment generated by the sender admits a valid opening, this opening will correspond to m. If instead, the commitment does not admit an opening, then we have no guarantee about the correctness of the extracted message. \(\varPi _{\textsf{BGRRV}}^{3R}\) does not satisfy this notion of extractability. To see why this is the case, we recall how, at a very high level, \(\varPi _{\textsf{BGRRV}}^{3R}\) works. Let m be the message that we want to commit to. The sender sends a non-interactive commitment of m and of a random group element r. The receiver sends a random group element \(\alpha \), and in the third round, the sender replies with \(a=r \alpha +m\).

Consider now a corrupted sender that computes a well-formed commitment (following the steps described above). A candidate extractor then could work by sending a new second round \(\alpha '\), thus obtaining \(a'\). At this point, the extractor can interpolate the points \((a,\alpha ),(a',\alpha ')\) thus obtaining a message \(m'\). Note that in the rewinding thread, the adversary could have used completely different values of r and m to compute \(a'\), hence, it can happen that the extracted value is \(m'\) with \(m'\ne m\). The hiding of the non-interactive commitment prevents the extractor from understanding whether it is extracting the correct value. Hence, even if the original commitment generated by the sender is valid, the extractor we have described fails. It is not clear whether there is a succeeding extraction procedure, hence, we modify \(\varPi _{\textsf{BGRRV}}^{3R}\), to make it extractable obtaining \(\varPi _{\mathsf {5\textsf{Ext}}}\).

Let us now see how to add classical extractability. We modify \(\varPi _{\textsf{BGRRV}}^{3R}\) obtaining a 5-round protocol that we denote by \(\varPi _{\mathsf {5\textsf{Ext}}}\). This new protocol is obtained via a simple modification. We replace the non-interactive commitments of \(\varPi _{\textsf{BGRRV}}^{3R}\), with a three-round extractable commitment \(\varPi _{\textsf{3Ext}}\). It is clear that this new commitment scheme is now extractable. In particular, the extractor of \(\varPi _{\mathsf {5\textsf{Ext}}}\) can run the extractor of \(\varPi _{\textsf{3Ext}}\) to obtain and return m. The extraction is successfully conditioned (i.e., it outputs the committed message with non-negligible probability) on the adversarial sender providing a well-formed commitment.

We need also to argue that the obtained scheme is still weak-non-malleable (i.e., it admits a special and partial extractor). We first observe that the scheme is hiding. Then we prove that it is weak-non-malleable, via a reduction to its hiding property. The reduction works as follows, an external challenger acts as a committer against (in the left session) a MiM, and we define an extractor that extracts the message committed by MiM (on the right session) either by running the partial extractor of \(\varPi _{\textsf{BGRRV}}^{3R}\) (which exists due to the weak-non-malleability of the scheme), or by running the extractor of \(\varPi _{\textsf{3Ext}}\). The choice of which extractors to run depends on the message schedule. In particular, there are two main cases of message schedule to consider: case 1) the right-session messages of \(\varPi _{\textsf{BGRRV}}^{3R}\) align with the messages of \(\varPi _{\textsf{3Ext}}\) in the left session; case 2) any other message schedule where case (1) does not occur.

In case (1), we can not extract from \(\varPi _{\textsf{BGRRV}}^{3R}\), as the rewinds would, in turn, rewind the messages of \(\varPi _{\textsf{3Ext}}\) generated from the challenger (which would compromise the hiding of the entire scheme). Hence, in this case, the extraction is performed using the extractor of \(\varPi _{\textsf{3Ext}}\). Note that this does not cause a problem, as in this message schedule, the second and third rounds of \(\varPi _{\textsf{3Ext}}\) in the right session could (in the worst case) be aligned with the second and third rounds of \(\varPi _{\textsf{BGRRV}}^{3R}\) in the left session. But we will argue that this does not cause issues in the reduction as we can generate locally valid third-round messages for \(\varPi _{\textsf{BGRRV}}^{3R}\) (i.e., the third round of \(\varPi _{\textsf{BGRRV}}^{3R}\) can be randomly generated).

For all schedules that fall in (2) instead, the extraction can be performed by simply running the partial extractor of \(\varPi _{\textsf{BGRRV}}^{3R}\) (that exists from the weak-non-malleability). Due to the way we have defined (2), the rewinds performed on the right session can only rewind the messages of \(\varPi _{\textsf{BGRRV}}^{3R}\), but as discussed, this is something that \(\varPi _{\textsf{BGRRV}}^{3R}\) can deal with. This concludes this high-level description of the proof, but we refer the reader to Sect. 4 for a formal proof.

1.3 Efficiency and Comparison with Previous Results

Here we analyze the efficiency of our main protocol \(\varPi _{\textsf{NM}}\) and compare it to state-of-the-art  NMZK argument systems. We want to stress that the goal of this section is not to provide a precise evaluation of the efficiency of our construction; instead we aim to compare it with the current state of the art.

Instantiation and efficiency of the main building blocks of \(\varPi _{\textsf{NM}}\). At a high level, our scheme consists of two main building blocks, namely the 5-round extractable commitment scheme, \(\varPi _{\mathsf {5\textsf{Ext}}}\), obtained by compiling the 3-round weak-non-malleable commitment scheme of [3], that we denote by \(\varPi ^{3R}_{\textsf{BGRRV}}\) (see the full version for a complete description), and a SHVZK protocol \(\varPi _{\textsf{SHVZK}}\) that we can instantiate for example with an optimized version of ZKBoo [4, 9] or Schnorr’s protocol.

We examine these two components separately, and follow the analysis given in [20] for the first building block. However, as mentioned before, compared to [20], we only need to instantiate \(\varPi ^{3R}_{\textsf{BGRRV}}\) deduced from the first three rounds of [3] and thus we avoid the consistency proof of the committed phase.

The perfect binding commitment scheme used in the first round of \(\varPi _{\mathsf {5\textsf{Ext}}}\) is instantiated with Naor’s commitment scheme [21] for messages longer that one bit, where the PRGs used to mask the message can be implemented using AES in CTR mode. Denoting by \(\textrm{AES}_\lambda \) an evaluation of AES on a \(\lambda \)-bit string, the extractable commitment scheme requires roughly \(3\lambda \) \(\textrm{AES}_{\lambda }\) in the commitment phase and \(2\lambda \) \(\textrm{AES}_\lambda \) in the decommitment stage. In addition, the verifier needs to evaluate \(\lambda \) dot-products on vectors of length \(2\lambda \) over \({\mathbb {Z}}_q\), with \(q \approx 2^\lambda \).

For the second building block, we choose an improved version of the ZKBoo protocol described by [9]. This is a 3-round SHVZK argument system based on the MPC-in-the-head paradigm of [15]. ZKBoo is only based on symmetric assumptions and has been successfully used to build efficient post-quantum secure signature schemes. We recall that ZKBoo, like almost all MPC-in-the-head protocols, require a certain number \(\rho \) of parallel repetitions to achieve the desired soundness error of \(2^{-\sigma }\), where \(\sigma \) is the statistical security parameters.

In our analysis, we also use the version of the protocol proposed by Chase et al. [4] that presents several optimizations especially in communication complexity. As done in [20] with Ligero, we use ZKBoo figures to estimate the concrete efficiency of our protocol. Notice, both Ligero and ZKBoo instantiate their main components similarly, i.e., random tapes are generated using AES in CTR mode; commitments are implemented using SHA-256, under the assumption that SHA-256 is a collision-resistant hash function and SHA-256\((r||\cdot )\) is a PRF (with key r)). Alternatively, to avoid random-oracle-based commitments we should use the commitment scheme proposed by Halevi and Micali [13]. In more details, we denote by |C| the size of the circuit C being evaluated and by m the number of its multiplication gates; we measure the complexity of our protocol for a given circuit C in terms of number of \(\textrm{AES}_\lambda \) and \(\mathrm {SHA\hbox {-}256}_\lambda \), where, as previously mentioned, \(\textrm{AES}_\lambda \) (or \(\mathrm {SHA\hbox {-}256}_\lambda \)) indicates an evaluation of the AES block cipher (resp. SHA-256) evaluations on a \(\lambda \)-bit string, similarly to what is done in [20]. Since the number of views needed for the MPC emulations in the ZKBoo protocol is only 3, overall this protocol requires roughly \(3 \cdot m \cdot \rho \) \(\textrm{AES}_\lambda \) and \(m \cdot \rho \) \(\mathrm {SHA\hbox {-}256}_\lambda \).

Communication Complexity. A main advantage of our approach is the very low round complexity compared to \(\varPi _{{\textsf{KLP}}}\), which makes our protocol significantly better than previous ones especially in the WAN setting. Let C be a circuit over \({\mathbb {Z}}_{2^\ell }\), where \(\ell =2\lambda \), with \(|\textsf{inp}|\) input wires and m multiplication gates. To estimate the communication complexity, again we consider the main components of our scheme. We report the optimized overall cost of ZKBoo as given in [4]:

In the extractable commitment step, we need to communicate approximatively \(4 \lambda ^2\) bits for commitments and again \(\lambda ^2\) challenge bits.

We summarized the analysis of the costs and comparison to [20] in Table 1. While the table only considers asymptotic complexity, we can have a more concrete idea of the different complexity of the two protocols by considering the case C= SHA-256 (i.e., by estimating the circuits in the table when proving knowledge of preimages of SHA-256). We use the “Bristol fashion” circuit^{Footnote 6} representation for SHA-256, AES-128 and AES-256 and set \(k=32\) [20]. This will give \(|C| \approx 120000\), \(|C_{\textsf{cons}}| \approx 5 \cdot 10^6\), \(|C_{\textsf{eq}}| \approx 30000\) and \(m \approx 22600\). We can see that our scheme achieves a significant improvement compared to the scheme of Kim et al. with less than half rounds.

In addition to this analysis, and in support of it, we can also try to estimate the running time of our scheme by considering the running time of its main building blocks. Once again, we follow the same analysis done in [20], which also gives estimated figures by using for all the Ligero executions the figures given in [1]. Specifically, we adopt the same efficiency approximation for AES and SHA-256 as described in [20]. Additionally, we consider the single-threaded version of the implementation of ZKBoo, provided by [9]. The work of Giacomelli et al. reports that proving SHA-256 takes roughly 30.81 ms for the prover and 34.16 ms for the verifier with communication of \(\approx \) 193KB when \(\sigma =40\), and 54.63ms for the prover and 67.74 ms for the verifier and requires communication of roughly 383 KB when the statistical security parameter \(\sigma =80\). Consequently, using \(\varPi _{\textsf{NM}}^{\textsf{ZKBoo}}\) for proving SHA-256 with a statistical security parameter \(\sigma \) set to 40 (or 80) results in a runtime of less than 100ms (or 300 ms), along with communication requirements of less than 5 MB. This is in stark contrast to the \(\varPi _{{\textsf{KLP}}}\) protocol, which necessitates approximately 1680ms (or 5000 ms) and communication of around 20MB for the same security levels.

Throughout this paper, we will use \(\lambda \) to denote the security parameter and \(\textsf{negl}(\lambda )\) to denote any function which tends to zero faster that \(\lambda ^{-c}\), for any constant c. We write [n] to denote the set \(\{1,\dots ,n\}\). We use the abbreviation ppt to denote probabilistic polynomial time. We use boldface to denote vectors, and \(\langle \cdot ,\cdot \rangle \) to denote inner product of vectors.

Let A and B be two interactive machines, we denote by (A, B) an interactive protocol between them. We denote by \(\left\langle A(a),B(b)\right\rangle (x)\) the interaction between A and B on common input x and private input a for A and private input b for B. We denote by \(\tau \) the transcript generated by \(\left\langle A(a),B(b)\right\rangle (x)\). We denote by \(Out_A(\left\langle A(a),B(b)\right\rangle (x))\) the output of A after the execution of the protocol and \(Out_B(\left\langle A(a),B(b)\right\rangle (x))\) the output of B after the execution of the protocol.

We denote by \(A^B(x)\) the output of A on input x and given oracle access to B.

Commitment Schemes. A commitment scheme \(\varPi _\texttt{com}=(\mathcal {C},\mathcal {R})\) is a two-phase protocol between two ppt interactive algorithms, a committer \(\mathcal {C}\) and a receiver \(\mathcal {R}\). In the first phase, called commit phase, \(\mathcal {C}\) on input a message m interacts with \(\mathcal {R}\). Let \(\tau = \langle \mathcal {C}(m,r_c),\mathcal {R}(r_r)\rangle \) denote the commitment transcript with committer input m, \(\mathcal {C}\) randomness \(r_c\) and \(\mathcal {R}\) randomness \(r_r\). In the second phase, called decommitment phase, the committer \(\mathcal {C}\) reveals \(m'\) and \(\mathcal {R}\) accepts the value committed in \(\tau \) to be \(m'\) if and only if \(\mathcal {C}\) proves that \(\tau \) can be produced on input \(m'\). We only consider commitment schemes where the decommitment phase consists of a single message from \(\mathcal {C}\) to \(\mathcal {R}\). Let \(\textsf{Dec}(\tau ,m,r_c)\) denote the polynomial time deterministic algorithm that outputs 1 or 0 to denote whether or not the decommitment was accepted. We say that a commitment scheme is delayed input if the message to commit is required only at the last round of the commit phase. A commitment scheme satisfies two main properties: informally, the binding property ensures that \(\mathcal {C}\) cannot open the commitment in two different ways; the hiding property guarantees that the commit phase does not reveal any information about the message m. We also consider non-interactive commitments. In this case the commitment phase consists of a single message sent by the committer to the receiver using an algorithm \(\textsf{Com}\) with some randomness \(r_c\). Moreover, we will indicate with the term well-formed transcript a transcript \(\tau \) of the commitment phase for which there exists a pair \((m,r_c)\) such that \(\textsf{Dec}(\tau ,m,r_c)=1\). We refer the reader to the full version for more details.

2.1 Extractable Commitments

Informally, a commitment scheme is said to be extractable (with over-extraction) if there exists a ppt extractor that extracts the committed value conditioned on the commitment being well-formed. Formally, we report the definition of [24].

Definition 1

Consider any statistically binding, computationally hiding commitment scheme \(\varPi _{\texttt{com}\textsf{Ext}}=(\mathcal {C},\mathcal {R})\). Then \(\varPi _{\texttt{com}\textsf{Ext}}\) is said to be extractable if there exists an expected ppt oracle algorithm \(\textsf{Ext}\) (the extractor) that, given oracle access to any ppt committer \(\mathcal {C}^*\), outputs a transcript \(\tau \) and a message m such that the following holds: (i) \(\tau \) is identically distributed to the view of \(\mathcal {C}^*\) when interacting with an honest receiver \(\mathcal {R}\) in commitment phase; (ii) the probability that \(\tau \) is a well-formed transcript and \(m=\bot \) is negligible; (iii) if \(m\ne \bot \) then \(\Pr [(\exists \tilde{m} \ne m,\tilde{r}_c): \textsf{Dec}(\tau ,\tilde{m},\tilde{r}_c)=1] \le \textsf{negl}(\lambda )\).

We also add the following definition that we use later in Sect. 4.

Definition 2

(2-Extractable Commitments). A 3-round (resp. 4-round, resp. 5-round) commitment scheme is said to be 2-extractable if, there exists a polynomial-time extractor algorithm \(\textsf{Ext}\) that given a set of 2 well-formed transcripts \(\{a, c_i, z_i\}_{i\in [2]}\) (resp. \(\{\gamma ,a, c_i, z_i\}_{i\in [2]}\), resp. \(\{\alpha ,\gamma ,a, c_i, z_i\}_{i\in [2]}\)) of the commitment phase w.r.t. the same committed message, where for each \(j,j'\in [2]\), \(j\ne j'\), \(c_j\ne c_{j'}\), outputs the value committed in \(\{a, c_1, z_1\}\) (resp. \(\{\gamma ,a, c_1, z_1\}\), resp. \(\{\alpha ,\gamma ,a, c_1, z_1\}\)) except with negligible probability.

2.2 Commitment Schemes and Man-in-the-Middle Attacks

Here we report the definition of non-malleable commitment scheme from [12]. Even though our construction will not include a non-malleable commitment, still we need to use a commitment scheme with special properties against a man-in-the-middle (MiM) adversary \(\textsf{MIM}\). Indeed we need a commitment scheme for which [12, Theorem 4] holds (we report this theorem in Sect. 3). Non-malleable commitments are defined considering two experiments that are required to produce indistinguishable views. We will refer to a game where a distinguisher would like to guess which among the two experiments as the indistinguishability game. The MiM execution is the following. Consider a (MiM) adversary \(\textsf{MIM}\) that is participating in two interactions called the left and the right interactions. In the left interaction \(\textsf{MIM}\) is the receiver and interacts with an honest committer \(\mathcal {C}\), whereas in the right interaction \(\textsf{MIM}\) is the committer and interacts with an honest receiver \(\mathcal {R}\). We denote all the entities used in the right session using the tilde symbol on the corresponding entities used on the left. So, if m is the value committed by \(\mathcal {C}\), \(\tilde{m}\) is the value committed by \(\textsf{MIM}\) on the right. We assume \(\mathcal {C}\) has an identity \(\textsf{id}\in \{0,1\}^k\) of its choice, for \(k=\varOmega (\lambda )\). At the onset of the commitment phase, \(\mathcal {C}\) receives the value m in input while \(\textsf{MIM}\) receives an auxiliary input \(\textsf{aux}\). In the left session, the MiM adversary \(\textsf{MIM}\) interacts with \(\mathcal {C}\) receiving a commitment to message m using identity \(\textsf{id}\). In the right session, \(\textsf{MIM}\) interacts with \(\mathcal {R}\) attempting to commit to a related value \(\tilde{m}\) using an identity \(\tilde{\textsf{id}}\) of its choice. If the right commitment is invalid, or undefined, the committed value is set to \(\bot \). If \(\textsf{id}= \tilde{\textsf{id}}\), we set the committed value to \(\bot \) (i.e., when the adversary uses the same identity of the honest committer the attack is invalid). Let \(\textsf{MIM}_{(\mathcal {C}, \mathcal {R})}(m,\textsf{aux})\) be the random variable that describes \((\textsf{view}, \tilde{m})\), consisting of the values committed by \(\textsf{MIM}\) and \(\textsf{MIM}\)’s view in the experiment above.

In the simulated execution, a simulator \(\textsf{SIM}\) directly interacts with \(\mathcal {R}\). Let \(\textsf{SIM}_{(C,R)}(1^\lambda ,\textsf{aux})\) be the random variable describing \((\textsf{view},\tilde{m})\), given by the values committed by \(\textsf{SIM}\) and its output. As before, whenever \(\textsf{SIM}\) commits in the right interaction a commitment for which the identity is the same as one of the left interaction, the committed value is set to \(\bot \). We consider one-one non-malleable commitments, where \(\textsf{MIM}\) participates in one left and one right interaction.

We will denote a ppt MiM adversary \(\textsf{MIM}\) participating in the above indistinguishability game as a valid MiM.

We report the following definition from [12].

Definition 3

A valid ppt MiM adversary \(\textsf{MIM}\) is successful if there exists a message m and a ppt distinguisher D such that \(\Pr [D(\textsf{MIM}_{(\mathcal {C}, \mathcal {R})}(m,\textsf{aux})_{\textsf{aux}\in \{0,1\}^*})=1]-\Pr [D(\textsf{SIM}_{(\mathcal {C}, \mathcal {R})}(1^\lambda ,\textsf{aux})_{\textsf{aux}\in \{0,1\}^*})=1]\ge \frac{1}{p(\lambda )}\) for some polynomial p and infinitely many \(\lambda \).

Given a successful \(\textsf{MIM}\) as described in Definition 3, it holds that for every successful ppt MiM adversary \(\textsf{A}\) there exists a pair of messages \(m_0\), \(m_1\) and a ppt distinguisher D such that \(\Pr [(D(\textsf{MIM}_{(\mathcal {C}, \mathcal {R})}(m_0,\textsf{aux})_{\textsf{aux}\in \{0,1\}^*})=1]-\Pr [D(\textsf{MIM}_{(\mathcal {C}, \mathcal {R})}(m_1,\textsf{aux})_{\textsf{aux}\in \{0,1\}^*})=1]\ge \frac{1}{p(\lambda )}\) for some polynomial p and infinitely many \(\lambda \).

Definition 4

Let \(\textsf{MIM}\) be a valid MiM ppt adversary which interacts with an honest sender in the left session with tag \(\textsf{id}\) and an honest receiver in the right session with tag of his choice \(\tilde{\textsf{id}}\) in the execution of an n-round protocol \(\varPi =(\mathcal {C},\mathcal {R})\). Let \(\tau =(com_1,\dots ,com_n,\widetilde{com_1},\ldots ,\widetilde{com_n})\) be the transcript (i.e., the messages generated in the left and right sessions) obtained at the end of such an interaction. We say that \(\tau \in \textsf{WELLF}\) if \((com_1,com_2,\dots ,com_n)\) and \((\widetilde{com_1}, \widetilde{com_2},\dots , \widetilde{com_n})\) are both well-formed (i.e., both the right and left session transcripts represent commitments that admit a valid opening).

2.3 Arguments/Proofs

Informally an interactive argument/proof system for an \(\mathcal {N}\mathcal {P}\)-language \(\mathcal {L}\) with associated relation \({\textsf{Rel}}_{\mathcal {L}}\) is a pair of ppt interactive algorithms \(\varPi =(\mathcal {P}, \mathcal {V})\) for which no cheating \(\mathcal {P}^*\) can convince, with non-negligible probability, an honest verifier on some instance \(x\) that does not belong to \(\mathcal {L}\). The formal definitions of proof system and SHVZK can be found in the full version.

We say that \(\varPi =(\mathcal {P}, \mathcal {V})\) is public coin if, at every round, \(\mathcal {V}\) simply tosses a predetermined number of coins (i.e., a random challenge) and sends the outcome to the prover. We denote with \(\pi ^0,\pi ^1,\ldots ,\pi ^\ell \) the messages of the transcript generated by \(\left\langle \mathcal {P}(w),\mathcal {V}\right\rangle \). For readability we use \(\pi ^0\) when the first message is sent by \(\mathcal {V}\) otherwise we start to enumerate the messages from 1. Moreover we say that the transcript \(\tau \) of an execution \(\langle \mathcal {P}(w), \mathcal {V}\rangle (x)\) is accepting if \(Out_\mathcal {V}(\left\langle \mathcal {P}(w),\mathcal {V}\right\rangle (x))=1\).

In the following, we consider the special case in which the number of rounds of \(\varPi \) is 3 (resp. 4), i.e. the messages of the transcript are \((\pi ^1,\pi ^2,\pi ^3)\) (resp. \((\pi ^0,\pi ^1,\pi ^2,\pi ^3)\)). We recall the following definition.

Definition 5

(Proof of Knowledge with Canonical Extractability). A 3-round (resp., 4-round) proof system \(\varPi =(\mathcal {P}, \mathcal {V})\) for an \(\mathcal {N}\mathcal {P}\)-language \(\mathcal {L}\) associated to a relation \({\textsf{Rel}}_{\mathcal {L}}\) as defined above, is a proof of knowledge with canonical extractor if there exists an expected ppt extractor \(\textsf{Ext}\) such that, for any ppt adversarial prover \(\mathcal {P}^*\) that interacting with \(\mathcal {V}\) produces an accepting transcript for a statement \(x\in \mathcal {L}\) with probability \(p\ge \frac{1}{|x|^c}\) for some constant c, then:

• \(\textsf{Ext}\) runs as \(\mathcal {V}\) with \(\mathcal {P}^*\), terminating and giving in output the transcript; if this transcript is not accepting than \(\textsf{Ext}\) stops, otherwise let \((\pi ^1,\pi ^2_1,\pi ^3_1)\) (resp. \((\pi ^0,\pi ^1,\pi ^2_1,\pi ^3_1)\)) be the accepting transcript;

• then \(\textsf{Ext}\) rewinding multiple times \(\mathcal {P}^*\) and playing each time a new random value instead of \(\pi ^2_1\) with overwhelming probability obtains a constant number k of accepting transcripts all with the same \(\pi ^1\) (resp. \(\pi ^0,\pi ^1\)) and different challenges;

• obtained k accepting transcripts \((x,\pi ^1,\pi ^2_i,\pi ^3_i)_{i\in [k]}\) (resp. \((x,\pi ^0,\pi ^1,\pi ^2_i,\pi ^3_i)_{i\in [k]}\)) such that for each \(j,z\in [k]\), \(j\ne z\), \(\pi ^2_j\ne \pi ^2_z\), \(\textsf{Ext}\) outputs a witness \(w\) such that \({\textsf{Rel}}_{\mathcal {L}}(x,w)=1\).

2.4 Non-malleable Interactive Arguments/Proofs

Let \(\{(\mathcal {P}_\textsf{id},\mathcal {V}_\textsf{id})\}_{\textsf{id}\in \{0,1\}^*}\) be a family of interactive argument/proof system for an \(\mathcal{N}\mathcal{P}\) language \(\mathcal {L}\) with the associated relation \({\textsf{Rel}}_{\mathcal {L}}\). Let \(x\in \mathcal {L}\) such that \(|x|=\lambda \) be the public input of the protocol and \(w\) \(\mathcal {P}\)’s private input such that \({\textsf{Rel}}_{\mathcal {L}}(x,w)=1\).

Let \(\textsf{MIM}\) be a ppt MiM adversary that is simultaneously participating in one left section with \((\mathcal {P}_\textsf{id},\mathcal {V}_\textsf{id})\) and one right session with \((\mathcal {P}_{\tilde{\textsf{id}}},\mathcal {V}_{\tilde{\textsf{id}}})\). \(\textsf{MIM}\) receives as auxiliary input \(\textsf{aux}\in \{0,1\}^*\). In the left session \(\textsf{MIM}\) verifies the validity of the statement \(x\) by interacting with \(\mathcal {P}\) using identity \(\textsf{id}\). In the right session \(\textsf{MIM}\) proves the validity of the statement \(\tilde{x}\) (chosen adaptively by \(\textsf{MIM}\)) to the honest verifier \(\mathcal {V}\), using identity \(\tilde{\textsf{id}}\) of \(\textsf{MIM}\)’s choice. Let \(\textsf{view}^\textsf{MIM}(x, \textsf{aux},\textsf{id})\) denote the joint view of \(\textsf{MIM}(x,\textsf{aux})\) and the honest verifier \(\mathcal {V}\) when \(\textsf{MIM}\) is verifying a statement \(x\) in the left execution, using identity \(\textsf{id}\), and proving on the right a statement \(\tilde{x}\) using identity \(\tilde{\textsf{id}}\).

Definition 6

(Simulation-Extractability [23]). A family of argument/proof systems \(\{(\mathcal {P}_\textsf{id},\mathcal {V}_\textsf{id})\}_{\textsf{id}\in \{0,1\}^*}\) for an \(\mathcal {N}\mathcal {P}\)-language \(\mathcal {L}\) with witness relation \({\textsf{Rel}}_\mathcal {L}\) is simulation extractable with tags of length \(m=m(|x|)\) if for any MiM adversary \(\textsf{MIM}\) that participates in one left session and one right session, there exists an expected ppt \(\textsf{Sim}\) such that:

1. 1.

   The two ensembles \(\{ \textsf{Sim}^1(x, \textsf{aux},\textsf{id}) \}_{x\in \mathcal {L}, \textsf{aux}\in \{0,1\}^*,\textsf{id}\in \{0,1\}^{m}}\) and \(\{ \textsf{view}^\textsf{MIM}(x,\textsf{aux},\textsf{id}) \}_{x\in \mathcal {L}, \textsf{aux}\in \{0,1\}^*,\textsf{id}\in \{0,1\}^m}\) are computationally indistinguishable, where \(\textsf{Sim}^1(x,\textsf{aux},\textsf{id})\) denotes the first output of \(\textsf{Sim}(x,\textsf{aux},\textsf{id})\).

2. 2.

   Let \(x\in \mathcal {L}\), \(\textsf{aux}\in \{0,1\}^*\), \(\textsf{id}\in \{0,1\}^{m}\) and let \((\textsf{view}, \tilde{w})\) denote the output of \(\textsf{Sim}(x, \textsf{aux},\textsf{id})\). Let \( \tilde{x}\) be the right-session instance appearing in \(\textsf{view}\) and let \(\tilde{\textsf{id}}\) be the identity used in the right session appearing in \(\textsf{view}\). If the right session is accepting and \(\textsf{id}\ne \tilde{\textsf{id}}\), then \(\tilde{w}\) is such that \(( \tilde{x}, \tilde{w}) \in {\textsf{Rel}}_\mathcal {L}\).

Remark 1

Differently from [20] that uses the definition of NMZK from [22] which in turn is based on the definition introduced by [8], we use a stronger definition named simulation extractability given in [23]. Notice that, as proved in [23, Proposition 3.6] Definition 6 implies the tag based NMZK definition of [22].

We recall here the non-malleable commitment scheme presented in [3]. This scheme consists of a three-round public-coin commitment, followed by a zero-knowledge proof to ensure that the committed phase is well formed. In the full version, we report the first phase of such a protocol, i.e., only the commitment phase, from [20], and we denote it by \(\varPi _{\textsf{BGRRV}}^{3R}=(\mathcal {C}_{\textsf{BGRRV}}^{3R}, \mathcal {R}_{\textsf{BGRRV}}^{3R})\). The commitment phase of \(\varPi _{\textsf{BGRRV}}^{3R}\) makes (black-box) use of a perfectly-binding commitment scheme \(\varPi =(\textsf{Com}, \textsf{Dec})\). In the rest of the paper we will use the following theorem proven in [12], whose key points are also proven in [3].

Theorem 1

([12]). Let \(\textsf{MIM}\) be a valid ppt MiM adversary which interacts with an honest sender in the left session with tag \(\textsf{id}\) and an honest receiver in the right session with a tag of his choice \(\tilde{\textsf{id}}\) in the execution of \(\varPi _{\textsf{BGRRV}}^{3R}\). Let \(\tau =(\texttt{cm},\tilde{\texttt{cm}},{\boldsymbol{\alpha }}, {\boldsymbol{\tilde{\alpha }}},{\boldsymbol{a}},\tilde{{\boldsymbol{a}}})\) denote the transcript (i.e., the messages generated in the left and right sessions) obtained at the end of such an interaction and \(\tilde{m}\) the message committed in the right session (i.e., the message that can be successfully opened, \(\bot \) otherwise). Let \(2\tilde{p}\) be the non-negligible probability with which \(\textsf{MIM}\) is successful according to Definition 3. Then there exists a ppt \(\textsf{Ext}\) which has oracle access to \(\textsf{MIM}\) such that:

where the probability is over the randomness of \(\textsf{Ext}\) and the one used to sample \(\tau \in \textsf{WELLF}\) (see Definition 4 for the formal definition of \(\textsf{WELLF}\)).

Remark on Theorem 1. In [12] the authors state the theorem slightly differently, requiring \(\tau \) to be the transcript for which an accepting zero-knowledge proof \(\pi \) has been provided in the left session, proving that \((\texttt{cm},{\boldsymbol{\alpha }}, {\boldsymbol{a}})\) is well formed, and also a zero-knowledge proof \(\tilde{\pi }\) is provided on the right session (again, proving that \((\tilde{\texttt{cm}},{\boldsymbol{\tilde{\alpha }}},\tilde{{\boldsymbol{a}}})\) is well-formed). In this paper, we will not use such zero-knowledge proofs and simply require the above special and partial extractor to work correctly over only those transcripts that are well formed, letting the extractor being undefined on other transcripts. When using such a theorem, we will restrict to those runs of the special and partial extractor where the transcript given as part of the input does indeed belong to \(\textsf{WELLF}\).

Remark on the Use of \(\varPi _{\textsf{BGRRV}}^{3R}\). In \(\varPi _{\textsf{BGRRV}}^{3R}\) the commitment in the first round is computed on a message that corresponds to a tuple of elements in \({\mathbb {Z}}_q\), i.e., \({\boldsymbol{m}}=(m_1,\ldots ,m_{\ell -1})\in {\mathbb {Z}}_q^{\ell -1}\). Looking ahead, in our scheme \(\varPi _\textsf{NM}\) (described in Sect. 5) we will only need to commit to a single element of \({\mathbb {Z}}_q\) (similarly to [20, Protocol 2]). Let \(m \in {\mathbb {Z}}_q\) be the message to be committed in \(\varPi _\textsf{NM}\), we can consider \({\boldsymbol{m}}=(m,m_2,\ldots ,m_{\ell -1})\), where \(m_2,\ldots ,m_{\ell -1}\) are all set to 0.

3.1 Extractable Commitment Scheme

We use the 3-round public-coin extractable commitment scheme \(\varPi _{\textsf{3Ext}}=(\mathcal {C}_\textsf{3Ext},\mathcal {R}_\textsf{3Ext})\) presented in [24, Section 4] is described in detail in the full version. \(\varPi _{\textsf{3Ext}}\) is a 3-round public-coin extractable perfectly binding commitment scheme that achieves 2-extractability. The first round of \(\varPi _{\textsf{3Ext}}\) is a non-interactive perfectly binding commitment scheme \(\textsf{Com}\). Notice that \(\textsf{Com}\) can be obtained relying only on one-way permutation (i.e., 1-1 OWF).

Notice that it is possible to rely only on OWF substituting \(\textsf{Com}\) with a statistically binding 2-round commitment scheme from OWF. In this case, the resulting protocol is a 4-round public-coin extractable statistically-binding commitment scheme that achieves 2-extractability. In the following sections, every time that we refer to a perfectly-binding non-interactive commitment scheme \(\textsf{Com}\) that relies only on 1-1 OWF it is possible to substitute it with a 2-round statistically-binding commitment scheme assuming only OWF.

In this section, we construct a 5-round extractable commitment scheme \(\varPi _\mathsf {5\textsf{Ext}}=(\mathcal {C},\mathcal {R})\) that satisfies Theorem 1 as \(\varPi _\textsf{BGRRV}^{3R}\) in Sect. 3. \(\varPi _\mathsf {5\textsf{Ext}}\) is also delayed-input (i.e., a commitment scheme where the message to be committed can be specified in the last round). We use the following building blocks:

• The 3-round 2-extractable, commitment scheme \(\varPi _{\textsf{3Ext}}\) of Sect. 3.1.

• The 3-round public-coin, commitment scheme \(\varPi _\textsf{BGRRV}^{3R}\) of [3], and \(\textsf{Ext}\) of Theorem 1. We recall \(\varPi _\textsf{BGRRV}^{3R}\) in Sect. 3, as we are going to use its components in the design of our \(\varPi _{\mathsf {5\textsf{Ext}}}\).

• A non-interactive perfect binding commitment \(\varPi _\texttt{com}=(\textsf{Com}, \textsf{Dec})\).

At a very high-level \(\varPi _{\mathsf {5\textsf{Ext}}}\), shown in Fig. 1, follows the commitment phase of \(\varPi _\textsf{BGRRV}^{3R}\) (described in Sect. 3), which in the first round takes as input a vector of \(\ell -1\) elements and commits to it (using \(\textsf{Com}\)) component-wise. Our only modification is that we commit to the first component of this vector using \(\varPi _{\textsf{3Ext}}\).

Notice that even though we give here a full description of \(\varPi _\mathsf {5\textsf{Ext}}=(\mathcal {C},\mathcal {R})\), part of it is useful in the performance analysis given in Sect. 1.3, part of it is explicitly used in our security proof and part of it is implicitly used when referring to the security proofs given in [3].

Lemma 1

\(\varPi _\mathsf {5\textsf{Ext}}\) described in Fig. 1 enjoys the 2-extractability property.

Proof

The lemma follows immediately from the 2-extractability of \(\varPi _{\textsf{3Ext}}\).

Theorem 2

\(\varPi _\mathsf {5\textsf{Ext}}\) described in Fig. 1 is a perfectly binding, computationally hiding 5-round extractable commitment scheme.

Proof

The perfect binding property of \(\varPi _\mathsf {5\textsf{Ext}}\) follows from the perfect binding property of \(\varPi _{\textsf{BGRRV}}^{3R}, \varPi _{\textsf{3Ext}}\) and \(\varPi _\texttt{com}\). The hiding property of \(\varPi _\mathsf {5\textsf{Ext}}\) follows from the hiding of \(\varPi _{\textsf{BGRRV}}^{3R}, \varPi _{\textsf{3Ext}}\) and \(\varPi _\texttt{com}\). The extractability follows from the extractability of \(\varPi _{\textsf{3Ext}}\). Indeed, we can run the extractor of \(\varPi _{\textsf{3Ext}}\) thus obtaining k, and return \(c\oplus k\) (where c is part of the last message generated by the committer).

Theorem 3

Let \(\textsf{MIM}\) be a valid ppt MiM adversary which interacts with an honest sender in the left session with tag \(\textsf{id}\) and an honest receiver in the right session with tag of his choice \(\tilde{\textsf{id}}\) in the execution of \(\varPi _\mathsf {5\textsf{Ext}}\) (Fig. 1). Let \(\tau \) denote the transcript obtained at the end of such an interaction and \(\tilde{m}\) the message committed in the right session (i.e., the message that can be successfully opened, \(\bot \) otherwise). Let \(2\tilde{p}\) be the probability with which \(\textsf{MIM}\) is successful in the indistinguishability game according to Definition 3, for some non-negligible \(\tilde{p}=\tilde{p}(\lambda )\). Then there exists a non-negligible probability \(\tilde{q}=\tilde{q}(\lambda )\) and a ppt \(\textsf{Ext}_\mathsf {5\textsf{Ext}}\) which has oracle access to \(\textsf{MIM}\) such that:

where \(\textsf{WELLF}\) is the set of well-formed transcripts, the probability is over the randomness of \(\textsf{Ext}_\mathsf {5\textsf{Ext}}\) and the ones used to sample \(\tau \in \textsf{WELLF}\) which is the set of well-formed transcripts of the commitment phase.

The high-level overview of the proof is presented in the end of Sect. 1.2, while the formal proof is given in the full version.

In this section, we describe our black-box NMZK argument system \(\varPi _\textsf{NM}\). Our construction provides an efficient transformation from any 3-round public-coin SHVZK proof of knowledge (with canonical extractor) to a 9-round (resp., 10-round) NMZK argument system only requiring access to 1-1 one-way functions (resp., one-way functions) in a black-box fashion. Efficient instantiations can be obtained in Minicrypt through AES and SHA-256 as already discussed in Sect. 1.3. The tools used in \(\varPi _\textsf{NM}\) are listed below:

1. 1.

   The 5-round public-coin 2-extractable commitment scheme \(\varPi _\mathsf {5\textsf{Ext}}=(\mathcal {C},\mathcal {R})\) of Sect. 4 which satisfies Theorem 3 and Lemma 1.

2. 2.

   A 3-round public-coin SHVZK proof of knowledge (with a canonical extractor) \(\varPi =(\mathcal {P},\mathcal {V})\) for the language \(\mathcal {L}\) and associated relation \({\textsf{Rel}}_\mathcal {L}\).

The protocol is described in Fig. 2.

Theorem 4

Given a 3-round public-coin SHVZK proof of knowledge \(\varPi =(\mathcal {P},\mathcal {V})\) with canonical extractor for an \(\mathcal {N}\mathcal {P}\) language \(\mathcal {L}\), the 5-round public-coin extractable commitment scheme \(\varPi _{\mathsf {5\textsf{Ext}}}\) of Sect. 4 (which satisfies Theorem 3 and Lemma 1), \(\varPi _\textsf{NM}\) (Fig. 2) is a simulation-extractable argument system for \(\mathcal {L}\) which makes only a black-box use of \(\varPi _{\mathsf {5\textsf{Ext}}}\) and \(\varPi \).

Proof

The completeness of \(\varPi _\textsf{NM}\) follows by inspection.

Computational simulation extractability.

The simulator \(\textsf{Sim}_\textsf{NM}\) is described in Fig. 3.

Let us consider a \(\textsf{MIM}\) that in the right session proposes an instance \(x^*\). We will prove that \(\{\textsf{Sim}_\textsf{NM}^1(x,\textsf{aux},\textsf{id}) \}_{x\in \mathcal {L},\textsf{aux}\in \{0,1\}^*,\textsf{id}\in \{0,1\}^{\varOmega (|x|)}}\) and \(\{ \textsf{view}^\textsf{MIM}(x,\textsf{aux},\textsf{id})\}_{x\in \mathcal {L},\textsf{aux}\in \{0,1\}^*,\textsf{id}\in \{0,1\}^{\varOmega (|x|)}}\) are computationally indistinguishable and only with negligible probability \(\textsf{Sim}_\textsf{NM}\) will output a transcript with an accepting right session for \(x^*\) but without a corresponding witness \(w^*\).

• \(\mathcal {H}_1\): This is equivalent to the real-world experiment among \(\mathcal {P}_\textsf{NM}\), \(\textsf{MIM}\), and \(\mathcal {V}_\textsf{NM}\), where \(\mathcal {P}_\textsf{NM}\) proves to \(\textsf{MIM}\) a statement \(x\in \mathcal {L}\) using a witness \(w\) and \(\textsf{MIM}\) proves to \(\mathcal {V}_\textsf{NM}\) that \(x^*\in \mathcal {L}\), for \(x^*\in \{0,1\}^\lambda \). If the proof of \(\textsf{MIM}\) is not accepting, the experiments terminates giving in output \((\tau ,\bot )\). If instead the proof given by \(\textsf{MIM}\) is accepting, the experiment performs the Extracting Stage described in the right session of Fig. 3 (i.e., the experiment acts as \(\textsf{Sim}_\textsf{NM}\) in the Extracting Stage). If the Extracting Stage terminates before Step 4, the experiment ends giving in output \((\bot ,\bot )\). Otherwise, the experiment ends giving in output \((\tau ,w^*)\), where \(\tau \) is the view of \(\textsf{MIM}\) in the main thread of the above execution and \(w^*\) is the extracted witness for \(x^*\).

• \(\mathcal {H}_2\): This is equal to \(\mathcal {H}_1\) except that \(\mathcal {P}_\textsf{NM}\) runs th extractor of \(\varPi _\mathsf {5\textsf{Ext}}\) in the left execution therefore, when \(\textsf{MIM}\) sends the last message of \(\varPi _\mathsf {5\textsf{Ext}}\) the experiment executes the Rewinding Stage described in the left session of Figure 3. The same (a run of the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\) that involves an execution of the Rewinding Stage) happens in case the commitment sent by \(\textsf{MIM}\) through \(\varPi _\mathsf {5\textsf{Ext}}\) changes during rewinds performed by the Extracting Stage. If the Rewinding Stage terminates with an output \(c_0^*\) and the adversary correctly opens the commitment played in the left session to a value that is different than \(c_0^*\), then the experiment ends giving in output \((\bot ,\bot )\), otherwise it continues as in \(\mathcal {H}_1\) computing the output in the same way.

• \(\mathcal {H}_3\): This is equal to \(\mathcal {H}_2\) except that in the left execution, the experiment fixes a candidate random value \(\pi ^2\) at the onset of the execution on the left session (i.e., before computing \(\pi ^1\)). Let \({c_0^*}\) be the value obtained from the Rewinding Stage of the left session. In Round 7 (after performing the Rewinding Stage) if \(c_0^*\ne \bot \) the experiment sets \(c_1=\pi ^2\oplus {c_0^*}\). The rest of the experiment proceeds as in \(\mathcal {H}_2\) computing the output in the same way.

• \(\mathcal {H}_4\): This is equal to \(\mathcal {H}_3\) except that in Round 1 of the left execution the experiment computes \((\pi ^1_h,\pi ^3_h)\leftarrow \textsf{Sim}_\varPi (x,\pi ^2_h)\) where \(\pi ^2_h\) corresponds to \(\pi ^2\) of \(\mathcal {H}_3\). The experiment sends \(\pi ^1_h\) in Round 1 and \(\pi ^3_h\) in Round 9. The rest of the experiment proceeds as in \(\mathcal {H}_3\) computing the output in the same way.

Lemma 2

\(\mathcal {H}_1\) terminates with output \((\bot ,\bot )\) only with negligible probability.

Proof

Let us assume by contradiction that Lemma 2 does not hold. This implies that the Extracting Stage terminates by giving in the output \((\bot ,\bot )\) with probability \(p\ge \frac{1}{\lambda ^c}\) for some constant c and infinitely many \(\lambda \). Notice that the Extraction Stage is invoked only when an accepting transcript has been generated. Therefore we have that the probability of getting an accepting transcript is also at least \(\frac{1}{\lambda ^c}\) and thus, by the proof of knowledge property of \(\varPi \) it follows that the canonical extractor of \(\varPi \) succeeds giving in output a witness with overwhelming probability as long as each time the right session is completed in the Extracting Stage the challenge \(\widetilde{\pi }^2\) is new. Therefore the only reason why the Extracting Stage still outputs \((\bot ,\bot )\) with probability p (contradicting the above overwhelming probability of success) is due to the fact that the Extracting Stage fails in collecting \((\widetilde{\pi }^1,\widetilde{\pi }^2,\widetilde{\pi }^3, \textsf{2R}, \textsf{3R}, x^*)\) such that the elements in \(\mathsf {\widetilde{2R}}=(\textsf{2R}+\widetilde{\pi }^2)\) are all distinct^{Footnote 7}. As a consequence, with non-negligible probability at least two elements in \(\mathsf {\widetilde{2R}}\) are identical. We can define the following event, which we call \(\textsf{Bad}\). Let \((\widetilde{\pi }^1,\widetilde{\pi }^2,\widetilde{\pi }^3)\) be the transcript obtained before starting the Extracting Stage of the right session. Then, \(\textsf{Bad}\) is defined as the event that during the Extracting Stage (and thus in the presence of a different \(\tilde{c}'_0\)), \(\textsf{MIM}\) continues the execution of the right session and provides \(\tilde{c}'_1\) such that \(\tilde{c}'_1 \oplus \tilde{c}'_0\) is equal to \(\widetilde{\pi }^2\). Since with non-negligible probability at least two elements in \(\mathsf {\widetilde{2R}}\) are identical, we have that \(\textsf{Bad}\) happens with non-negligible probability. We now use this fact to show a reduction \(\textsf{A}_{\textsf{ExpHiding}}\) to the hiding of \(\varPi _\mathsf {5\textsf{Ext}}\), therefore reaching a contradiction. Let \(\textsf{C}_{\textsf{ExpHiding}}\) be the corresponding challenger.

\(\textsf{A}_{\textsf{ExpHiding}}\) interacts with \(\textsf{MIM}\) acting exactly as in hybrid \(\mathcal {H}_1\). Upon receiving \(\widetilde{\pi }^2\) from the right session \(\textsf{A}_{\textsf{ExpHiding}}\) rewinds \(\textsf{MIM}\) at the onset of Round 2 in the right session of \(\varPi _\textsf{NM}\) and continues the execution as follows.

In the right session of \(\varPi _\textsf{NM}\), \(\textsf{A}_{\textsf{ExpHiding}}\) received a value \(\widetilde{\pi }^1\) from \(\textsf{MIM}\) and then \(\textsf{A}_{\textsf{ExpHiding}}\) chooses two random values (\(\tilde{c}'_0\), \(\tilde{c}_0\)) and sends them to \(\textsf{C}_{\textsf{ExpHiding}}\). At this point \(\textsf{A}_{\textsf{ExpHiding}}\) will act as a proxy between \(\textsf{C}_{\textsf{ExpHiding}}\) and \(\textsf{MIM}\) for the messages of \(\varPi _\mathsf {5\textsf{Ext}}\) and continuing the rest of the experiment as before, until \(\textsf{MIM}\) sends \(\tilde{c}_1\) in the right session. At this point, \(\textsf{A}_{\textsf{ExpHiding}}\) checks if \(\widetilde{\pi }^2=\tilde{c}_0 \oplus \tilde{c}_1\), and in this case \(\textsf{A}_{\textsf{ExpHiding}}\) sends \(b=0\) to \(\textsf{C}_{\textsf{ExpHiding}}\). If \(\widetilde{\pi }^2=\tilde{c}'_0 \oplus \tilde{c}_1\) \(\textsf{A}_{\textsf{ExpHiding}}\) sends \(b=1\). Otherwise \(\textsf{A}_{\textsf{ExpHiding}}\) sends a random bit.

Since we are assuming that \(\textsf{Bad}\) happens with non-negligible probability then, by noticing that the value among \(\tilde{c}'_0\) and \(\tilde{c}_0\) that is not committed by \(\textsf{C}_{\textsf{ExpHiding}}\) is information theoretically hidden, we have that \(\textsf{A}_{\textsf{ExpHiding}}\) returns the bit b chosen by \(\textsf{C}_{\textsf{ExpHiding}}\) with probability \(\frac{1}{2}+\widetilde{p}\) where \(\widetilde{p}\) is non-negligible. This contradicts the hiding of \(\varPi _\mathsf {5\textsf{Ext}}\).

Finally notice that we did not make any restriction on the scheduling of messages of the right and left sessions.

Lemma 3

\(\mathcal {H}_2\) is statistically indistinguishable from \(\mathcal {H}_1\).

Proof

\(\mathcal {H}_2\) and \(\mathcal {H}_1\) are statistically indistinguishable for the following reasons. First of all, the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\) produces a perfectly indistinguishable transcript of \(\varPi _\mathsf {5\textsf{Ext}}\). There can be an additional impact on the output of the experiment depending on the value extracted by the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\) and we distinguish the following cases. In the first case, the message committed in the left session is invalid and the extractor outputs a valid message (due to over-extraction). Notice that an invalid commitment does not admit a valid opening, and thus this case corresponds in both hybrids to the left session that reaches at most the (invalid) opening of the commitment, therefore producing no deviation in the two distributions. The second case, concerns the fact that the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\) outputs a legitimate message that could be different from the one actually opened by the adversary in the left session. While this makes a deviation among the two hybrids, by the statistical binding of \(\varPi _\mathsf {5\textsf{Ext}}\) this can happen only with negligible probability. The third case refers to the extractor giving in output \(\bot \) while instead the commitment admits a correct opening, therefore producing again a gap in the outputs of the two hybrids. However this failure in the extraction can happen by Definition 1 only with negligible probability.

Finally, when the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\) outputs the same message that is then opened by the adversary, the two hybrids produce identically distributed outputs. Also during the Extracting Stage the messages played in \(\mathcal {H}_2\) are identically distributed to the ones of \(\mathcal {H}_1\). More formally, as shown in the proof of Lemma 2 a failure in extracting a witness implies that the event \(\textsf{Bad}\) happens with non-negligible probability. The very same reduction shown in Lemma 2 can be repeated here, running \(\textsf{A}_{\textsf{ExpHiding}}\) once the transcripts of the right session is completed, without running the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\) when the challenger \(\textsf{C}_{\textsf{ExpHiding}}\) is involved. Therefore we can conclude that the outputs of the two hybrids are statistically indistinguishable.

We stress that the claim holds regardless of the scheduling of the left execution and right execution. Indeed, note that the Extracting Stage consists of playing messages that are identically distributed with respect to the ones of an honest verifier. Similarly, the Rewinding Stage consists of playing messages that are identically distributed with respect to the ones of an honest receiver. Moreover, each Stage fails only with negligible probability, and repeating it polynomially many times (as it could be required because of rewinds performed by the other stage) still leaves negligible the probability of a failure. Therefore, any possible interleaving of messages between left and right sessions, does not noticeably affect the success probabilities of the extractor of \(\varPi \) and the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\).

Lemma 4

\(\mathcal {H}_3\) is computationally indistinguishable from \(\mathcal {H}_2\).

Proof

The first output of \(\mathcal {H}_3\) is identical to the one of \(\mathcal {H}_2\) since selecting \(\pi ^2\) randomly in advance to then establish \(c_1=\pi ^2 \oplus c_0\) is equivalent to randomly selecting \(c_1\) and then computing \(\pi ^2\). We now focus on the second value in the output of the experiment. We consider again the event \(\textsf{Bad}\) that corresponds to a failure in computing a witness for the accepting transcript appearing in the right session. Showing that \(\textsf{Bad}\) happens with negligible probability would conclude the proof of this Lemma. Notice that the only difference between \(\mathcal {H}_3\) and \(\mathcal {H}_2\) is that in the left session of \(\mathcal {H}_3\) the experiment sets a specific value, namely \(\pi ^2\), as a challenge for \(\varPi \). If the event \(\textsf{Bad}\) happens in \(\mathcal {H}_3\) with non-negligible probability then it must be the case that \(\textsf{MIM}\) manages to force a value \(\widetilde{\pi ^2}\) on the right session that will appear again during the Extracting Stage. We will contradict the hiding of \(\varPi _\mathsf {5\textsf{Ext}}\), using the fact that \(\varPi _\mathsf {5\textsf{Ext}}\) satisfies Theorem 3.

Let \(\pi ^2\) be the challenge message of \(\varPi \) for the left session, which is computed as described in \(\mathcal {H}_3\).

Suppose that \(\textsf{Bad}\) happens with non-negligible probability \(\widetilde{p}\). Let \(\widetilde{\pi ^2}\) be the value that has non-negligible probability^{Footnote 8} to appear again in the right session during the Extracting Stage when \(\pi ^2\) is forced on the left session and \(\widetilde{\pi ^1}\) is fixed.

We split now the proof into two sub-cases based on the schedule of the messages of \(\textsf{MIM}\): schedule of type (1) in which \(\textsf{MIM}\) plays Round 7 (i.e., message \(\tilde{c}_1\)) after the commitment phase is terminated in the left session; schedule of type (2) in which \(\textsf{MIM}\) plays Round 7 (i.e., message \(\tilde{c}_1\)) before the commitment phase is terminated in the left session. Notice that when the event \(\textsf{Bad}\) happens the schedule must be either of type (1) or type (2).

We proceed now proving that for both types of schedules, the hypothesis that \(\textsf{Bad}\) verifies with non-negligible probability leads to a contradiction.

Case 1: all schedules of type (1). If \(\textsf{Bad}\) happens with non-negligible probability \(\widetilde{p}\) with schedules of type (1) our first goal is to show a successful man-in-the-middle adversary \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) and a corresponding distinguisher \(\textsf{D}_{\mathsf {5\textsf{Ext}}}\) for \(\varPi _\mathsf {5\textsf{Ext}}\). Then we will use them to reach a contradiction to the hiding of \(\varPi _\mathsf {5\textsf{Ext}}\).

More in detail, we define the man-in-the-middle \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) which plays as a receiver in the left session interacting with an honest sender \(\mathcal {C}_\mathsf {5\textsf{Ext}}\) committing either to^{Footnote 9} a message \(m_0\) or to a message \(m_1\) and as a sender in the right session of \(\varPi _\mathsf {5\textsf{Ext}}\) against an honest receiver \(\mathcal {R}_\mathsf {5\textsf{Ext}}\).

When playing as a receiver, therefore getting messages from \(\mathcal {C}_\mathsf {5\textsf{Ext}}\), in the left session of \(\varPi _\mathsf {5\textsf{Ext}}\), \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) internally runs \(\textsf{MIM}\) in a right session of \(\varPi _\textsf{NM}\) where \(\textsf{MIM}\) plays the role of a prover and \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) plays the role of a verifier. Therefore in the right session of \(\varPi _\textsf{NM}\), \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) playing the subprotocol \(\varPi _\mathsf {5\textsf{Ext}}\) as a sender will forward the messages of \(\mathcal {C}_\mathsf {5\textsf{Ext}}\) to \(\textsf{MIM}\). In the internal execution of \(\varPi _\textsf{NM}\) we have a left session where \(\textsf{MIM}\) will be a sender in the subprotocol \(\varPi _\mathsf {5\textsf{Ext}}\), and \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) will be a receiver. The messages of the subprotocol \(\varPi _\mathsf {5\textsf{Ext}}\) that \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) will receive in this left session of the internal execution of \(\varPi _\textsf{NM}\) will be forwarded to the honest receiver \(\mathcal {R}_\mathsf {5\textsf{Ext}}\) playing in the right session of \(\varPi _\mathsf {5\textsf{Ext}}\). Similarly, there will be a symmetric flow of messages in the opposite direction that for completeness we report now. Messages sent by \(\mathcal {R}_\mathsf {5\textsf{Ext}}\) played in the right execution of \(\varPi _\mathsf {5\textsf{Ext}}\) will be forwarded by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) to \(\textsf{MIM}\) in the left session of the internal execution of \(\varPi _\textsf{NM}\) where indeed \(\textsf{MIM}\) is a sender of the subprotocol \(\varPi _\mathsf {5\textsf{Ext}}\). In turn, \(\textsf{MIM}\) in the right session of the internal execution of \(\varPi _\textsf{NM}\) will play messages as a receiver of the subprotocol \(\varPi _\mathsf {5\textsf{Ext}}\) that \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) will receive and forward to \(\mathcal {C}_\mathsf {5\textsf{Ext}}\) in the left session of \(\varPi _\mathsf {5\textsf{Ext}}\). \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) will play \(\pi _1\) in the left session of the internal execution of \(\varPi _\textsf{NM}\) precisely as done in \(\mathcal {H}_3\). Upon finishing the commitment phases of the subprotocol \(\varPi _\mathsf {5\textsf{Ext}}\) in the left (resp., right) session of \(\varPi _\textsf{NM}\) (i.e., in the right (resp., left) session of \(\varPi _\mathsf {5\textsf{Ext}}\)) with \(\textsf{MIM}\), \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) sets \({\tau }_\mathsf {5\textsf{Ext}}=({com}_1,{com}_2,{com}_3,{com}_4,{com}_5)\) (resp., \(\widetilde{\tau }_\mathsf {5\textsf{Ext}}=(\widetilde{com}_1,\widetilde{com}_2,\widetilde{com}_3,\widetilde{com}_4,\widetilde{com}_5)\)). Then \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) terminates giving in output \(\textsf{view}_\mathsf {5\textsf{Ext}}= (m,\widetilde{\tau }_\mathsf {5\textsf{Ext}}, {\tau }_\mathsf {5\textsf{Ext}},r^*)\) where \(r^*\) is its randomness.

Notice that, by definition, \(\textsf{D}_\mathsf {5\textsf{Ext}}\) runs on input the message \(\tilde{m}\) committed by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) (i.e., the commitment generated by \(\textsf{MIM}\) while acting as a sender in the subprotocol \(\varPi _\mathsf {5\textsf{Ext}}\) in the left session of \(\varPi _\textsf{NM})\). Moreover, \(\textsf{D}_\mathsf {5\textsf{Ext}}\) takes as an input the view given in output by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) that includes the randomness \(r^*\) used by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) in the above-described execution of \(\varPi _\textsf{NM}\). Therefore, the distinguisher \(\textsf{D}_\mathsf {5\textsf{Ext}}\) that we describe now (recall that our goal is to show a successful pair \((\textsf{MIM}_\mathsf {5\textsf{Ext}},\textsf{D}_\mathsf {5\textsf{Ext}})\) in the indistinguishability game of the non-malleable commitment definition) interacts internally with \(\textsf{MIM}\), resumes the execution of \(\varPi _\textsf{NM}\) described above, and then computes and sends Round 7 of the left session of \(\varPi _\textsf{NM}\) to \(\textsf{MIM}\), namely \(c_1=\pi ^2 \oplus \tilde{m}\). \(\textsf{D}_\mathsf {5\textsf{Ext}}\) upon receiving Round 7 of the right session from \(\textsf{MIM}\) (namely, \(\tilde{c}_1\)) does the following: if \(\widetilde{\pi ^2}=m_b\oplus \tilde{c}_1\) then \(\textsf{D}_{\mathsf {5\textsf{Ext}}}\) outputs b, otherwise \(\textsf{D}_{\mathsf {5\textsf{Ext}}}\) outputs a random bit, where \(\widetilde{\pi ^2}\) is the value that was already opened by \(\textsf{MIM}\) in the right session of the main thread. \(\textsf{MIM}_{\mathsf {5\textsf{Ext}}}\) and \(\textsf{D}_{\mathsf {5\textsf{Ext}}}\) are successful according to Definition 3.

Indeed the fact that the event \(\textsf{Bad}\) happens with non-negligible probability implies that a run of the above execution of \(\textsf{MIM}_{\mathsf {5\textsf{Ext}}}\) when the honest sender commits to \(m_b\) leads with non-negligible probability to \(\textsf{D}_{\mathsf {5\textsf{Ext}}}\) giving in output 1 in addition to flipping the coin in the other cases (i.e., when the event \(\textsf{Bad}\) does not happen). This means that the output of \(\textsf{D}_{\mathsf {5\textsf{Ext}}}\) is 1 with a probability non-negligibly larger than 1/2. Instead, when the honest sender does not commit to \(m_b\) we have that \(\textsf{D}_{\mathsf {5\textsf{Ext}}}\) outputs 1 with probability non-larger than 1/2 plus some negligible function.

The existence of the above \(\textsf{MIM}_{\mathsf {5\textsf{Ext}}}\) therefore implies, as guaranteed by Theorem 3 that there exists a special and partial extractor \(\textsf{Ext}_{\mathsf {5\textsf{Ext}}}\) that given in input the transcript of the commitment phase of \(\varPi _\mathsf {5\textsf{Ext}}\) generated by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) (and with oracle access to \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\)) extracts with non-negligible probability^{Footnote 10} the message committed by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) in the right session of \(\varPi _\mathsf {5\textsf{Ext}}\), which in turn corresponds to the message committed by \(\textsf{MIM}\) in the left session of the execution of \(\varPi _\textsf{NM}\) that is run internally by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\).

We now describe the adversary \(\textsf{A}_{\textsf{ExpHiding}}\) that breaks the hiding of \(\varPi _{\mathsf {5\textsf{Ext}}}\) interacting with a challenger \(\textsf{C}_{\textsf{ExpHiding}}\).

The reduction \(\textsf{A}_{\textsf{ExpHiding}}\) internally uses \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\), \(\textsf{MIM}\) and \(\textsf{Ext}_{\mathsf {5\textsf{Ext}}}\) providing them the needed randomness. Moreover, \(\textsf{A}_{\textsf{ExpHiding}}\) has hard-coded the value \(\widetilde{\pi ^2}\) that is the value appeared in the main thread in the right session when \(\pi ^2\) is forced on the left session. As such, \(\textsf{A}_{\textsf{ExpHiding}}\) can recompute all messages of the execution of \(\varPi _\textsf{NM}\) that is played internally by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) with \(\textsf{MIM}\). \(\textsf{A}_{\textsf{ExpHiding}}\) works again considering two sessions, we will refer to them following the places where such commitments are played in the sessions of \(\varPi _\textsf{NM}\); the right session will see the challenger \(\textsf{C}_{\textsf{ExpHiding}}\) playing the role of \(\mathcal {C}_\mathsf {5\textsf{Ext}}\), while the left session is the one where \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) tries to commit to a related value that will be extracted using \(\textsf{Ext}_{\mathsf {5\textsf{Ext}}}\) without rewinding \(\textsf{C}_{\textsf{ExpHiding}}\). The reduction works as follows:

1. 1.

   \(\textsf{A}_{\textsf{ExpHiding}}\) chooses two messages \(\tilde{c}^0_0\) and \(\tilde{c}^1_0\) sampled at random from \(\{0,1\}^\lambda \) and sends them to \(\textsf{C}_{\textsf{ExpHiding}}\). \(\textsf{C}_{\textsf{ExpHiding}}\) computes \(\widetilde{com}_1\) w.r.t. \(\tilde{c}^b_0\) for some randomly chosen bit b and sends it to \(\textsf{A}_{\textsf{ExpHiding}}\). \(\textsf{A}_{\textsf{ExpHiding}}\) obtains \(\widetilde{com}_1\) from \(\textsf{C}_{\textsf{ExpHiding}}\) and sends it to \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\).

2. 2.

   Upon receiving \({com}_i\) from \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) in the left execution \(\textsf{A}_{\textsf{ExpHiding}}\) computes \({com}_{i+1}\) as an honest receiver and send it to \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\), for \( i \in \{1,3\}\).

3. 3.

   Upon receiving \(\widetilde{com}_j\) from \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) in the right execution \(\textsf{A}_{\textsf{ExpHiding}}\) asks for \(\widetilde{com}_{j+1}\) to \(\textsf{C}_{\textsf{ExpHiding}}\) and then \(\textsf{A}_{\textsf{ExpHiding}}\) forwards it to \(\textsf{MIM}\), for \(j \in \{2,4\}\).

4. 4.

   Upon finishing the commitment phase of \(\varPi _\mathsf {5\textsf{Ext}}\) in the left session, \(\textsf{A}_{\textsf{ExpHiding}}\) runs \(\textsf{Ext}_{\mathsf {5\textsf{Ext}}}\) on input the transcript \(\tau =(com_1,\ldots ,com_5)\) generated in this session, and \(\textsf{Ext}_{\mathsf {5\textsf{Ext}}}\) will get oracle access to \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\).

   At the end of this phase \(\textsf{Ext}_{\mathsf {5\textsf{Ext}}}\) outputs \(c^*_0\) (recall that with non-negligible probability it corresponds to the value committed by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) which in turn corresponds to the share for the challenge of \(\varPi \) played by \(\textsf{MIM}\) in the left execution of \(\varPi _\textsf{NM}\)).

5. 5.

   \(\textsf{A}_{\textsf{ExpHiding}}\) continues the execution of the left and right sessions of \(\varPi _\textsf{NM}\) played internally by \(\textsf{MIM}_\mathsf {5\textsf{Ext}}\) with \(\textsf{MIM}\) and that were interrupted when \(\tau \) was obtained; \(\textsf{A}_{\textsf{ExpHiding}}\) will use \(c^*_0\) as described in \(\mathcal {H}_3\) and will continue the execution of \(\varPi _\textsf{NM}\) until obtaining \(\tilde{c}_1\) from \(\textsf{MIM}\).

6. 6.

   \(\textsf{A}_{\textsf{ExpHiding}}\) checks if \(\widetilde{{\pi }^2}=\tilde{c}^0_0 \oplus \tilde{c}_1\), and if so \(\textsf{A}_{\textsf{ExpHiding}}\) outputs 0. If \(\widetilde{{\pi }^2}=\tilde{c}^1_0 \oplus \tilde{c}_1\) then \(\textsf{A}_{\textsf{ExpHiding}}\) outputs 1. Otherwise \(\textsf{A}_{\textsf{ExpHiding}}\) outputs a random bit.

Note that if the value \(c^*_0\) is correct, then it corresponds to the value extracted (through the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\)) and then used in \(\mathcal {H}_3\). Since \(\textsf{Ext}_{\mathsf {5\textsf{Ext}}}\) succeeds with non-negligible probability, we have that the above run of \(\textsf{A}_{\textsf{ExpHiding}}\) with non-negligible probability corresponds to a run of \(\mathcal {H}_3\). Since we know that in a run of \(\mathcal {H}_3\) (by contradiction) the event \(\textsf{Bad}\) happens with non-negligible probability we have that the reduction with non-negligible probability will not output a random bit, since it will correctly guess b. At the same time, we observe that the probability that the reduction will not output a random bit and will instead output the incorrect bit is negligible since the value \(\tilde{c}^{1-b}_0\) is sampled uniformly at random and is unconditionally hidden in the experiment.

From the above arguments we can conclude that \(\textsf{A}_{\textsf{ExpHiding}}\) breaks the hiding of \(\varPi _\mathsf {5\textsf{Ext}}\) with non-negligible probability and this contradicts the hypothesis that \(\textsf{Bad}\) happens with non-negligible probability in \(\mathcal {H}_3\). Therefore in \(\mathcal {H}_3\) the Extracting Stage succeeds in obtaining a witness with a probability that is negligibly close to the one of \(\mathcal {H}_2\).

Case 2: all the schedules of type (2). In this type of schedule the event \(\textsf{Bad}\) occurs with negligible probability since otherwise we can again show a reduction to the hiding of \(\varPi _\mathsf {5\textsf{Ext}}\). The reduction proceeds exactly as described in Lemma 2 and terminates after obtaining Round 7 of the right session of \(\varPi _\textsf{NM}\) which, in this case, is scheduled before the end of the commitment phase in the left session^{Footnote 11}. Therefore there is not even a need to run an extraction on the left session and thus there is no issue with respect to the challenger of the hiding property that is instead acting as a sender of the subprotocol \(\varPi _\mathsf {5\textsf{Ext}}\) played in the right session.

The above two cases cover all possible schedules and this observation concludes the proof of the indistinguishability of \(\mathcal {H}_2\) and \(\mathcal {H}_3\).

Lemma 5

\(\mathcal {H}_4\) is computationally indistinguishable from \(\mathcal {H}_3\).

Proof

Assume by contradiction that the claim does not hold, therefore there exists a distinguisher \(\textsf{D}\) which distinguishes the view produced by \(\textsf{MIM}\) in \(\mathcal {H}_3\) from the one produced in \(\mathcal {H}_4\) with non-negligible probability. We now show an adversary \(\textsf{A}_{\textsf{ExpZK}}\) for the SHVZK property of \(\varPi \).

\(\textsf{A}_{\textsf{ExpZK}}\) receives in input a transcript \((\pi ^1,\pi ^2,\pi ^3)\) from the challenger w.r.t. an instance \(x\in \mathcal {L}\). Then, the reduction proceeds as follows. \(\textsf{A}_{\textsf{ExpZK}}\) sends \(\pi ^1\) to \(\textsf{MIM}\) in the left execution of \(\varPi _\textsf{NM}\). Further, \(\textsf{A}_{\textsf{ExpZK}}\) continues the execution with \(\textsf{MIM}\) on the left execution of \(\varPi _\textsf{NM}\) and on the right execution of \(\varPi _\textsf{NM}\) following \(\mathcal {H}_4\) until Round 7. Next, in Round 7 \(\textsf{A}_{\textsf{ExpZK}}\) sets \(c_1=\pi ^2 \oplus {c_0^*}\), where \({c_0^*}\) is the value extracted in the left execution of \(\varPi _\textsf{NM}\) (specifically, \({c_0^*}\) is obtained rewinding once \(\textsf{MIM}\) from Round 5 to Round 4 of \(\varPi _\mathsf {5\textsf{Ext}}\) in the left session and sending to \(\textsf{MIM}\) a different message in Round 4 of \(\varPi _\mathsf {5\textsf{Ext}}\)^{Footnote 12}). \(\textsf{A}_{\textsf{ExpZK}}\) sends \(c_2\) to \(\textsf{MIM}\). \(\textsf{A}_{\textsf{ExpZK}}\) continues the execution with \(\textsf{MIM}\) until Round 9 in both left and right sessions. Next, in Round 9 of the left execution of \(\varPi _\textsf{NM}\), \(\textsf{A}_{\textsf{ExpZK}}\) sends to \(\textsf{MIM}\) the value \(\pi ^3\) received in input. Notice that if \((\pi ^1,\pi ^2,\pi ^3)\) is computed by the SHVZK simulator of \(\varPi \), then the execution corresponds exactly to \(\mathcal {H}_4\). If instead \((\pi ^1,\pi ^2,\pi ^3)\) is computed by the prover of \(\varPi \), then the execution corresponds exactly to \(\mathcal {H}_3\). Therefore \(\textsf{A}_{\textsf{ExpZK}}\) runs the distinguisher \(\textsf{D}\) and breaks with non-negligible probability the SHVZK of \(\varPi \).

The event \(\textsf{Bad}\) happens in \(\mathcal {H}_4\) with negligible probability, otherwise, observe that a run of \(\mathcal {H}_4\) would lead with non-negligible probability to the same \(\widetilde{\pi }^2\) appearing both in the first output of the experiment, and in the Extraction Stage. As proven in Lemma 4, the above event happens only with negligible probability in \(\mathcal {H}_3\). Therefore one can again show a reduction to the SHVZK of \(\varPi \) that follows the one just shown, except that the reduction will succeed by running the experiment until \(\widetilde{\pi }^2\) is played during the Extraction Stage. Clearly the reduction will have an advantage in distinguishing between the transcript of a SHVZK simulator of \(\varPi \) and the one of a prover of \(\varPi \). Being this reduction to the SHVZK of \(\varPi \) very similar to the previous one, we omit further details.

Finally, observe that both the proven indistinguishability of the transcripts and the negligible probability that the event \(\textsf{Bad}\) happens apply to any schedule of the left and right sessions. The observations that the distributions of the views of \(\textsf{MIM}\) in \(\mathcal {H}_3\) and \(\mathcal {H}_4\) are computationally indistinguishable, and that the probability of extracting a witness in \(\mathcal {H}_4\) is negligibly close to the one in \(\mathcal {H}_3\), conclude the proof.

\(\mathcal {H}_5\) is equal to \(\textsf{Sim}_\textsf{NM}\) that therefore produces a transcript that is computationally indistinguishable from a real transcript. Moreover, \(\textsf{Sim}_\textsf{NM}\) fails only with negligible probability in giving in output also a witness \(w^*\) for the accepting right session appearing the right session of the transcript.

Running time. The running time of \(\textsf{Sim}_\textsf{NM}\) consists of a run of the extractor of \(\varPi _\mathsf {5\textsf{Ext}}\) on the left session and a run of the extractor of \(\varPi \) in the right session to get a witness. Note that the two extraction procedures are independent and in particular, the new messages played in the Extracting Stage are identically distributed to the ones of an honest verifier. Therefore, even in case the scheduling of the messages is such that rewinds to get a witness on the right session require each time to simulate from scratch the left session (and thus to extract again from the extractable commitment in the left session), the overall expected running time remains polynomial (as discussed in [17]).

Corollary 1

Assuming the existence of OWFs (resp., 1-1 OWFs), there exists a 10-round (resp., 9-round) NMZK, which makes black-box use of OWFs (resp., 1-1 OWFs).

The corollary holds since \(\varPi _{\mathsf {5\textsf{Ext}}}\) only uses OWFs (resp., 1-1 OWFs) in a black-box fashion and \(\varPi \) can be instantiated using [15] which also uses OWFs (resp., 1-1 OWFs) in a black-box way.

The above corollary differentiates the two cases in terms of round complexity because the 1st round of \(\varPi \) could need to compute a non-interactive commitment and this requires a preliminary round in order to be instantiated with OWFs.