Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The Fiat–Shamir (FS) transformation [26] is a popularFootnote 1 technique to build efficient non-interactive zero-knowledge (NIZK) arguments and signature schemes, starting from three-round public-coin (3PC) protocols satisfying certain properties. In a 3PC protocol the prover starts by sending a commitment \(\alpha \), to which the verifier replies with a challenge \(\beta \) drawn at random from some space \(\mathcal {B}\); finally the prover sends a reply \(\gamma \) and the verifier’s verdict is computed as a predicate of the transcript \((\alpha ,\beta ,\gamma )\).

1.1 Fiat–Shamir NIZK and Signatures

We briefly review both the main applications of the FS transform below.

  • NIZK. A NIZK is a non-interactive protocol in which the prover—holding a witness w for membership of a statement x in some \( NP \)-language \( L \)—can convince the verifier—holding just x—that \(x\in L \), by sending a single message \(\pi \). NIZK should satisfy three properties. First, completeness says that an honest prover holding a valid witness (almost) always convinces an honest verifier. Second, soundness says that a malicious prover should not be able to convince the honest verifier into accepting a false statement, i.e. a statement \(x\not \in L \); we speak of arguments (resp., proofs) when the soundness requirement holds for all computationally bounded (resp., computationally unbounded) provers. Third, zero-knowledge requires that a proof does not reveal anything about the witness beyond the validity of the statement being proven.

    Apart from being a fascinating topic, NIZK have been demonstrated to be extremely useful for cryptographic applications (see, e.g., [11, 12, 22, 24, 28, 36]). NIZK require a setup assumption, typically in the form of a common reference string (CRS).

    Starting with a 3PC protocol, the FS transform makes it a NIZK by having the prover compute the verifier’s challenge as a hash of the commitment \(\alpha \) via some hash function \(\mathsf {H}\) (with “hash key” \(\mathsf {hk}\)); this results in a single message \(\pi = (\alpha ,\beta ,\gamma )\), where \(\beta = \mathsf {H}(\mathsf {hk},\alpha )\), that is sent from the prover to the verifier.Footnote 2 (The description of the hash function, i.e. key \(\mathsf {hk}\), is included as part of the CRS.)

  • Signatures. Digital signatures are among the most important and well-studied cryptographic tools. Signature schemes allow a signer (holding a public/secret key pair \((\mathsf {pk},\mathsf {sk})\)) to generate a signature \(\sigma \) on a message m, in such a way that anyone possessing the public key \(\mathsf {pk}\) can verify the validity of \((m,\sigma )\). Signatures must be unforgeable, meaning that it should be hard to forge a signature on a “fresh” chosen message (even after seeing polynomially many signatures on possibly chosen messages).

    Starting with a 3PC protocol, the FS transform makes it a signature by having the signer compute the verifier’s challenge as a hash of the commitment \(\alpha \), concatenated with the message m, via some hash function \(\mathsf {H}\) (with “hash key” \(\mathsf {hk}\)); this results in a signature \(\sigma = (\alpha ,\beta ,\gamma )\), where \(\beta = \mathsf {H}(\mathsf {hk},\alpha ||m)\).

1.2 Positive and Negative Results

We refer to the non-interactive system obtained by applying the FS transform to a 3PC protocol (i.e., a NIZK or a signature scheme) as the FS collapse. A fundamental question in cryptography is to understand what properties the initial 3PC protocol and the hash function should satisfy in order for the FS collapse to be a NIZK argument or a secure signature scheme. This question has been studied extensively in the literature; we briefly review the current state of affairs below.

Positive Results. All security proofs for the FS transform follow the random oracle methodology (ROM) of Bellare and Rogaway [4], i.e., they assume that the function \(\mathsf {H}\) behaves like an external random function accessible to all parties (including the adversary). In particular, a series of papers [1, 26, 40, 42] establishes that the FS transform yields a secure signature scheme in the ROM provided that the starting 3PC is a passively secure identification scheme. The first definition of NIZK in the ROM dates back to [4] (where a particular protocol was analyzed); in general, it is well known that, always in the ROM, the FS transform yields a NIZK satisfying sophisticated properties such as simulation-soundness [25] and simulation-extractability [6].

