Implicit Zero-Knowledge Arguments and Applications to the Malicious Setting

Zero-Knowledge Arguments (ZK) enable a prover to prove the validity of a statement to a verifier without revealing anything else [13, 30]. In addition to being interesting in its own right, zero knowledge has found numerous applications in cryptography, most notably to simplify protocol design as in the setting of secure two-party computation [28, 29, 46], and as a tool for building cryptographic primitives with strong security guarantees such as encryption secure against chosen-ciphertext attacks [19, 41].

In this work, we focus on the use of zero-knowledge arguments as used in efficient two-party protocols for enforcing semi-honest behavior. We are particularly interested in round-efficient two-party protocols, as network latency and round-trip times can be a major efficiency bottleneck, for instance, when a user wants to securely compute on data that is outsourced to the cloud. In addition, we want to rely on standard and widely-deployed cryptographic assumptions. Here, a standard interactive zero-knowledge argument based on the \(\mathsf{DDH }\) assumption would require at least three flows; moreover, this overhead in round complexity is incurred each time we want to enforce semi-honest behavior via zero knowledge. To avoid this overhead, we could turn to non-interactive zero-knowledge proofs (\(\mathsf{NIZK }\)). However, efficient \(\mathsf{NIZK }\) would require either the use of pairings [32] and thus stronger assumptions and additional efficiency overhead, or the use of random oracles [6, 23].

We would like to point out that, contrary to some common belief, there is no straightforward way to reduce the number of rounds of zero-knowledge proofs “\(\grave{\mathrm{a}}\) la Schnorr” [42] by performing the first steps (commitment and challenges) in a preprocessing phase, so that each proof only takes one flow subsequently. Indeed, as noticed by Bernhard-Pereira-Warinsky in [9], the statement of the proof has to be chosen before seeing the challenges, unless the proof becomes unsound.

On the Importance of Round-Efficiency. In addition to being an interesting theoretical problem, improving the round efficiency is also very important in practice. If we consider a protocol between a client in Europe, and a cloud provider in the US, for example, we expect a latency of at least 100ms (and even worse if the client is connected with 3 g or via satellite, which may induce a latency of up to 1s [14]). Concretely, using Curve25519 elliptic curve of Bernstein [10] (for 128 bits of security, and 256-bit group elements) with a 10 Mbps Internet link and 100 ms latency, 100 ms corresponds to sending 1 flow, or 40,000 group elements, or computing 1,000 exponentiations at 2 GHz on one core of current AMD64 microprocessor^{Footnote 1}, hence 4,000 exponentiations on a 4-core microprocessor^{Footnote 2}. As a final remark on latency, while speed of networks keeps increasing as technology improves, latency between two (far away) places on earth is strongly limited by the speed of light: there is no hope to get a latency less than 28 ms between London and San Francisco, for example.

Our Contributions. In this work, we introduce implicit Zero-Knowledge Arguments or \(\mathsf{iZK }\) and simulation-sound variants thereof or \(\mathsf{SSiZK }\), lightweight alternatives to (simulation-sound) zero-knowledge arguments for enforcing semi-honest behavior in two-party protocols. Then, we construct efficient two-flow \(\mathsf{iZK }\) and \(\mathsf{SSiZK }\) protocols for a large class of languages under the (plain) \(\mathsf{DDH }\) assumption in cyclic groups without random oracles; this is the main technical contribution of our work. Our \(\mathsf{SSiZK }\) construction from \(\mathsf{iZK }\) is very efficient and incurs only a small additive overhead. Finally, we present several applications of \(\mathsf{iZK }\) to the design of efficient secure two-party computation, where \(\mathsf{iZK }\) can be used in place of interactive zero-knowledge arguments to obtain more round-efficient protocols.

While our \(\mathsf{iZK }\) protocols require an additional flow compared to \(\mathsf{NIZK }\), we note that eliminating the use of pairings and random oracles offers both theoretical and practical benefits. From a theoretical stand-point, the \(\mathsf{DDH }\) assumption in cyclic groups is a weaker assumption than the \(\mathsf{DDH }\)-like assumptions used in Groth-Sahai pairing-based NIZK [32], and we also avoid the theoretical pitfalls associated with instantiating the random oracle methodology [5, 16]. From a practical stand-point, we can instantiate our \(\mathsf{DDH }\)-based protocols over a larger class of groups. Concrete examples include Bernstein’s Curve25519 [10] which admit very efficient group exponentiations, but do not support an efficient pairing and are less likely to be susceptible to recent breakthroughs in discrete log attacks [4, 31]. By using more efficient groups and avoiding the use of pairing operations, we also gain notable improvements in computational efficiency over Groth-Sahai proofs. Moreover, additional efficiency improvements come from the structure of \(\mathsf{iZK }\) which makes them efficiently batchable. Conversely, Groth-Sahai \(\mathsf{NIZK }\) cannot be efficiently batched and do not admit efficient \(\mathsf{SS\hbox {-}NIZK }\) (for non-linear equations).

New Notion: Implicit Zero-Knowledge Arguments. \(\mathsf{iZK }\) is a two-party protocol executed between a prover and a verifier, at the end of which both parties should output an ephemeral key. The idea is that the key will be used to encrypt subsequent messages and to protect the privacy of a verifier against a cheating prover. Completeness states that if both parties start with a statement in the language, then both parties output the same key K. Soundness states that if the statement is outside the language, then the verifier’s ephemeral output key is hidden from the cheating prover. Note that the verifier may not learn whether his key is the same as the prover’s and would not be able to detect whether the prover is cheating, hence the soundness guarantee is implicit. This is in contrast to a standard ZK argument, where the verifier would “explicitly” abort when interacting with a cheating prover. Finally, zero-knowledge stipulates that for statements in the language, we can efficiently simulate (without the witness) the joint distribution of the transcript between an honest prover and a malicious verifier, together with the honest prover’s ephemeral output key K. Including K in the output of the simulator ensures that the malicious verifier does not gain additional knowledge about the witness when honest prover uses K in subsequent interaction, as will be the case when \(\mathsf{iZK }\) is used as part of a bigger protocol.

Enforcing semi-honest behavior of Alice (A)

Full size image

More precisely, \(\mathsf{iZK }\) are key encapsulation mechanisms in which the public key \(\mathsf {ipk}\) is associated with a word \(\mathsf {x}\) and a language \(\mathsf i \!\mathscr {L}\). In our case, \(\mathsf {x}\) is the flow^{Footnote 3} and \(\mathsf i \!\mathscr {L}\) the language of valid flows. If \(\mathsf {x}\) is in \(\mathsf i \!\mathscr {L}\), knowing a witness proving so (namely, random coins used to generate the flow) enables anyone to generate \(\mathsf {ipk}\) together with a secret key \(\mathsf {isk}\), using a key generation algorithm \({\mathsf {iKG}}\). But, if \(\mathsf {x}\) is not in \(\mathsf i \!\mathscr {L}\), there is no polynomial-time way to generate a public key \(\mathsf {ipk}\) for which it is possible to decrypt the associated ciphertexts (soundness).

To ensure semi-honest behavior, as depicted in Fig. 1, each time a player sends a flow \(\mathsf {x}\), he also sends a public key \(\mathsf {ipk}\) generated by \({\mathsf {iKG}}\) and keeps the associated secret key \(\mathsf {isk}\). To answer back, the other user generates a key encapsulation \(c\) for \(\mathsf {ipk}\) and \(\mathsf {x}\), of a random ephemeral key \(K\). He can then use \(K\) to encrypt (using symmetric encryption or pseudo-random generators and one-time pad) all the subsequent flows he sends to the first player. For this transformation to be secure, we also need to be sure that \(c\) (and the ability to decapsulate \(K\) for any \(\mathsf {ipk}\)) leaks no information about random coins used to generate the flow (or, more generally, the witness of \(\mathsf {x}\)). This is ensured by the zero-knowledge property, which states there must exist a trapdoor (for some common reference string) enabling to generate a public key \(\mathsf {ipk}\) and a trapdoor key \(\mathsf {itk}\) (using a trapdoor key algorithm \({\mathsf {iTKG}}\)), so that \(\mathsf {ipk}\) looks like a classical public key and \(\mathsf {itk}\) allows to decapsulate any ciphertext for \(\mathsf {ipk}\).