Barak et al. [3] put forward a new hash function property (called entropy preservationFootnote 3) that allows to prove soundness of the FS collapse without random oracles; their result requires that the starting 3PC protocol is statistically sound, i.e. it is a proof. Dodis et al. [21] show that such hash functions exist if a conjecture on the existence of certain “condensers for leaky sources” turns out to be true. Canetti et al. [13] study the correlation intractability of obfuscated pseudorandom functions and show a close connection between entropy preservation and correlation intractability, but it remains open whether their construction achieves entropy preservation or, in fact, whether entropy-preserving hash functions exist in the standard model. A negative indication to this question was recently presented by Bitansky et al. [7] who show that entropy-preservation security cannot be proven via a black-box reduction to a cryptographic game.

Negative Results. It is often difficult to interpret what a proof in the ROM means in the standard model. This is not only because concrete hash functions seem far from behaving like random oracles, but stems from the fact that there exist cryptographic schemes that can be proven secure in the ROM, but are always insecure in the standard model [14].

The FS transformation is not an exception in this respect. In their study of “magic functions”, Dwork et al. [23] establish that whenever the initial 3PC protocol satisfies the zero-knowledge property, its FS collapse can never be (computationally) sound for any implementation of the hash function. Goldwasser and Kalai [29], building on previous work of Barak [2], construct a specially-crafted 3PC argument for which the FS transform yields an insecure signature scheme for any standard model implementation of the hash function.

Bitansky et al. [8] and Dachman-Soled et al. [18] (see also [7]) show an unprovability result that also covers 3PC proofs. More in detail, [8] shows that the FS transform cannot always preserve soundness when starting with a 3PC proof, under a black-box reduction to any falsifiable assumption (even ones with an inefficient challenger). [18] shows a similar black-box separation (although only for assumptions with an efficient challenger) for any concrete proof that is honest-verifier zero-knowledge against sub-exponential size distinguishers. In a related paper, Goyal et al. [30] obtain a negative result for non-interactive information-theoretically secure witness indistinguishable arguments.

1.3 Our Contributions

The negative results show that, for certain classes of interactive protocols, the FS transform cannot be instantiated in the standard model. We initiate the study of complementary positive results, namely, studying classes of interactive protocols where the FS transform does have a standard-model instantiation. We show that for a class of “highly sound” protocols that we define, instantiating the FS transform via a q-wise independent hash function yields both a NIZK argument in the CRS model and a secure signature scheme. In the case of NIZK, we get a weaker “q-bounded” zero-knowledge flavor where the simulator works for all adversaries asking an a-priori bounded number of queries q; in the case of signatures, we get the weaker notion of random-message unforgeability against q-bounded random message attacks, where the forger can observe signatures on random messages and has to produce a forgery on a fresh random message.

Very roughly, highly sound protocols are a special class of 3PC arguments and identification schemes satisfying three additional properties: (\(\mathbf P1 \)) The honest prover computes the commitment \(\alpha \) independently of the instance being proven and of the corresponding witness; (\(\mathbf P2 \)) The soundness error of the protocol is tiny, in particular the ratio between the soundness error and the worst-case probability of guessing a given commitment is bounded-away from one; (\(\mathbf P3 \)) Honest conversations between the prover and the verifier on common input x can be simulated knowing just x, and moreover the simulator can fake \(\alpha \) independently of x itself.

We are not aware of natural protocols that are directly highly sound according to our definition. (But we will later discuss that, e.g., the Lapidot-Shamir protocol [37] partially satisfies our requirements.) Hence, the question is whether such highly sound protocols exist and, if so, which languages and protocols lie in this class. We answer this question in the affirmative in the CRS model and under strong assumptions. Namely, assuming indistinguishability obfuscation, puncturable pseudorandom functions and equivocal commitments, we build a sequence of two compilers that transform any three-move interactive protocol with instance-independent commitments (i.e., property \(\mathbf P1 \)) into a compiled protocol in the CRS model that satisfies the required properties. Noteworthy, our compilers are language-independent, and we know that assuming one-way permutations three-move interactive protocols with instance-independent commitments exist for all of \( NP \).

Our result avoids Dwork et al. [23], because we start from a protocol that is honest-verifier zero-knowledge rather than fully zero-knowledge. Note that our approach also circumvents the negative result of [8, 30] as our technique applies only to a certain class of 3PC arguments. Furthermore, we circumvent the black-box impossibility result [18] by using complexity leveraging and sub-exponential security assumptions.

1.4 Perspective

The main contribution from our perspective is to initiate the study of restricted positive standard-model results for the FS transform. Namely, we show that for the class of highly sound protocols, the FS transform can be instantiated via a q-wise independent hash function (both for the case of NIZK and signatures). This is particularly interesting given the negative results in [7, 23, 29].

An important complementary question is, of course, to study the class of highly sound protocols. Under strong assumptions, our compilers show that highly sound protocols exist for all languages in \( NP \). However, the compilers yield protocols in the CRS model and, at least for the case of NIZK, as we discuss now, one has to take care in interpreting positive results about the FS transform applied to 3PC protocols in the CRS model.

It is well known that in the CRS model one can obtain a NIZK both for \( NP \)-complete languages [10] and for specific languages [31]. Let \( L \) be a language. Given a standard 3PC protocol for proving membership of elements \(x\in L \), and with transcripts \((\alpha , \beta , \gamma )\), consider the following dummy “compiler” for obtaining a 3PC protocol for \( L \) in the CRS model. The first message \(\alpha ^*\) and the second message \(\beta ^*\) of the compiled protocol are equal to the empty string \(\varepsilon \); the third message is a NIZK proof \(\gamma ^*\) that \(x\in L \). Note that the FS transform is easily seen to be secure (without random oracles) on such a dummy protocol, the reason for this being that \(\alpha ^*\) and \(\beta ^*\) play no role at all in the obtained 3PC! Further note that this artificial “compiler” actually ignores the original protocol, and hence it does not rely on any of the security features of the underlying protocol. Regrettably, the above example does not shed any light on the security of the FS transform and when it applies.

In turn, our result for FS NIZK has two interesting features. First, our instantiation of the FS transform works even if the starting 3PC is in the standard model (provided that it satisfies \(\mathbf P1 \)-\(\mathbf P3 \)). Second, our CRS-based compiler is very different from the above dummy compiler in that we do not simply “throw away” the initial 3PC but instead rely on all of its properties in order to obtain a 3PC satisfying \(\mathbf P1 \)-\(\mathbf P3 \).

We remark that the above limitation does not apply to our positive result for FS signatures, since assuming the initial 3PC protocol works in the CRS model does not directly yield a dummy “compiler” as the one discussed above.

1.5 Related Work

On Fiat–Shamir. It is worth mentioning that using indistinguishability obfuscation and puncturable PRFs one can directly obtain a NIZK for all \( NP \) as shown by Sahai and Waters [43]. However, our main focus is not on constructions of NIZK, rather we aim at providing a better understanding of what can be proved for the FS transform without relying on random oracles. In this respect, our result shares similarities to the standard-model instantiation of Full-Domain Hash given in [34].

In the case of NIZK, an alternative version of the FS transform is defined by having the prover hashing the statement x together with value \(\alpha \), in order to obtain the challenge \(\beta \). The latter variant is sometimes called the strong FS transform (while the variant we analyze is known as the weak FS transform). Bernhard et al. [6] show that the weak FS transform might lead to problems in certain applications where the statement to be proven can be chosen adversarially (this is the case, e.g., in the Helios voting protocol). Unfortunately, it seems hard to use our proof techniques to prove zero-knowledge of the strong FS collapse, because the simulator for zero-knowledge does not know the x values in advance.

Our positive result for FS signatures shares some similarities with the work of Bellare and Shoup [5], showing that “actively secure” 3PC protocols yield a restricted type of secure signature schemes (so-called two-tier signatures) when instantiating the hash function in the FS transform via any collision-resistant hash function.

Compilers. Our approach of first compiling any “standard” 3PC protocol into one with additional properties that suffice for proving security of the FS transform is similar in spirit to the approach taken by Haitner [32] who shows how to transform any interactive argument into one for which parallel repetition decreases the soundness error at an exponential rate.

Lindell recently used a similar idea to first transform a 3PC into a new protocol in the CRS model, and then show that the resulting 3PC when transformed with (a slightly modified version of) Fiat–Shamir satisfies zero-knowledge in the standard model [38]. His approach was later improved in [17]. We note that the use of a CRS-enhanced interactive protocol is only implicit in Lindell’s work as he directly analyzes the collapsed non-interactive version. On the downside, to prove soundness Lindell still requires (non-programmable) random oracles. We note that one of our compilers is essentially equivalent to the compiler used by Lindell. Before Lindell’s work, interactive protocols in the CRS model have also been studied by Damgård who shows how to build 3-round concurrent zero-knowledge arguments for all \( NP \)-problems in the CRS model [20].

Alternative Transforms. Other FS-inspired transformations were considered in the literature. For instance Fischlin’s transformation [27] (see also [19]) yields a simulation-sound NIZK argument with an online extractor; as mentioned above, Lindell [38] defines a twist of the FS transform that allows to prove zero-knowledge in the CRS model, and soundness in the non-programmable random oracle model. It is an interesting direction for future research to apply our techniques to analyze the above transformations without random oracles.