Overview of Our iZK and SSiZK Constructions. We proceed to provide an overview of our two-flow \(\mathsf{iZK }\) protocols; this is the main technical contribution of our work. Our main tool is Hash Proof Systems or Smooth Projective Hash Functions (\(\mathsf{SPHFs }\)) [18]. We observe that \(\mathsf{SPHFs }\) are essentially “honest-verifier” \(\mathsf{iZK }\); our main technical challenge is to boost this weak honest-verifier into full-fledged zero knowledge, without using pairings or random oracles.

Informally speaking, a smooth projective hash function on a language \(\mathscr {L}\) is a sort of hash function whose evaluation on a word \(C\in \mathscr {L}\) can be computed in two ways, either by using a hashing key \(\mathsf {hk} \) (which can be seen as a private key) or by using the associated projection key \(\mathsf {hp} \) (which can be seen as a public key). On the other hand, when \(C\notin \mathscr {L}\), the hash of C cannot be computed from \(\mathsf {hp} \); actually, when \(C\notin \mathscr {L}\), the hash of C computed with \(\mathsf {hk} \) is statistically indistinguishable from a random value from the point of view of any individual knowing the projection key \(\mathsf {hp} \) only. Hence, an \(\mathsf{SPHF }\) on \(\mathscr {L}\) is given by a pair \((\mathsf {Hash},\mathsf {ProjHash})\) with the requirements that, when there is a witness \(w\) ensuring that \(C\in \mathscr {L}\), \(\mathsf {Hash}(\mathsf {hk},\mathscr {L},C) = \mathsf {ProjHash}(\mathsf {hp},\mathscr {L},C,w)\), while when there is no such witness (i.e. \(C\notin \mathscr {L}\)), the smoothness property states that \(H = \mathsf {Hash}(\mathsf {hk},\mathscr {L},C)\) is random and independent of \(\mathsf {hp} \). In this paper, as in [26], we consider a weak form of \(\mathsf{SPHFs }\), where the projection key \(\mathsf {hp} \) can depend on C.

Concretely, if we have an \(\mathsf{SPHF }\) for some language \(\mathscr {L}\), we can set the public key \(\mathsf {ipk}\) to be empty (\(\bot \)), the secret key \(\mathsf {isk}\) to be the witness \(w\), the ciphertext \(c\) to be the projection key \(\mathsf {hp} \), and the encapsulated ephemeral key \(K\) would be the hash value. (Similar connections between \(\mathsf{SPHF }\) and zero knowledge were made in [1, 12, 25, 26]). The resulting \(\mathsf{iZK }\) would be correct and sound, the soundness coming from the smoothness of the \(\mathsf{SPHF }\): if the word C is not in \(\mathscr {L}\), even given the ciphertext \(c= \mathsf {hp} \), the hash value \(K\) looks random. However, it would not necessarily be zero-knowledge for two reasons: not only, a malicious verifier could generate a malformed projection key, for which the projected hash value of a word depends on the witness, but also there seems to be no trapdoor enabling to compute the hash value \(K\) from only \(c= \mathsf {hp} \).

These two issues could be solved using either Trapdoor \(\mathsf{SPHF }\)  [7] or \(\mathsf{NIZK }\) of knowledge of \(\mathsf {hk} \). But both methods require pairings or random oracle, if instantiated on cyclic or bilinear groups. Instead we construct it as follows:

First, suppose that a projection key is well-formed (i.e., there exists a corresponding hashing key). Then, there exists an unbounded zero-knowledge simulator that “extracts” a corresponding hashing key and computes the hash value. To boost this into full-fledged zero knowledge with an efficient simulator, we rely on the “OR trick” from [22]. We add a random 4-tuple \((g',h',u',e')\) to the CRS, and build an \(\mathsf{SPHF }\) for the augmented language \(C\in \mathscr {L}\) or \((g',h',u',e')\) is a \(\mathsf{DDH }\) tuple. In the normal setup, \((g',h',u',e')\) is not a \(\mathsf{DDH }\) tuple with overwhelming probability, so the soundness property is preserved. In the trapdoor setup, \((g',h',u',e') := (g',h',g'^r,h'^r)\) is a random \(\mathsf{DDH }\) tuple, and the zero-knowledge simulator uses the witness r to compute the hash value.

Second, to ensure that the projection key is well-formed, we use a second \(\mathsf{SPHF }\). The idea for building the second \(\mathsf{SPHF }\) is as follows: in most \(\mathsf{SPHF }\) schemes, proving that a projected key \(\mathsf {hp} \) is valid corresponds to proving that it lies in the column span of some matrix \(\varGamma \) (where all of the linear algebra is carried out in the exponent). Now pick a random vector \(\mathsf {tk} \): if \(\mathsf {hp} \) lies in the span of \(\varGamma \), then \(\mathsf {hp} ^\intercal \mathsf {tk} \) is completely determined given \(\varGamma ^\intercal \mathsf {tk} \); otherwise, it is completely random. The former yields the projective property and the latter yields smoothness, for the \(\mathsf{SPHF }\) with hashing key \(\mathsf {hk} \) and projection key \(\mathsf {tp} = \varGamma ^\intercal \mathsf {tk} \). Since the second \(\mathsf{SPHF }\) is built using the transpose \(\varGamma ^\intercal \) of the original matrix \(\varGamma \) (defining the language \(\mathscr {L}\)), we refer to it as a “transpose SPHF”. As it turns out, the second fix could ruin soundness of the ensuing \(\mathsf{iZK }\) protocol: a cheating prover could pick a malformed \(\varGamma ^\intercal \mathsf {tk} \), and then the hash value \(\mathsf {hp} ^\intercal \mathsf {tk} \) computed by the verifier could leak additional information about his witness \(\mathsf {hk} \) for \(\mathsf {hp} \), thereby ruining smoothness. To protect against the leakage, we would inject additional randomness into \(\mathsf {hk} \) so that smoothness holds even in the presence of leakage from the hash value \(\mathsf {hp} ^\intercal \mathsf {tk} \). This idea is inspired by the 2-universality technique introduced in a very different context of chosen-ciphertext security [18].

Finally, to get simulation-soundness (i.e., soundness even if the adversary can see fake or simulated proofs), we rely on an additional “OR trick” (mixed up with an idea of Malkin et al. [40]): we build an \(\mathsf{SPHF }\) for the augmented language \(C \in \mathscr {L}\), or \((g',h',u',e')\) is a \(\mathsf{DDH }\) tuple (as before), or \((g',h',\mathcal {W}_1(C),\mathcal {W}_2(C))\) is not a \(\mathsf{DDH }\) tuple (with \(\mathcal {W}_k\) a Waters function [45], \(\mathcal {W}_k(m) = v_{k,0} \prod _{i=1}^{|m|} v_{k,i}^{m_i}\), when \(m=m_1\Vert \dots \Vert m_{|m|}\) is a bitstring, the \(v_{k,0},\dots ,v_{k,|m|}\) are random group elements, and C is seen as a bitstring, for \(k=1,2\)). In the security proof, with non-negligible probability, \((g'',h'',\mathcal {W}_1(C),\mathcal {W}_2(C))\) is a non-\(\mathsf{DDH }\) tuple for simulated proofs, and a \(\mathsf{DDH }\) tuple for the soundness challenge, which proves simulation-soundness.

Organization. First, we formally introduce the notion of implicit zero-knowledge proofs (\(\mathsf{iZK }\)) in Sect. 2. Second, in Sect. 3, we discuss some difficulties related to the construction of \(\mathsf{iZK } \) from \(\mathsf{SPHF }\) and provide an intuition of our method to overcome these difficulties. Next, we show how to construct \(\mathsf{iZK } \) and \(\mathsf{SSiZK } \) from \(\mathsf{SPHF }\) over cyclic groups for any language handled by the generic framework [7], which encompasses most, if not all, known \(\mathsf{SPHFs }\) over cyclic groups. This is the main technical part of the paper. Third, in Sect. 4, we indeed show a concrete application of our \(\mathsf{iZK }\) constructions: the most efficient 3-round two-party protocol computing inner product in the UC framework with static corruption so far. We analyze our construction and provide a detailed comparison with the Groth-Sahai methodology [32] and the approach based on zero-knowledge proofs “\(\grave{\mathrm{a}}\) la Schnorr” [42]. In addition, as proof of concept, we show in the full version [8] that \(\mathsf{iZK }\) can be used instead of ZK arguments to generically convert any protocol secure in the semi-honest model into a protocol secure in the malicious model. This conversion follows the generic transformation of Goldreich, Micali and Wigderson (GMW) in their seminal papers [28, 29]. While applying directly the original transformation with Schnorr-like ZK protocols blows up the number of rounds by a multiplicative factor of at least three (even in the common reference string model), our conversion only adds a small constant number of rounds. Eventually, in the full version [8], we extend our construction of \(\mathsf{iZK } \) from \(\mathsf{SPHF } \) to handle larger classes of languages described by computational structures such as circuits or branching programs.