Concurrent Paper. Recently, in a concurrent and independent work, Kalai, Rothblum and Rothblum [35] showed a positive result for FS in the plain model, under complexity assumptions similar to ours. More in details, assuming sub-exponentially secure indistinguishability obfuscation, input-hiding obfuscation for the class of multi-bit point functions, and sub-exponentially secure one-way functions, [35] shows that, when starting with any 3PC proof, the FS transform yields a two-round computationally-sound interactive protocol.

On the positive side, their result applies to any 3PC proof (while ours only covers a very special class of 3PC arguments). On the negative side, their technique only yields a positive result for a two-round interactive variant of the FS transform (while our techniques apply to the full FS collapse, both for NIZK and for signatures).

1.6 Roadmap

Section 2 contains a detailed informal overview of our positive result for the case of FS NIZK; the corresponding formal definitions and proofs are deferred to the full version [39]. We present an overview of our compilers for obtaining highly sound protocols (in the CRS model) in Sect. 3; a more detailed treatment appears in the full paper [39], where we also explain how to adapt our techniques to the case of FS signatures.

Fig. 1.
figure 1

Message flow of a typical 3PC argument system and its corresponding FS collapse.

Full size image

2 FS NIZK

Fiat–Shamir Transform. The Fiat–Shamir (FS) transform [26] is a generic way to remove interaction from certain argument systems, using a hash function. For the rest of the paper, we consider only interactive arguments consisting of three messages—which we denote by \((\alpha ,\beta ,\gamma )\)—where the first message is sent by the prover. We also focus on so-called public-coin protocols where the verifier’s message \(\beta \) is uniformly random over some space \(\mathcal {B}\) (e.g., \(\beta \in \{0,1\}^k\) for some \(k\in \mathbb {N}\)). We call this a 3PC argument system for short, and denote it by \(\varPi = (\mathsf {K},\mathsf {P},\mathsf {V})\); here \(\mathsf {K}\) generates a CRS \(\mathsf {crs}\),Footnote 4 whereas \(\mathsf {P}\) and \(\mathsf {V}\) correspond to the prover and verifier algorithms.

For 3PC arguments we can think of the prover algorithm as being split into two sub-algorithms \(\mathsf {P}:= (\mathsf {P}_0,\mathsf {P}_1)\), where \(\mathsf {P}_0\) takes as input a pair (x, w) and outputs the prover’s first message \(\alpha \) (the so-called commitment) and \(\mathsf {P}_1\) takes as input (x, w) as well as the verifier’s challenge \(\beta \) to produce the prover’s second message \(\gamma \) (the so-called response). In general \(\mathsf {P}_0\) and \(\mathsf {P}_1\) are allowed to share the same random tape, which we denote by \(r\in \{0,1\}^*\). In a similar fashion we can think of the verifier’s algorithm as split into two sub-algorithms \(\mathsf {V}= (\mathsf {V}_0,\mathsf {V}_1)\), where \(\mathsf {V}_0\) outputs a uniformly random value \(\beta \in \mathcal {B}\) and \(\mathsf {V}_1\) is deterministic and corresponds to the verifier’s verdict (i.e., \(\mathsf {V}_1\) takes as input x and a transcript \((\alpha ,\beta ,\gamma )\) and returns a decision bit \(d\in \{0,1\}\)).

The FS transform allows to remove interaction from any 3PC argument system for a polynomial-time computable relation \( R \) as specified below (see also Fig. 1). Let \(\varPi = (\mathsf {K},\mathsf {P},\mathsf {V})\) be the initial 3PC argument system. Additionally, consider a family of hash functions \(\mathsf {H}\) consisting of algorithms \(\mathsf {H}.\mathsf {KGen}\), \(\mathsf {H}.\mathsf {kl}\), \(\mathsf {H}.\mathsf {Eval}\), \(\mathsf {H}.\mathsf {il}\) and \(\mathsf {H}.\mathsf {ol}\); here \(\mathsf {H}.\mathsf {il}\) and \(\mathsf {H}.\mathsf {ol}\) correspond, respectively, to the bit lengths of messages \(\alpha \) and \(\beta \) (as a function of the security parameter \(\lambda \)).

The FS collapse of \(\varPi \) using \(\mathsf {H}\) is a triple of algorithms \(\overline{\varPi }_{\mathrm {FS},\mathsf {H}}:= (\mathsf {K}_\mathrm {FS},\mathsf {P}_\mathrm {FS},\mathsf {V}_\mathrm {FS})\):

  • Algorithm \(\mathsf {K}_\mathrm {FS}\) takes as input the security parameter, samples , , and publishes \(\overline{\mathsf {crs}}:= (\mathsf {crs},\mathsf {hk})\).

  • Algorithm \(\mathsf {P}_\mathrm {FS}\) takes as input \((\overline{\mathsf {crs}},x,w)\) and runs \(\mathsf {P}_0(\mathsf {crs},x,w)\) in order to obtain the commitment \(\alpha \in \{0,1\}^{\mathsf {H}.\mathsf {il}(\lambda )}\); next \(\mathsf {P}_\mathrm {FS}\) defines the challenge as \(\beta := \mathsf {H}.\mathsf {Eval}(\mathsf {hk},\alpha )\) and runs \(\mathsf {P}_1(\mathsf {crs},x,w,\beta )\) in order to obtain the response \(\gamma \). Finally \(\mathsf {P}_\mathrm {FS}\) outputs \(\pi := (\alpha ,\gamma )\).

  • Algorithm \(\mathsf {V}_\mathrm {FS}\) takes as input \((\overline{\mathsf {crs}},x,\pi )\) and returns 1 if and only if verifier \(\mathsf {V}_1(\mathsf {crs},x,(\alpha ,\beta ,\gamma )) = 1\) where \(\beta = \mathsf {H}.\mathsf {Eval}(\mathsf {hk},\alpha )\).

Briefly, the result of Fiat and Shamir says that if \(\varPi \) is a (standard-model) 3PC argument satisfying completeness, computational soundness, and computational honest-verifier zero-knowledge (in addition to a basic requirement on the min-entropy of the prover’s commitment), its FS collapse \(\overline{\varPi }_{\mathrm {FS},\mathsf {H}}\) is a NIZK argument system if \(\mathsf {H}\) is modeled as a random oracle.

Our standard-model security proof proceeds in two modular steps. In the first step, we prove completeness and soundness of a “selective” variant of the FS transform; in the second step we analyze the standard FS transform using complexity leveraging. Details follow.

The Selective FS Transform. Consider a 3PC argument for a language \( L \). For a hash family \(\mathsf {H}\), consider the following (interactive) selective adaptation of the FS transformation: The prover sends the commitment \(\alpha \) as in the original protocol; the verifier, instead of sending the challenge \(\beta \in \mathcal {B}\) directly, forwards a honestly generated hash key \(\mathsf {hk}\); finally the prover uses \((\mathsf {hk},\alpha )\) to compute \(\beta = \mathsf {H}(\mathsf {hk},\alpha )\) and then obtains the response \(\gamma \) as in the original 3PC argument.

In the full paper [39] we prove that if the starting 3PC protocol has instance-independent commitments, is complete and computationally sound, so is the one obtained by applying the selective FS transform. The idea is to use a “programmable” q-wise independent hash function (e.g., a random polynomial of degree \(q - 1\) over a finite field) to “program” the hash function up-front; note that commitment \(\alpha \) is computed before the hash key is generated and hence, we can embed the challenge value \(\beta \) into the hash function such that it maps \(\alpha \) to \(\beta \) and reduce to the soundness of the underlying 3PC argument.

Complexity Leveraging. The second step in proving soundness of the FS collapse (we discuss zero-knowledge below) consists in applying complexity leveraging so that we can swap the order of \(\alpha \) and \(\beta \). Hence, this step can only be applied to protocols satisfying an additional property as we discuss next.

Let \(\varPi \) be the initial 3PC argument, and denote by \(\overline{\varPi }\) its corresponding FS collapse. Given a malicious prover \(\mathsf {P}^*\) breaking soundness of \(\overline{\varPi }\), we construct a prover \(\mathsf {P}\) attacking soundness of the selective FS transform as follows. \(\mathsf {P}\) picks a random \(\alpha \) from the space of all possible commitments, and forwards \(\alpha \) to the verifier; after receiving the challenge hash key \(\mathsf {hk}\), prover \(\mathsf {P}\) runs \(\mathsf {P}^*\) which outputs a proof \((\alpha ^*,\gamma ^*)\). Prover \(\mathsf {P}\) simply hopes that \(\alpha ^* = \alpha \), in which case it forwards \(\gamma ^*\) to the verifier (otherwise it aborts). It follows that if the selective FS has soundness roughly \(s(\lambda )\) (for security parameter \(\lambda \)), the soundness of \(\overline{\varPi }\) is roughly \(s(\lambda )\) divided by the probability of guessing correctly the value \(\alpha ^*\) in the first step of the reduction.