Additional Related Work. Using the “OR trick” with \(\mathsf{SPHF }\) is reminiscent of [2]. However, the methods used in our paper are very different from the one in [2], as we do not use pairings, but consider weaker form of \(\mathsf{SPHF }\) on the other hand.

A recent line of work has focused on the cut-and-choose approach for transforming security from semi-honest to malicious models [34, 35, 37–39, 43, 44] as an alternative to the use of zero-knowledge arguments. Indeed, substantial progress has been made towards practical protocols via this approach, as applied to Yao’s garbled circuits. However, the state-of-the-art still incurs a large computation and communication multiplicative overhead that is equal to the security parameter. We note that Yao’s garbled circuits do not efficiently generalize to arithmetic computations, and that our approach would yield better concrete efficiency for natural functions F that admit compact representations by arithmetic branching programs. In particular, Yao’s garbled circuits cannot take advantage of the structure in languages handled by the Groth-Sahai methodology [32], and namely the ones defined by multi-exponentiations: even in the latter case, Groth-Sahai technique requires pairings, while we will be able to avoid them.

The idea of using implicit proofs (without the zero-knowledge requirement) as a lightweight alternative to zero-knowledge proofs also appeared in an earlier work of Aiello, Ishai and Reingold [3]. They realize implicit proofs using conditional disclosure of secrets [27]. The latter, together with witness encryption [24] and \(\mathsf{SPHFs }\), only provide a weak “honest-verifier zero-knowledge” guarantee.

Recently, Jarecki introduced the concept of conditional key encapsulation mechanism [36], which is related to \(\mathsf{iZK }\) as it adds a “zero-knowledge flavor” to \(\mathsf{SPHFs }\) by allowing witness extraction. The construction is a combination of \(\mathsf{SPHF }\) and zero-knowledge proofs “\(\grave{\mathrm{a}}\) la Schnorr”. Contrary to \(\mathsf{iZK }\), it does not aim at reducing the interactivity of the resulting protocol, but ensures its covertness.

Witness encryption was introduced by Garg et al. in [24]. It enables to encrypt a message M for a word C and a language \(\mathscr {L}\) into a ciphertext c, so that any user knowing a witness \(w\) that \(C\in \mathscr {L}\) can decrypt c. Similarly to \(\mathsf{SPHFs }\), witness encryption also only has this “honest-verifier zero-knowledge” flavor: it does not enable to decrypt ciphertext for words \(C \notin \mathscr {L}\), with a trapdoor. That is why, as \(\mathsf{SPHF }\), witness encryption cannot be used to construct directly \(\mathsf{iZK }\).

2.1 Notations

Since we will now be more formal, let us present the notations that we will use. Let \({\{0,1\}}^*\) be the set of bitstrings. We denote by PPT a probabilistic polynomial time algorithm. We write \(y \leftarrow A(x)\) for ‘y is the output of the algorithm A on the input x’, while \(y \mathop {\leftarrow }\limits ^{{}_\$}A(x)\) means that A will additionally use random coins. Similarly, \(X \mathop {\leftarrow }\limits ^{{}_\$}\mathcal {X}\) indicates that X has been chosen uniformly at random in the (finite) set \(\mathcal {X}\). We sometimes write \(\mathsf {st}\) the state of the adversary. We define, for a distinguisher A and two distributions \(\mathcal {D}_0, \mathcal {D}_1\), the advantage of A (i.e., its ability to distinguish those distributions) by \(\mathsf {Adv}^{\mathcal {D}_0,\mathcal {D}_1}(A) = \Pr _{x \in \mathcal {D}_0}[A(x) = 1]-\Pr _{x \in \mathcal {D}_1}[A(x) = 1]\). The qualities of adversaries will be measured by their successes and advantages in certain experiments \(\mathsf {Exp}^\mathtt sec _\mathcal {A}\) or \(\mathsf {Exp}^\mathtt{sec -b}_\mathcal {A}\): \(\mathsf {Succ}^\mathtt sec (\mathcal {A},\mathfrak {K})=\Pr [\mathsf {Exp}^{\sec }_\mathcal {A}(1^\mathfrak {K})= 1]\) and \(\mathsf {Adv}^\mathtt{sec }(\mathcal {A},\mathfrak {K})=\Pr [\mathsf {Exp}^{\sec -1}_\mathcal {A}(1^\mathfrak {K}) = 1]-\Pr [\mathsf {Exp}^{\sec -0}_\mathcal {A}(1^\mathfrak {K}) = 1]\) respectively, where \(\mathfrak {K}\) is the security parameter, and probabilities are over the random coins of the challenger and of the adversary.

2.2 Definition

Let \((\mathsf i \!\mathscr {L}_{\mathsf {crs}})_{\mathsf {crs}} \) be a family of NP languages, indexed by a common reference string \({\mathsf {crs}} \), and defined by a witness relation \(\mathsf i \mathcal {R}_{\mathsf {crs}} \), namely \(\mathsf i \!\mathscr {L}= \{ \mathsf {x}\in \mathsf i \!\mathcal {X}_{\mathsf {crs}} \mid \exists \mathsf {iw},\, \mathsf i \mathcal {R}_{\mathsf {crs}} (\mathsf {x},\mathsf {iw}) = 1 \}\), where \((\mathsf i \!\mathcal {X}_{\mathsf {crs}})_{\mathsf {crs}} \) is a family of sets. \({\mathsf {crs}} \) is generated by some polynomial-time algorithm \(\mathsf {Setup}_{{\mathsf {crs}}} \) taking as input the unary representation of the security parameter \(\mathfrak {K}\). We suppose that membership to \(\mathcal {X}_{\mathsf {crs}} \) and \(\mathsf i \mathcal {R}_{{\mathsf {crs}}}\) can be evaluated in polynomial time (in \(\mathfrak {K}\)). For the sake of simplicity, \({\mathsf {crs}} \) is often implicit.

To achieve stronger properties (namely simulation-soundness in  Sect. 3.4), we sometimes also assume that \(\mathsf {Setup}_{{\mathsf {crs}}} \) can also output some additional information or trapdoor \(\mathcal {T} _{{\mathsf {crs}}} \). This trapdoor should enable to check, in polynomial time, whether a given word \(\mathsf {x}\) is in \(\mathsf i \!\mathscr {L}\) or not. It is only used in security proofs, and is never used by the \(\mathsf{iZK } \) algorithms.

An \(\mathsf{iZK }\) is defined by the following polynomial-time algorithms:

• \({\mathsf {i}{\mathsf {crs}}}\mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iSetup}}({\mathsf {crs}})\) generates the (normal) common reference string (CRS) \({\mathsf {i}{\mathsf {crs}}}\) (which implicitly contains \({\mathsf {crs}} \)). The resulting CRS provides statistical soundness;

• \(({\mathsf {i}{\mathsf {crs}}}, {\mathsf {i}\!\mathcal {T}}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iTSetup}}({\mathsf {crs}})\) ^{Footnote 4} generates the (trapdoor) common reference string \({\mathsf {i}{\mathsf {crs}}}\) together with a trapdoor \({\mathsf {i}\!\mathcal {T}}\). The resulting CRS provides statistical zero-knowledge;

• \((\mathsf {ipk},\mathsf {isk}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iKG}}^\ell ({\mathsf {i}{\mathsf {crs}}}, \mathsf {x}, \mathsf {iw})\) generates a public/secret key pair, associated to a word \(\mathsf {x}\in \mathsf i \!\mathscr {L}\) and a label \(\ell \in {\{0,1\}}^*\), with witness \(\mathsf {iw}\);

• \((\mathsf {ipk},\mathsf {itk}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iTKG}}^\ell ({\mathsf {i}{\mathsf {crs}}}, {\mathsf {i}\!\mathcal {T}}, \mathsf {x})\) generates a public/trapdoor key pair, associated to a word \(\mathsf {x}\in \mathcal {X}\) and a label \(\ell \in {\{0,1\}}^*\);

• \((c,K) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iEnc}}^\ell ({\mathsf {i}{\mathsf {crs}}}, \mathsf {ipk},\mathsf {x})\) outputs a ciphertext \(c\) of a value \(K\) (an ephemeral key), for the public key \(\mathsf {ipk}\), the word \(\mathsf {x}\), and the label \(\ell \in {\{0,1\}}^*\);