Note that for the above argument to give a meaningful bound, we need that the soundness of \(\overline{\varPi }\) is bounded away from one. This leads to the following (non-standard) requirement that the initial 3PC argument should satisfy.

P2: \(\varrho (\lambda ) := s(\lambda )/2^{-a(\lambda )} < 1\), where \(s(\lambda )\) is the soundness error and \(a(\lambda )\) is the maximum bit-length associated to the commitment \(\alpha \).

Zero-Knowledge. We assume that the initial 3PC is honest-verifier zero-knowledge (HVZK)—i.e., that it is zero-knowledge for honest verifiers. We need to show that \(\overline{\varPi }\) satisfies zero-knowledge. Here, we require two additional properties as explained below; interactive protocols obeying the first property already appeared in the literature under the name of “input-delayed” protocols [15, 16, 33].

P1: The value \(\alpha \) output by the prover is computed independently of the instance x being proven (and of the corresponding witness w).

P3: The value \(\alpha \) output by the simulator is computed independently of the instance x being proven.

We now discuss the reduction for the zero-knowledge property and explain where \(\mathbf P1 \) and \(\mathbf P3 \) are used. We need to construct an efficient simulator that is able to simulate arguments for adaptively chosen (true) statements—without knowing a witness for such statements. The output of the simulator should result in a distribution that is computationally indistinguishable from the distribution generated by the real prover. The simulator gets extra power, as it can produce a “fake” CRS together with some trapdoor information \(\mathsf {tk}\) (on which the simulator can rely) such that the “fake” CRS is indistinguishable from a real CRS.

In order to build some intuition, it is perhaps useful to recall the random-oracle-based proof for the zero-knowledge property of the FS transform. There, values \(\alpha _i\) and \(\beta _i\) corresponding to the i-th adversarial query are computed by running the HVZK simulator and are later “matched” relying on the programmability of the random oracle. Roughly speaking, in our standard-model proof we take a similar approach, but we cannot use adaptive programming of the hash function. Instead, we rely on \(\mathbf P1 \) and \(\mathbf P3 \) to program the hash function in advance. More specifically, the trapdoor information will consist of q random tapes \(r_i\) (one for simulating each proof queried by the adversary) and the corresponding q challenges \(\beta _i\) (that can be pre-computed as a function of \(r_i\), relying on \(\mathbf P1 \)). Since the challenges have the correct distribution, we can use the underlying HVZK simulator to simulate the proofs; here is where we need \(\mathbf P3 \), as the simulator has to pre-compute the values \(\alpha _i\) in order to embed the \(\beta _i\) values on the correct points.

A caveat is that our simulator needs to know the value of q in advance; for this reason we only get a weaker bounded flavor of the zero-knowledge property where there exists a “universal” simulator that works for all adversaries asking q queries, for some a-priori fixed value of q. Note, however, that the CRS—as it contains the description of a q-wise independent hash function—needs to grow with q, and hence bound q should be seen as a parameter of the construction rather than a parameter of the simulator.

It is an interesting open problem whether this limitation can be removed, thus proving that actually our transformation achieves unbounded zero-knowledge.

Putting it Together. We will call 3PC arguments satisfying properties \(\mathbf P1 \)-\(\mathbf P3 \) above (besides completeness and soundness) highly sound 3PC arguments. The theorem below summarizes the above discussion. Its proof is deferred to the full version [39].

Theorem 1

Let \(\varPi = (\mathsf {K},\mathsf {P},\mathsf {V})\) be a highly sound 3PC argument system for an \( NP \) language \( L \), and \(\mathsf {H}\) be a programmable q-wise independent hash function. Then, the FS collapse \(\overline{\varPi }_{\mathrm {FS},\mathsf {H}}\) of \(\varPi \) using \(\mathsf {H}\) yields a q-bounded NIZK argument system for \( L \).

3 Compilers