• \(K\leftarrow {\mathsf {iDec}}^\ell ({\mathsf {i}{\mathsf {crs}}}, \mathsf {isk}, c)\) decrypts the ciphertext \(c\) for the label \(\ell \in {\{0,1\}}^*\), and outputs the ephemeral key \(K\);

• \(K\leftarrow {\mathsf {iTDec}}^\ell ({\mathsf {i}{\mathsf {crs}}}, \mathsf {itk}, c)\) decrypts the ciphertext \(c\) for the label \(\ell \in {\{0,1\}}^*\), and outputs the ephemeral key \(K\).

The three last algorithms can be seen as key encapsulation and decapsulation algorithms. Labels \(\ell \) are only used for \(\mathsf{SSiZK }\) and are often omitted. The CRS \({\mathsf {i}{\mathsf {crs}}}\) is often omitted, for the sake of simplicity.

Normally, the algorithms \({\mathsf {iKG}}\) and \({\mathsf {iDec}}\) are used by the user who wants to (implicitly) prove that some word \(\mathsf {x}\) is in \(\mathsf i \!\mathscr {L}\) (and we often call this user the prover), while the algorithm \({\mathsf {iEnc}}\) is used by the user who wants to (implicitly) verify this (and we often call this user the verifier), as shown in Figs. 1 and 3. The algorithms \({\mathsf {iTKG}}\) and \({\mathsf {iTDec}}\) are usually only used in proofs, to generate simulated or fake implicit proofs (for the zero-knowledge property).

2.3 Security Requirements

An \(\mathsf{iZK }\) satisfies the four following properties (for any \(({\mathsf {crs}},\mathcal {T} _{{\mathsf {crs}}}) \mathop {\leftarrow }\limits ^{{}_\$}\mathsf {Setup}_{{\mathsf {crs}}} (1^\mathfrak {K})\)):

• Correctness. The encryption is the reverse operation of the decryption, with or without a trapdoor: for any \({\mathsf {i}{\mathsf {crs}}}\mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iSetup}}({\mathsf {crs}})\) or with a trapdoor, for any \(({\mathsf {i}{\mathsf {crs}}},{\mathsf {i}\!\mathcal {T}}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iTSetup}}({\mathsf {crs}})\), and for any \(\mathsf {x}\in \mathcal {X}\) and any \(\ell \in {\{0,1\}}^*\),

  • if \(\mathsf {x}\in \mathsf i \!\mathscr {L}\) with witness \(\mathsf {iw}\), \((\mathsf {ipk},\mathsf {isk}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iKG}}^\ell ({\mathsf {i}{\mathsf {crs}}}, \mathsf {x}, \mathsf {iw})\), and \((c, K) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iEnc}}^\ell (\mathsf {ipk}, \mathsf {x})\), then we have \(K= {\mathsf {iDec}}^\ell (\mathsf {isk}, c)\);

  • if \((\mathsf {ipk},\mathsf {itk}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iTKG}}^\ell ({\mathsf {i}\!\mathcal {T}}, \mathsf {x})\) and \((c, K) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iEnc}}^\ell (\mathsf {ipk},\mathsf {x})\), then we have \(K= {\mathsf {iTDec}}^\ell (\mathsf {itk}, c)\).

• Setup Indistinguishability. A polynomial-time adversary cannot distinguish a normal CRS generated by \({\mathsf {iSetup}}\) from a trapdoor CRS generated by \({\mathsf {iTSetup}}\). More formally, no PPT can distinguish, with non-negligible advantage, the two distributions:

  $$\begin{aligned}&\{{\mathsf {i}{\mathsf {crs}}} \mid {\mathsf {i}{\mathsf {crs}}}\mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iSetup}}({\mathsf {crs}}) \}&\{ {\mathsf {i}{\mathsf {crs}}} \mid ({\mathsf {i}{\mathsf {crs}}},{\mathsf {i}\!\mathcal {T}}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iTSetup}}({\mathsf {crs}})\}. \end{aligned}$$

• Soundness. When the CRS is generated as \({\mathsf {i}{\mathsf {crs}}}\mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iSetup}}({\mathsf {crs}})\), and when \(\mathsf {x}\notin \mathscr {L}\), the distribution of \(K\) is statistically indistinguishable from the uniform distribution, even given \(c\). More formally, if \(\varPi \) is the set of all the possible values of \(K\), for any bitstring \(\mathsf {ipk}\), for any word \(\mathsf {x}\notin \mathsf i \!\mathscr {L}\), for any label \(\ell \in {\{0,1\}}^*\), the two distributions:

  $$\begin{aligned}&\{(c,K) \mid (c,K) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iEnc}}^\ell (\mathsf {ipk},\mathsf {x})\}&\{(c,K') \mid (c,K) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iEnc}}^\ell (\mathsf {ipk},\mathsf {x}); K' \mathop {\leftarrow }\limits ^{{}_\$}\varPi \} \end{aligned}$$

  are statistically indistinguishable (\({\mathsf {iEnc}}\) may output \((\perp ,K)\) when the public key \(\mathsf {ipk}\) is not well formed).

• Zero-Knowledge. For any label \(\ell \in {\{0,1\}}^*\), when the CRS is generated using \(({\mathsf {i}{\mathsf {crs}}},{\mathsf {i}\!\mathcal {T}}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iTSetup}}^\ell ({\mathsf {crs}})\), for any message \(\mathsf {x}^* \in \mathsf i \!\mathscr {L}\) with the witness \(\mathsf {iw}^*\), the public key \(\mathsf {ipk}\) and the decapsulated key \(K\) corresponding to a ciphertext \(c\) chosen by the adversary, either using \(\mathsf {isk}\) or the trapdoor \(\mathsf {itk}\), should be indistinguishable, even given the trapdoor \({\mathsf {i}\!\mathcal {T}}\). More formally, we consider the experiment \(\mathsf {Exp}^{\mathtt{iZK\hbox {-}zk }\hbox {-}b}\) in Fig. 2. The \(\mathsf{iZK }\) is (statistically) zero-knowledge if the advantage of any adversary \(\mathcal {A}\) (not necessarily polynomial-time) for this experiment is negligible.

Experiments \(\mathsf {Exp}^{\mathtt{iZK\hbox {-}zk }\mathtt - b}\) for zero-knowledge of \(\mathsf{iZK }\), and \(\mathsf {Exp}^\mathtt{iZK\hbox {-}ss \mathtt - b}\) for simulation-soundness of \(\mathsf{SSiZK }\)

Full size image

Three-round zero-knowledge from \(\mathsf{iZK }\) for a word \(\mathsf {x}\in \mathsf i \!\mathscr {L}\) and a witness \(\mathsf {iw}\)

Full size image

We defined our security notion with a “composable” security flavor, as Groth and Sahai in [32]: soundness and zero-knowledge are statistical properties, the only computational property is the setup indistinguishability property. This is slightly stronger than what is needed, but is satisfied by our constructions and often easier to use.

We also consider stronger \(\mathsf{iZK }\), called simulation-sound \(\mathsf{iZK }\) or \(\mathsf{SSiZK }\), which satisfies the following additional property:

• Simulation Soundness. The soundness holds (computationally) even when the adversary can see simulated public keys and decryption with these keys. More formally, we consider the experiment \(\mathsf {Exp}^\mathtt{iZK\hbox {-}ss \mathtt - b}\) in Fig. 2, where the oracle \(\mathcal {O}\), and the lists L and \(L'\) are defined as follows:

  • on input \((\ell ,\mathsf {x})\), \(\mathcal {O}\) generates \((\mathsf {ipk},\mathsf {itk}) \mathop {\leftarrow }\limits ^{{}_\$}{\mathsf {iTKG}}({\mathsf {i}{\mathsf {crs}}},{\mathsf {i}\!\mathcal {T}}, \mathsf {x})\), stores \((\ell ,\mathsf {x},\mathsf {ipk},\mathsf {itk})\) in a list L, and outputs \(\mathsf {ipk}\);

  • on input \((\mathsf {ipk}, c)\), \(\mathcal {O}\) retrieves the record \((\ell ,\mathsf {x},\mathsf {ipk},\mathsf {itk})\) from L (and aborts if no such record exists), removes it from L, and adds it to \(L'\), computes \(K\leftarrow {\mathsf {iTDec}}^\ell ({\mathsf {i}{\mathsf {crs}}},\mathsf {itk},c)\), and outputs \(K\).

  The \(\mathsf{iZK }\) is (statistically) simulation-sound if the advantage of any adversary \(\mathcal {A}\) (not necessarily polynomial-time) for this experiment is negligible.

Remark 1

An \(\mathsf{iZK }\) for some language \(\mathsf i \!\mathscr {L}\) directly leads to a 3-round zero-knowledge arguments for \(\mathsf i \!\mathscr {L}\). The construction is depicted in Fig. 3 and the proof is provided in the full version [8]. If the \(\mathsf{iZK }\) is additionally simulation-sound, the resulting zero-knowledge argument is also simulation-sound.

Remark 2

For the sake of completeness, in the full version [8], we show how to construct \(\mathsf{iZK }\) from either \(\mathsf{NIZK }\) or Trapdoor \(\mathsf{SPHFs }\). In the latter case, the resulting \(\mathsf{iZK }\) is not statistically sound and zero-knowledge but only computationally sound and zero-knowledge. In both cases, using currently known constructions over cyclic groups, strong assumptions such as the random oracle model or pairings are needed.

Let us first recall the generic framework of \(\mathsf{SPHFs }\)  [7] for the particular case of cyclic groups, and when the projection key \(\mathsf {hp} \) can depend on the word C, as it is at the core of our construction of \(\mathsf{iZK }\). Second, we explain in more details the limitations of \(\mathsf{SPHFs }\) and the fact they cannot directly be used to construct \(\mathsf{iZK }\) (even with a concrete attack). Third, we show how to overcome these limitations to build \(\mathsf{iZK }\) and \(\mathsf{SSiZK }\).

3.1 Review of the Generic Framework of \(\mathsf{SPHFs }\) over Cyclic Groups

Languages. Let \(\mathbb {G}\) be a cyclic group of prime order p and \(\mathbb {Z}_p\) the field of integers modulo p. If we look at \(\mathbb {G}\) and \(\mathbb {Z}_p\) as the same ring \((\mathbb {G},+,\bullet )\), where internal operations are on the scalars, many interesting languages can be represented as subspaces of the vector space \(\mathbb {G}^n\), for some n. Here are some examples.

Example 3

( DDH or ElGamal Ciphertexts of 0). Let g and h be two generators of \(\mathbb {G}\). The language of \(\mathsf{DDH }\) tuples in basis (g, h) is

where r is the witness. It can be seen as the subspace of \(\mathbb {G}^2\) generated by (g, h). We remark that this language can also be seen as the language of (additive) ElGamal ciphertexts of 0 for the public key \(\mathsf {pk} =(g,h)\).    \(\square \)

Example 4

(ElGamal Ciphertexts of a Bit). Let us consider the language of ElGamal ciphertexts of 0 or 1, under the public key \(\mathsf {pk} = (g,h)\):

Here \(C=(u,e)\) cannot directly be seen as an element of some vector space. However, a word \(C = (u,e) \in \mathbb {G}^2\) is in \(\mathscr {L}\) if and only there exists \(\mathbf {\lambda } = (\lambda _1,\lambda _2,\lambda _3) \in \mathbb {Z}_p^3\) such that:

because, if we write \(C=(u,e)=(g^r,h^rg^b)\) (with \(r,b \in \mathbb {Z}_p\), which is always possible), then the first three equations ensure that \(\lambda _1 = r\), \(\lambda _2 = b\) and \(\lambda _3 = -rb\), while the last equation (right bottom) ensures that \(b(b-1) = 0\), i.e., \(b \in \{0,1\}\), as it holds that \((h^rg^b/g)^bh^{-rb} = g^{b(b-1)}=1\).

Therefore, if we introduce the notation \(\mathbf {\hat{C}}= \theta (C) :=\begin{pmatrix} u&e&1&1 \end{pmatrix} \in \mathbb {G}^4\), then the language \(\mathscr {L}\) can be defined as the set of \(C = (u,e)\) such that \(\mathbf {\hat{C}}\) is in the subspace of \(\mathbb {G}^4\) generated by the rows of the following matrix

Example 5

(Conjunction of Languages). Let \(g_i\) and \(h_i\) (for \(i=1,2\)) be four generators of \(\mathbb {G}\), and \(\mathscr {L}_i\) be (as in Example 3) the languages of \(\mathsf{DDH }\) tuples in bases \((g_i,h_i)\) respectively. We are now interested in the language \(\mathscr {L}= \mathscr {L}_1 \times \mathscr {L}_2 \subseteq \mathbb {G}^4\), which is thus the conjunction of \(\mathscr {L}_1\times \mathbb {G}^2\) and \(\mathbb {G}^2 \times \mathscr {L}_2\): it can be seen as the subspace of \(\mathbb {G}^4\) generated by the rows of the following matrix

This can also be seen as the matrix, diagonal by blocks, with \(\varGamma _1\) and \(\varGamma _2\) the matrices for \(\mathscr {L}_1\) and \(\mathscr {L}_2\) respectively.

More formally, the generic framework for \(\mathsf{SPHFs }\) in [7] considers the languages \(\mathscr {L}\subseteq \mathcal {X}\) defined as follows: There exist two functions \(\theta \) and \(\varGamma \) from the set of words \(\mathcal {X}\) to the vector space \(\mathbb {G}^n\) of dimension n, and to set \(\mathbb {G}^{k \times n}\) of \(k \times n\) matrices over \(\mathbb {G}\), such that \(C \in \mathscr {L}\) if and only if \(\mathbf {\hat{C}}:=\theta (C)\) is a linear combination of the rows of \(\varGamma (C)\). From a witness \(w\) for a word C, it should be possible to compute such a linear combination as a row vector \(\mathbf {\lambda }=(\lambda _i)_{i=1,\dots ,k} \in \mathbb {Z}_p^{1 \times k}\):

For the sake of simplicity, because of the equivalence between \(w\) and \(\mathbf {\lambda }\), we will use them indifferently for the witness.

SPHFs. Let us now build an \(\mathsf{SPHF }\) on such a language. A hashing key \(\mathsf {hk} \) is just a random column vector \(\mathsf {hk} \in \mathbb {Z}_p^n\), and the associated projection key is \(\mathsf {hp} :=\varGamma (C) \bullet \mathsf {hk} \). The hash value of a word C is then \(H :=\mathbf {\hat{C}}\bullet \mathsf {hk} \), and if \(\mathbf {\lambda }\) is a witness for \(C \in \mathscr {L}\), this hash value can also be computed as:

which only depends on the witness \(\mathbf {\lambda }\) and the projection key \(\mathsf {hp} \). On the other hand, if \(C \notin \mathscr {L}\), then \(\mathbf {\hat{C}}\) is linearly independent from the rows of \(\varGamma (C)\). Hence, \(H :=\mathbf {\hat{C}}\bullet \mathsf {hk} \) looks random even given \(\mathsf {hp} :=\varGamma (C) \bullet \mathsf {hk} \), which is exactly the smoothness property.

Example 6

The \(\mathsf{SPHF }\) corresponding to the language in Example 4, is then defined by:

For the sake of clarity, we will omit the C argument, and write \(\varGamma \), instead of \(\varGamma (C)\).

3.2 Limitations of Smooth Projective Hash Functions

At a first glance, as explained in the introduction, it may look possible to construct an \(\mathsf{iZK }\) from an \(\mathsf{SPHF }\) for the same language \(\mathscr {L}= \mathsf i \!\mathscr {L}\) as follows:

• \({\mathsf {iSetup}}({\mathsf {crs}})\) and \({\mathsf {iTSetup}}({\mathsf {crs}})\) outputs the empty CRS \({\mathsf {i}{\mathsf {crs}}}:=\perp \);

• \({\mathsf {iKG}}({\mathsf {i}{\mathsf {crs}}},\mathsf {x},\mathsf {iw})\) outputs an empty public key \(\mathsf {ipk}:=\perp \) together with the secret key \(\mathsf {isk}:=(\mathsf {x}, \mathsf {iw})\);

• \({\mathsf {iEnc}}(\mathsf {ipk},\mathsf {x})\) generates a random hashing key \(\mathsf {hk} \mathop {\leftarrow }\limits ^{{}_\$}\mathsf {HashKG}({\mathsf {crs}},\mathsf {x})\) and outputs the ciphertext \(c:=\mathsf {hp} \leftarrow \mathsf {ProjKG}(\mathsf {hk},{\mathsf {crs}},\mathsf {x})\) together with the ephemeral key \(K:=H \leftarrow \mathsf {Hash}(\mathsf {hk},{\mathsf {crs}},\mathsf {x})\);

• \({\mathsf {iDec}}(\mathsf {isk},c)\) outputs the ephemeral key \(K:={\mathsf {proj}H} \leftarrow \mathsf {ProjHash}(\mathsf {hp},{\mathsf {crs}},\mathsf {x},\mathsf {iw})\).

This construction is sound: if \(\mathsf {x}\notin \mathscr {L}\), given only \(c=\mathsf {hp} \), the smoothness ensures that \(K=H\) looks random. Unfortunately, there seems to be no way to compute \(K\) from only \(c\), or in other words, there does not seem to exist algorithms \({\mathsf {iTKG}}\) and \({\mathsf {iTDec}}\).

Example 6 Is Not Zero-Knowledge. Actually, with the \(\mathsf{SPHF }\) from Example 6, no such algorithm \({\mathsf {iTKG}}\) or \({\mathsf {iTDec}}\) (verifying the zero-knowledge property) exists. It is even worse than that: a malicious verifier may get information about the witness, even if he just has a feedback whether the prover could use the correct hash value or not (and get the masked value or not), in a protocol such as the one in Fig. 1. A malicious verifier can indeed generate a ciphertext \(c= \mathsf {hp} \), by generating \(\mathsf {hp} _1\) honestly but by picking \(\mathsf {hp} _2\) and \(\mathsf {hp} _3\) uniformly at random. Now, a honest prover will compute \({\mathsf {proj}H} = \mathsf {hp} _1^r\mathsf {hp} _2^b\mathsf {hp} _3^{-rb}\), to get back the ephemeral key (using \({\mathsf {iDec}}\)). When C is an encryption of \(b=1\), this value is random and independent of H, as \(\mathsf {hp} _2\) and \(\mathsf {hp} _3\) have been chosen at random, while when \(b=0\), this value is the correct \({\mathsf {proj}H}\) and is equal to \(H\). Thus the projected hash value \({\mathsf {proj}H} \), which is the ephemeral output key by the honest prover, reveals some information about b, part of the witness.

If we want to avoid such an attack, the prover has to make sure that the \(\mathsf {hp}\) he received was built correctly. Intuitively, this sounds exactly like the kind of verifications we could make with an \(\mathsf{SPHF }\): we could simply build an \(\mathsf{SPHF }\) on the language of the “correctly built” \(\mathsf {hp}\). Then the prover could send a projection key for this new \(\mathsf{SPHF }\) and ask the verifier to XOR the original hash value H with the hash value of this new \(\mathsf{SPHF }\). However, things are not that easy: first this does not solve the limitation due to the security proof (the impossibility of computing H for \(\mathsf {x}\notin \mathsf i \!\mathscr {L}\)) and second, in the \(\mathsf{SPHF }\) in Example 6, all projection keys are valid (since \(\varGamma \) is full-rank, for any \(\mathsf {hp} \), there exists necessarily a \(\mathsf {hk} \) such that \(\mathsf {hp} = \varGamma \bullet \mathsf {hk} \)).

3.3 \(\mathsf{iZK }\) Construction

Let us consider an \(\mathsf{SPHF }\) defined as in Sect. 3.1 for a language \(\mathsf i \!\mathscr {L}= \mathscr {L}\). In this section, we show how to design, step by step, an \(\mathsf{iZK }\) for \(\mathsf i \!\mathscr {L}\) from this \(\mathsf{SPHF }\), following the overview in Sect. 1. At the end, we provide a summary of the construction and a complete proof. We illustrate our construction on the language of ElGamal ciphertexts of bits (Examples 4 and 6), and refer to this language as “our example”. We suppose a cyclic group \(\mathbb {G}\) of prime order p is fixed, and that \(\mathsf{DDH }\) is hard in \(\mathbb {G}\) ^{Footnote 5}.

We have seen the limitations of directly using the original \(\mathsf{SPHF }\) are actually twofold. First, \(\mathsf{SPHFs }\) do not provide a way to compute the hash value of a word outside the language, with just a projection key for which the hashing key is not known. Second, nothing ensures that a projection key has really been derived from an actually known hashing key, and in such a bad case, the projected hash value may leak some information about the word C (and the witness).

To better explain our construction, we first show how to overcome the first limitation. Thereafter, we will show how our approach additionally allows to check the validity of the projection keys (with a non-trivial validity meaning). It will indeed be quite important to notice that the projection keys coming from our construction (according to one of the setups) will not necessarily be valid (with a corresponding hashing key), as the corresponding matrix \(\varGamma \) will not always be full rank, contrary to the projection keys of the \(\mathsf{SPHF }\) in Example 6. Hence, the language of the valid projection keys will make sense in this setting.

Adding the Trapdoor. The CRS of our construction is a tuple \({\mathsf {i}{\mathsf {crs}}}=(g',h',u'={g'}^{r'},e'={h'}^{s'}) \in \mathbb {G}^4\), with \(g',h'\) two random generators of \(\mathbb {G}\), and

• \(r',s'\) two random distinct scalars in \(\mathbb {Z}_p\), for the normal CRS generated by \({\mathsf {iSetup}}\), so that \((g',h',u',e')\) is not a \(\mathsf{DDH }\) tuple;

• \(r'=s'\) a random scalar in \(\mathbb {Z}_p\), for the trapdoor CRS generated by \({\mathsf {iTSetup}}\), with \({\mathsf {i}\!\mathcal {T}}=r'\) the trapdoor, so that \((g',h',u',e')\) is a \(\mathsf{DDH }\) tuple.

Then, we build an \(\mathsf{SPHF }\) for the augmented language \(\mathscr {L}_t\) defined as follows: a word \(C_t = (C,u',e')\) is in \(\mathscr {L}_t\) if and only if either C is in the original language \(\mathscr {L}\) or \((u',e')\) is a \(\mathsf{DDH }\) tuple. This new language \(\mathscr {L}_t\) can be seen as the disjunction of the original language \(\mathscr {L}\) and of the \(\mathsf{DDH }\) language in basis \((g',h')\). Construction of disjunctions of \(\mathsf{SPHFs }\) were proposed in [2] but require pairings. In this article, we use an alternative more efficient construction without pairing^{Footnote 6}. Let us show it on our example, with \(C_t = (C,u',e')\). We set \(\mathbf {\hat{C}}_t :=(g'^{-1},1,1,1,1,1,1)\) and \(\varGamma _t(C_t)\in \mathbb {G}^{(k+3) \times (n+3)}\) as

(2)

Let us show the language corresponding to \(\varGamma _t\) and \(\mathbf {\hat{C}}_t\) is indeed \(\mathscr {L}_t\): Due to the first column of \(\varGamma _t\) and the first element of \(\mathbf {\hat{C}}_t\), if \(\mathbf {\hat{C}}_t\) is a linear combination of rows of \(\varGamma _t\) with coefficients \(\mathbf {\lambda _t}\) (i.e., \(\mathbf {\hat{C}}_t = \mathbf {\lambda _t} \bullet \varGamma _t\)), one has \(\lambda _{t,4} + \lambda _{t,6} = -1\), and thus at least \(\lambda _{t,4}\) or \(\lambda _{t,6}\) is not equal to zero.

• If \(\lambda _{t,6} \ne 0\), looking at the second and the third columns of \(\varGamma _t\) gives that:

  $$\begin{aligned} \lambda _{t,5} \bullet (g',\; h') +\lambda _{t,6} \bullet (u',\;e') = (1,1) {\,\text {, i.e.,}\,} (u',e') = (g'^{\lambda _{t,5}/\lambda _{t,6}},\;h'^{\lambda _{t,5}/\lambda _{t,6}}), \end{aligned}$$

  or in other words \((u',e')\) is a \(\mathsf{DDH }\) tuple in basis \((g',h')\);

• if \(\lambda _{t,4} \ne 0\), looking at the last four columns of \(\varGamma _t\) gives that: \(\lambda _{t,4} \bullet \mathbf {\hat{C}}= \lambda _{t,4} \bullet (u,e,1,1)\) is a linear combination of rows of \(\varGamma \), hence \(\mathbf {\hat{C}}\) too. As a consequence, by definition of \(\mathscr {L}\), \(C \in \mathscr {L}\).

Now, whatever the way the CRS is generated (whether \((u',e')\) is a \(\mathsf{DDH }\) tuple or not), it is always possible to compute \({\mathsf {proj}H} \) as follows, for a word \(C \in \mathscr {L}\) with witnesses r and b:

When the CRS is generated with the normal setup, as shown above, this is actually the only way to compute \({\mathsf {proj}H} \), since \((u',e')\) is not a \(\mathsf{DDH }\) tuple and so \(\mathbf {\hat{C}}_t\) is linearly dependent of the rows of \(\varGamma _t\) if and only if \(C \in \mathscr {L}\). On the opposite, when the CRS is generated by the trapdoor setup with trapdoor \(r'\), we can also compute \({\mathsf {proj}H} \) using the witness \(r'\): \({\mathsf {proj}H} = \mathbf {\lambda '_t} \bullet \mathsf {hp} \text { with } \mathbf {\lambda '_t} = (0,0,0,0,r',-1)\).

However, the latter way to compute \({\mathsf {proj}H} \) gives the same result as the former way, only if \(\mathsf {hp} _{t,5}\) and \(\mathsf {hp} _{t,6}\) involve the correct value for \(\mathsf {hk} _1\). A malicious verifier could decide to choose random \(\mathsf {hp} _{t,5}\) and \(\mathsf {hp} _{t,6}\), which would make \(\mathbf {\lambda '_t} \bullet \mathsf {hp} \) look random and independent of the real hash value!

Ensuring the Validity of Projection Keys. The above construction and trapdoor would provide zero-knowledge if we could ensure that the projection keys \(\mathsf {hp} \) (generated by a potentially malicious verifier) is valid, so that, intuitively, \(\mathsf {hp} _{t,5}\) and \(\mathsf {hp} _{t,6}\) involve the correct value of \(\mathsf {hk} _1\). Using a zero-knowledge proof (that \(\mathsf {hp} \) derives from some hashing key \(\mathsf {hk} \)) for that purpose would annihilate all our efforts to avoid adding rounds and to work under plain \(\mathsf{DDH }\) (interactive ZK proofs introduce more rounds, and Groth-Sahai [32] \(\mathsf{NIZK }\) would require assumptions on bilinear groups). So we are left with doing the validity check again with \(\mathsf{SPHFs }\).

Fortunately, the language of valid projection keys \(\mathsf {hp} \) can be handled by the generic framework, since a valid projection key \(\mathsf {hp} \) is such that: \(\mathsf {hp} = \varGamma _t \bullet \mathsf {hk} \), or in other words, if we transpose everything \(\mathsf {hp} ^\intercal = \mathsf {hk} ^\intercal \bullet \varGamma _t^\intercal \). This is exactly the same as in Eq. (1), with \(\mathbf {\hat{C}}\leftrightarrow \mathsf {hp} ^\intercal \), \(\varGamma \leftrightarrow \varGamma _t^\intercal \) and witness \(\mathbf {\lambda }\leftrightarrow \mathsf {hk} ^\intercal \). So we can now define a smooth projective hash function on that language, where the projection key is called transposed projection key \(\mathsf {tp} \), the hashing key is called transposed hashing key \(\mathsf {tk} \), the hash value is called transposed hash value \({\mathsf {t}H} \) and the projected hash value is called transposed projected hash value \({\mathsf {t}{\mathsf {proj}H}} \).

Finally, we could define an \(\mathsf{iZK }\), similarly to the one in Sect. 3.2, except, \(\mathsf {ipk}\) contains a transposed projection key \(\mathsf {tp} \) (generated by the prover from a random transposed hashing key \(\mathsf {tk} \)), and c contains the associated transposed projected hash value \({\mathsf {t}{\mathsf {proj}H}} \) in addition to \(\mathsf {hp} \), so that the prover can check using \(\mathsf {tk} \) that \(\mathsf {hp} \) is valid by verifying whether \({\mathsf {t}{\mathsf {proj}H}} = {\mathsf {t}H} \) or not.

An Additional Step. Unfortunately, we are not done yet, as the above modification breaks the soundness property! Indeed, in this last construction, the prover now learns an additional information about the hash value H: \({\mathsf {t}{\mathsf {proj}H}} = \mathsf {hk} ^\intercal \mathsf {tp} \), which does depend on the secret key \(\mathsf {hk} \). He could therefore choose \(\mathsf {tp} = \mathbf {\hat{C}}_t^\intercal \), so that \({\mathsf {t}{\mathsf {proj}H}} = \mathsf {hk} ^\intercal \mathbf {\hat{C}}_t^\intercal = \mathbf {\hat{C}}_t \mathsf {hk} \) is the hash value \(H = K\) of C under \(\mathsf {hk} \).

We can fix this by ensuring that the prover will not know the extended word \(\mathbf {\hat{C}}_t\) on which the \(\mathsf{SPHF }\) will be based when he sends \(\mathsf {tp}\), using an idea similar to the 2-universality property of \(\mathsf{SPHF }\) introduced by Cramer and Shoup in [18]. For that purpose, we extend \(\varGamma _t\) and make \(\mathbf {\hat{C}}_t\) depends on a random scalar \(\zeta \in \mathbb {Z}_p\) chosen by the verifier (and included in \(c\)).

Detailed Construction. Let us now formally show how to build an \(\mathsf{iZK }\) from any \(\mathsf{SPHF }\) built from the generic framework of [7], following the previous ideas. We recall that we consider a language \(\mathscr {L}=\mathsf i \!\mathscr {L}\), such that a word \(\mathsf {x}=C\) is in \(\mathsf i \!\mathscr {L}\), if and only if \(\mathbf {\hat{C}}= \theta (C)\) is a linear combination of the rows of some matrix \(\varGamma \in \mathbb {G}^{k \times n}\) (which may depend on C). The coefficients of this linear combination are entries of a row vector \(\mathbf {\lambda }\in \mathbb {Z}_p^{1 \times k}\): \(\mathbf {\hat{C}}= \mathbf {\lambda }\bullet \varGamma \), where \(\mathbf {\lambda }= \mathbf {\lambda }(\mathsf {iw})\) can be computed from the witness \(\mathsf {iw}\) for \(\mathsf {x}\).

The setup algorithms \({\mathsf {iSetup}}({\mathsf {crs}})\) and \({\mathsf {iTSetup}}({\mathsf {crs}})\) are defined as above (page 13). We define an extended language using the generic framework:

where \(\varGamma '_t(\mathsf {x})\) is the matrix (initially called \(\varGamma _t(\mathsf {x})\) in Eq. (2), \(\mathbf{1}\) is the matrix of \(\mathbb {G}^{(2k+3) \times (2n+3)}\) with all entries equal to 1, and \(\zeta \) is a scalar used to ensure the prover cannot guess the word \(\mathbf {\hat{C}}_t\) which will be used, and so cannot choose \(\mathsf {tp} = \mathbf {\hat{C}}_t\). As explained above, this language corresponds to a 2-universal \(\mathsf{SPHF }\) for the disjunction of the language of \(\mathsf{DDH }\) tuples \((g',h',u',e')\) and the original language \(\mathscr {L}\). We write:

so that:

The resulting \(\mathsf{iZK }\) construction is depicted in Fig. 4. This is a slightly more efficient construction that the one we sketched previously, where the prover does not test anymore explicitly \({\mathsf {t}{\mathsf {proj}H}} \), but \({\mathsf {t}{\mathsf {proj}H}} \) (or \({\mathsf {t}H} \)) is used to mask \(K\). Thus, \({\mathsf {t}{\mathsf {proj}H}} \) no more needs to be included in \(c\).

Construction of \(\mathsf{iZK }\)

Full size image

Variants. In numerous cases, it is possible to add the trapdoor in a slightly more efficient way, if we accept to use word-dependent CRS. While the previous construction would be useful for security in the \(\mathsf{UC }\) framework [15], the more efficient construction with a word-dependent CRS is enough in the stand-alone setting. Independently of that improvement, it is also possible to slightly reduce the size of \(\mathsf {hp} \), by computing \(\zeta \) with an entropy extractor, and so dropping it from \(\mathsf {hp} \). Details for both variants are given in the full version [8].

3.4 \(\mathsf{SSiZK }\) Construction

Our \(\mathsf{SSiZK }\) construction is similar to our \(\mathsf{iZK }\) construction, except that, in addition both \({\mathsf {iSetup}}\) and \({\mathsf {iTSetup}}\) add the CRS \({\mathsf {i}{\mathsf {crs}}}\), a tuple \((v_{k,i})^{k=1,2}_{i=0,\dots ,2\mathfrak {K}}\) of group elements constructed as follows: for \(i=0\) to \(2\mathfrak {K}\) (with \(\mathfrak {K}\) the security parameter): \(r'_i \mathop {\leftarrow }\limits ^{{}_\$}\mathbb {Z}_p, v_{1,i} \leftarrow {g'}^{r'_i}, v_{2,i} \leftarrow {h'}^{r'_i}.\) We also define the two Waters functions [45] \(\mathcal {W}_k: {\{0,1\}}^{2\mathfrak {K}} \rightarrow \mathbb {G}\), as \(\mathcal {W}_k(m) = v_{k,0} \prod _{i=1}^{2\mathfrak {K}} v_{k,i}^{m_i}\), for any bitstring \(m = m_1\Vert \dots \Vert m_{2\mathfrak {K}} \in {\{0,1\}}^{2\mathfrak {K}}\). Finally, the CRS is also supposed to contain a hash function \(\mathcal {H}: {\{0,1\}}^*\rightarrow {\{0,1\}}^{2\mathfrak {K}}\) drawn from a collision-resistant hash function family \(\mathcal {HF}\).

Next, the language \(\mathscr {L}_t\) is further extended by adding 3 rows and 2 columns (all equal to 1 except on the 3 new rows) to both the sub-matrices \(\varGamma '_t(\mathsf {x})\) of \(\varGamma _t(\mathsf {x})\), where the 3 new rows are:

with \(u'' = \mathcal {W}_1(\mathcal {H}(\ell ,\mathsf {x}))\) and \(e'' = \mathcal {W}_2(\mathcal {H}(\ell ,\mathsf {x}))\). The vector \(\mathbf {\hat{C}}_t\) becomes \(\mathbf {\hat{C}}_t = (g^{-1},1,\dots ,1,g^{-\zeta },1,\dots ,1)\) (it is the same except for the number of 1’s). Due to lack of space, the full matrix is depicted in the full version [8], where the security proof can also be found. The security proof requires that \(\mathsf {Setup}_{{\mathsf {crs}}} \) also outputs some additional information or trapdoor \(\mathcal {T} _{{\mathsf {crs}}} \), which enables to check, in polynomial time, whether a given word \(\mathsf {x}\) is in \(\mathsf i \!\mathscr {L}\) or not.

Here is an overview of the security proof. Correctness, setup indistinguishability, and zero-knowledge are straightforward. Soundness follows from the fact that \((g',h',u'',e'')\) is a \(\mathsf{DDH }\)-tuple, when parameters are generated by \({\mathsf {iSetup}}\) (and also \({\mathsf {iTSetup}}\) actually), and so \((g',1)\) is never in the subspace generated by \((g',h')\) and \((u'',e'')\) (as \(h' \ne 1\)), hence the corresponding language \(\mathscr {L}_t\) is the same as for our \(\mathsf{iZK }\) construction. Finally, to prove simulation-soundness, we use the programmability of the Waters function [33] and change the generation of the group elements \((v_{k,i})\) so that for the challenge proof (generated by the adversary) \((g',h',u'',e'')\) is not a \(\mathsf{DDH }\)-tuple, while for the simulated proofs it is a \(\mathsf{DDH }\)-tuple. Then, we can change the setup to \({\mathsf {iSetup}}\), while still being able to simulate proofs. But in this setting, the word \(\mathbf {\hat{C}}_t\) for the challenge proof is no more in \(\mathscr {L}_t\), and smoothness implies simulation-soundness.

In case of biometric authentication, a server \(\mathcal {S}\) wants to compute the Hamming distance between a fresh user’s feature and the stored template, but without asking the two players to reveal their own input: the template y from the server side and the fresh feature x from the client side. One can see that the Hamming distance between the \(\ell \)-bit vectors x and y is the sum of the Hamming weights of x and y, minus twice the inner product of x and y. Let us thus focus on this private evaluation of the inner product: a client \(\mathcal {C}\) has an input \(x = (x_i)_{i=1}^\ell \in \{0,1\}^\ell \) and a server \(\mathcal {S}\) has an input \(y = (y_i)_{i=1}^\ell \in \{0,1\}^\ell \). The server \(\mathcal {S}\) wants to learn the inner product \(\mathsf{IP} = \sum _{i=1}^\ell x_i y_i \in \{0, \dots , \ell \}\), but nothing else, while the client \(\mathcal {C}\) just learns whether the protocol succeeded or was aborted.

Semi-Honest Protocol. \(\mathcal {C}\) can send an ElGamal encryption of each bit under a public key of her choice and then \(\mathcal {S}\) can compute an encryption of \(\mathsf{IP }+R\), with \(R \in \mathbb {Z}_p\) a random mask, using the homomorphic properties of ElGamal, and sends this ciphertext. \(\mathcal {C}\) finally decrypts and sends back \(g^{\mathsf{IP }+R}\) to \(\mathcal {S}\) who divides it by \(g^R\) to get \(g^\mathsf{IP }\). Since \(\mathsf{IP }\) is small, an easy discrete logarithm computation leads to \(\mathsf{IP }\).

Malicious Setting. To transform this semi-honest protocol into one secure against malicious adversaries, we could apply our generic conversion presented in the full version [8]. Here, we propose an optimized version of this transformation for this protocol. We use the ElGamal scheme for the encryption \(\mathcal {E}_\mathsf {pk} \), where \(\mathsf {pk} \) is a public key chosen by \(\mathcal {C}\) and the secret key is \(\mathsf {sk} = (\mathsf {sk} _j)_{j=1}^{\log p}\), and the Cramer-Shoup scheme [17] for commitments \(\mathsf{Com }\), of group elements or multiple group elements with randomness reuse, where the public key is in the CRS. The CRS additionally contains the description of a cyclic group and a generator g of this group. The construction is presented on Fig. 5. First, the client commits to her secret key (this is the most efficient alternative as soon as \(n \gg \ell \)) and sends encryptions \((c_i)_{i \le n}\) of her bits. Then, the server commits to his inputs \((y_i)_i\) and to two random integers \((R,R')\), computes the encryption \((\hat{u}, \hat{e})\) of \(g^{R\cdot \mathsf{IP }+ R'})\), re-randomized with a randomness \(\rho \), masked by an \(\mathsf{iZK }\) to ensure that the \(c_i\)’s encrypt bits under the key \(\mathsf {pk} \) whose corresponding secret key \(\mathsf {sk} \) is committed (masking one of the two components of an ElGamal ciphertext suffices). The client replies with \(g^{R\cdot \mathsf{IP }+R'}\), masked by a \(\mathsf{SSiZK }\) (this is required for UC security) to ensure that the \(\mathsf{Com }(g^{y_i})\) contains bits, and that the masked ciphertext has been properly built. The server then recovers \(g^{R\cdot \mathsf{IP }+R'}\), removes R and \(R'\), and tries to extract the discrete logarithm \(\mathsf{IP }\). If no solution exists in \(\{0,\dots ,\ell \}\), the server aborts. This last verification avoids the 2-round verification phase from our generic compiler: if the client tries to cheat on \(R\cdot \mathsf{IP }+ R'\), after removing R and \(R'\), the result would be random, and thus in the appropriate range with negligible probability \(\ell /p\), since \(\ell \) is polynomial and p is exponential. We prove in the full version [8] that the above protocol is secure against malicious adversaries in the UC framework with static corruptions, under the plain DDH assumption, and in the common reference string setting.

Semi-honest and malicious protocols for secure inner product computation

Full size image

Efficiency and Comparison with Other Methodologies. In the full version [8], we provide a detailed analysis of our inner product protocol in terms of complexity. Then, we estimate the complexity of this protocol when, instead of using \(\mathsf{iZK }\), the security against malicious adversaries in the UC model is ensured by using the Groth-Sahai methodology [32] or \(\varSigma \)-protocols. In this section, we sum up our comparisons in a table. The notation \(>\) indicates that the given complexity is a lower bound on the real complexity of the protocol (we have not taken into account the linear blow-up incurred by the conversion of \(\mathsf{NIZK }\) into \(\mathsf{SS\hbox {-}NIZK }\)), and \(\gg \) indicates a very loose lower bound. We stress that with usual parameter, an element of \(\mathbb {G}_2\) is twice as big as an element of \(\mathbb {G}_1\) (or \(\mathbb {G}\)) and the number of rounds in the major efficiency drawback (see Sect. 1). The efficiency improvement of \(\mathsf{iZK } \) compared to \(\mathsf{NIZK } \) essentially comes from their “batch-friendly” nature.

Moreover, our \(\mathsf{iZKs } \) do not require pairings, which allows us to use more efficient elliptic curves than the best existing curves for the Groth-Sahai methodology. With a reasonable choice of two curves, one without pairing and one with pairing, for 128 bits of security, we get the following results: (counting efficiency as a multiple of the running time of an exponentiation in \(\mathbb {G}_1\)).