It remains to construct a highly sound 3PC argument, and to understand which languages admit such arguments. Unfortunately we do not know of a natural highly sound 3PC argument. However, we do know of protocols that partially satisfy our requirements. For instance the classical 3PC argument for quadratic residuosity due to Blum [9] satisfies \(\mathbf P1 \), and moreover can be shown to achieve completeness, soundness, and HVZK, but it does not directly meet \(\mathbf P2 \) and \(\mathbf P3 \). Another interesting example is given by the Lapidot-Shamir protocol for the \( NP \)-complete problem of graph Hamiltonicity [37] (see also [41, Appendix B]). Here, the prover’s commitment consists of a (statistically binding) commitment to the adjacency matrix of a random k-vertex cycle, where k is the size of the Hamiltonian cycle.Footnote 5 Hence, the protocol clearly satisfies \(\mathbf P1 \). Additionally the simulator fakes the prover’s commitment by either committing to a random k-vertex cycle, or by committing to the empty graph. Hence, the protocol also satisfies \(\mathbf P3 \). As a corollary, we know that assuming non-interactive statistically binding commitment schemes (which follow from one-way permutations [9]), for all languages in \( NP \), there exist 3PC protocols that satisfy completeness, computational soundness, and HVZK, as well as \(\mathbf P1 \) and \(\mathbf P3 \).

Motivated by the above examples, we turn to the question whether it is possible to compile a 3PC protocol (with completeness, soundness, and HVZK) satisfying either \(\mathbf P1 \) or \(\mathbf P1 \) and \(\mathbf P3 \), into a highly sound argument. Our compilers rely on several cryptographic tools (including indistinguishability obfuscation, puncturable PRFs, complexity leveraging and equivocal commitment schemes), and yield a 3PC in the CRS model; note that this means that we obtain an interactive protocol with a CRS even if the original protocol was in the standard model. It is an intriguing open problem if a highly sound argument can be constructed in the standard model, or whether a CRS is, in fact, necessary.

3.1 First Compiler

We present a compiler that turns a 3PC argument (possibly in the CRS model) with instance-independent commitments and HVZK (i.e., properties \(\mathbf P1 \) and \(\mathbf P3 \)) into a 3PC argument which has the soundness-error-to-guessing ratio (i.e., property \(\mathbf P2 \)) needed for the complexity leveraging in our positive result for FS NIZK. The idea for the compiler is to provide a mechanism that allows to produce many challenges \(\beta \) given only a single commitment \(\alpha \). To this effect the CRS will contain two obfuscated circuits to help the prover and the verifier run the protocol. For obfuscation we use an indistinguishability obfuscator. The first circuit \(C_0\) is used by the prover to generate a pre-commitment \(\alpha ^*\) which it sends over to the verifier. The verifier will then use the second circuit \(C_1\) and run it on \(\alpha ^*\) to obtain multiple commitments. For this \(C_1[\mathsf {k},\mathsf {crs}]\) has a PRF key (for function \(\mathsf {F}\)) and the \(\mathsf {crs}\) for algorithm \(\mathsf {P}_0\) of the underlying protocol hardcoded, and computes \(\ell \) commitments as follows:

figure a

Using \(C_1\) the compiled verifier \(\mathsf {V}^*\) can generate \(\ell \) real commitments \(\varvec{\alpha }[1]\) to \(\varvec{\alpha }[\ell ]\) given the single (short) pre-commitment \(\alpha ^*\). The verifier will then run the underlying verifier \(\mathsf {V}\) on all these commitments to receive \(\beta _1, \ldots , \beta _\ell \) which it sends back to the prover.

In order to correctly continue the prover’s computation (which was started on the verifier’s side) the compiled prover \(\mathsf {P}^*\) needs to somehow obtain the randomnesses \(r^*\) used within \(C_1\). For this, we will build a backdoor into \(C_1\) which allows to obtain the randomness \(r^*\) if one knows the randomness that was used to generate \(\alpha ^*\). Once the prover has recovered randomnesses \(r^*_1,\ldots ,r^*_\ell \) it can run the underlying prover \(\mathsf {P}\) on this randomness and the corresponding challenges \(\beta _i\) to get correct values \(\gamma _i\) which it sends back to the verifier. In a final step verifier \(\mathsf {V}^*\) runs the original verifier on the implicit transcripts \((\alpha _i,\beta _i,\gamma _i)_{i=1,\ldots ,\ell }\) and returns 1 if and only if the original verifier returns 1 on all the transcripts.

Compiler Description. Let \(\varPi = (\mathsf {K}, \mathsf {P}, \mathsf {V})\) be a 3PC argument system where the prover generates instance-independent commitments and that satisfies instance-independent HVZK. Let \(\mathsf {rl}\) denote an upper bound on the randomness used by the prover (i.e., \(\mathsf {P}.\mathsf {rl}\)) and HVZK simulator (i.e., \(\mathcal {S}.\mathsf {rl}\)). Let \(\mathsf {F}_1\) be a puncturable pseudorandom function which is length doubling. Let \(\mathsf {F}_2\) be a puncturable pseudorandom function with \(\mathsf {F}_2.\mathsf {il}= \mathsf {F}_1.\mathsf {ol}\) and with \(\mathsf {F}_2.\mathsf {ol}= \mathsf {rl}\). Let \(\ell \) be a polynomial. We construct an argument system \(\varPi ^* = (\mathsf {K}^*,\mathsf {P}^*,\mathsf {V}^*)\) in the CRS model as follows. On input the security parameter \(\mathsf {K}^*\) will construct an obfuscation of the following two circuits:

figure b

Note that we assume that the underlying protocol is in the CRS model and has a setup algorithm \(\mathsf {K}\). If this is not the case one recovers the transformation for a 3PC in the standard model by assuming that \(\mathsf {K}\) outputs the empty string \(\varepsilon \). The compiled 3PC \(\varPi ^* =(\mathsf {K}^*,\mathsf {P}^*,\mathsf {V}^*)\) is then constructed as in Fig. 2.

Fig. 2.
figure 2

The compiled protocol from Sect. 3.1 to turn a 3PC protocol into one that has a small soundness-error-to-guessing ratio (in the CRS model).

Full size image

Security Analysis. It remains to show that the compiled protocol is computationally sound, achieves (bounded) instance-independent HVZK, is complete, and that it has instance-independent commitments and a sufficient soundness-error-to-guessing ratio:

Theorem 2

Let \(\varPi = (\mathsf {K},\mathsf {P},\mathsf {V})\) be a 3PC argument system for a polynomial-time computable relation \( R \) such that \(\varPi \) is \(c\)-complete and \(s\)-sound and has instance-independent commitments and satisfies q-bounded instance-independent HVZK. Let \(\mathsf {iO}\) be an indistinguishability obfuscator and \(\mathsf {F}_1\) and \(\mathsf {F}_2\) puncturable pseudorandom functions. Let \(\ell \) be a polynomial. Then, in the CRS model, the compiled protocol \(\varPi ^*=(\mathsf {K}^*,\mathsf {P}^*,\mathsf {V}^*)\) is \((\ell \cdot c)\)-complete, \((2\cdot s^{-\ell }+2^{\mathsf {F}_1.\mathsf {ol}(\lambda )}s^{-\ell })\)-sound, has a worst-case collision probability of \(2^{-\mathsf {F}_1.\mathsf {il}(\lambda )}\), and satisfies \(q/\ell \)-bounded instance-independent HVZK. Furthermore the compiled protocol has instance-independent commitments.

The proof to the above theorem appears in the full version [39].

3.2 Second Compiler

Next, we present a compiler that turns a 3PC protocol with HVZK and instance-independent commitments (i.e., property \(\mathbf P1 \)) into a 3PC protocol in the CRS model that has instance-independent commitments and instance-independent simulators, that is, the HVZK simulator produces \(\alpha \) and \(\beta \) independently of the instance (i.e., property \(\mathbf P3 \)).

The idea is inspired by Lindell’s compiler [38]. Namely, we replace \(\alpha \) by a commitment \(\alpha ^*\) to \(\alpha \) where the deployed commitment scheme can come in one of two modes: if honestly generated the commitment will be perfectly binding thus allowing us to directly argue that the resulting compiled protocol retains soundness and completeness. On the other hand, the commitment scheme can be initialized to be equivocal (looking indistinguishably from the honest commitment setup) such that a simulator can open a commitment to arbitrary values. This way, the simulator can first commit to an arbitrary \(\alpha ^*\) and then, using the trapdoor in the CRS, it can open \(\alpha ^*\) to some arbitrary value \(\alpha \). In particular, in the reduction to the HVZK property, the verifier can choose \(\alpha ^*\) before knowing the statement that the simulator of the underlying protocol needs in order to produce \(\alpha \).

We refer the reader to the full paper [39] for a formal description of the above compiler, and for its security analysis.

4 Fiat–Shamir Signatures

Our techniques can be generalized in order to obtain a standard model instantiation of FS signatures, under similar complexity assumptions as in the case of FS NIZK. In particular it is possible to identify a certain class of so-called highly sound identification (ID) schemes, such that one can instantiate the hash function in the corresponding FS collapse via a q-wise independent hash function. As discussed in the introduction, the obtained signature scheme satisfies the weaker property of q-bounded random-message unforgeability against random-message attacks. Since the actual details of the instantiation are somewhat similar to the case of FS NIZK discussed above, we refer the reader to the full paper [39] for a more throughout discussion.