Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications

Abstract

We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. In particular, under the SXDH assumption, the USS-QA-NIZK proof size is only seventeen group elements with a factor $O(\log {Q})$ loss in security reduction to SXDH. The USS-QA-NIZK primitive has many applications, including structure-preserving signatures (SPS), CCA2-secure publicly-verifiable public-key encryption (PKE), which in turn have applications to CCA-anonymous group signatures, blind signatures and unbounded simulation-sound Groth-Sahai NIZK proofs. We show that the almost tight security of our USS-QA-NIZK translates into constructions of all of the above applications with (almost) tight-security to standard assumptions such as SXDH and, more generally, $\mathcal{D}_k$-MDDH. Thus, we get the first publicly-verifiable (almost) tightly-secure multi-user/multi-challenge CCA2-secure PKE with practical efficiency under standard bilinear assumptions. Our (almost) tight SPS construction is also improved in the signature size over previously known constructions.

1 Introduction

Over the last decade, pairing-based cryptography has facilitated many new cryptographic protocols and applications that are provably-secure under static assumptions. Some of these static assumptions (SXDH, DLIN, MDDH) are now considered standard, as they generalize decisional-Diffie-Hellman (DDH) assumption to pairings-based groups. Some of the ground-breaking ideas include the Groth-Sahai (GS) non-interactive zero-knowledge (NIZK) proofs [GS12], fully-secure identity-based-encryption (IBE) [Wat09], structure-preserving signatures (SPS) [AFG+10], quasi-adaptive NIZK arguments (QA-NIZK) [JR13], and tightly-secure IBE [CW13]. In particular, structure-preserving signatures use Groth-Sahai NIZK proof structure to enable a wide-range of privacy-preserving applications, such as, group signatures [AHO10], blind signatures [AO09a, AFG+10], group encryption [CLY09], among others. Recent works [JR17, JOR18] have employed QA-NIZK to get more efficient SPS, and tightly-secure unbounded-simulation-sound QA-NIZK (USS-QA-NIZK [LPJY14, KW15]) to get tightly-secure CCA2-secure public-key encryption (PKE) in the multi-user and multi-challenge setting [LPJY15].

In this work we focus on the basic primitive of USS-QA-NIZK for linear-subspaces of vector spaces of bilinear groups, which has important implications as a structure-preserving version of it directly implies structure-preserving signatures. Further, it is already known to imply CCA2-secure PKE [LPJY15], which in turn leads to several new applications such as CCA-anonymous group signatures [AHO10], and UC-commitments [FLM11]. Further, an (almost) tightly-secure USS-QA-NIZK implies (almost) tightly-secure version of all the above applications. While an (almost) tightly-secure USS-QA-NIZK was given in [LPJY15] it required a large common reference string (CRS), which was of the order of the security parameter $\lambda$. In this work, we give the first (almost) tightly-secure USS-QA-NIZK for linear-subspaces with compact (number of group elements independent of $\lambda$) CRS and compact proofs. Moreover, the earlier construction only worked under the DLIN assumption in symmetric groups, and required non-standard assumptions in the asymmetric pairing-group setting, whereas we give a construction which is tightly-secure under the SXDH assumption in asymmetric groups. Asymmetric groups usually allow leaner constructions, which we validate below. At the same time, we make the CRS compact. Our construction of USS-QA-NIZK is also structure-preserving.

Related Techniques. In [KW15], Kiltz and Wee observed that QA-NIZK can be seen as a generalization of hash proof systems [CS98] to public-verifiability by publishing a “partial commitment” to the secret hash-key in the second group $\mathbb {G}_2$ of a pairings-based groups $(\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, e)$. Simulation of proofs of statements then just requires hash computation using the secret hash-key . Computational-soundness is slightly more tricky to prove than in the hash-proof setting, but essentially an adversary cannot generate hash proofs of false statements given only the “partial commitment” to and the projection-key (of the hash-proof system). In the simulation-soundness setting, the simulation of fake proofs would give additional information to the adversary about secret-hash key , and hence to obtain a USS-QA-NIZK, [KW15] encrypt the hash-proofs and employ a dual-system [Wat09] technique to achieve soundness. This methodology should be contrasted with the “OR” proof methodology of [LPJY15] (for USS-QA-NIZK) and [CCS09] (for unbounded simulation-sound GS-NIZK).

While the USS-QA-NIZK of [KW15] leads to compact proofs (of size only $(2k+2)$ under k-linear assumption), the security reduction to the underlying hardness assumption is not tight. The reason behind this being that the dual-system approach is itself not tight as at its heart it employs one-time simulation-soundness along with two-universal hash-proof systems [JR15], similar to Cramer-Shoup CCA2-encryption [CS98]. A nested-version of dual-system approach does lead to (almost) tight IBE [CW13], but then requires non-compact (master) public keys.

However, the concept of identity-space partitioning introduced in [CW13] is also applicable to signature schemes, and this technique repeatedly splits the message space into two based on the message or a tag. This idea was further enhanced in [Hof17] to adaptive partitioning in which the partitioning is decided dynamically based on an encrypted partitioning-bit. [AHN+17] refined this technique by introducing new ideas using “OR” GS-NIZK systems and made the scheme structure-preserving. Since signature schemes, especially the ones considered in the above works, usually encrypt a secret and prove in zero-knowledge that such a secret is encrypted in the signature, the question arises if this refined adaptive-partitioning methodology can be employed to the USS-QA-NIZK of [KW15] discussed above that encrypted the hash-proofs. One main difference between NIZK proofs embedded in signature schemes is that they need only be “designated-prover” NIZK proofs. In other words, such NIZK proofs while still providing public verifiability, need only give the proving capability to a designated party, namely the CRS (or public-key) generator itself. Hence, such designated-prover NIZK proofs are much easier to devise and it is not immediately clear if such restricted NIZK proofs can be extended to usual NIZK proofs (especially in the tight USS-NIZK setting).

Finally, we argue that the recent constructions of tight CCA2-secure PKE [GHK17, Hof17] (along with [CCS09]) also do not easily imply tight USS-NIZK. [CCS09] requires proving an OR-statement where one of the disjuncts is that a CCA2-PKE ciphertext is well-formed. For [GHK17], this statement is not Groth-Sahai friendly as its own “qualified”-OR proof in the ciphertexts employs a mapping that maps group elements to $\mathbb {Z}_q$ elements. This should be contrasted with Cramer-Shoup CCA2-PKE, which also has such a tag, but that is publicly computable from other elements in the ciphertext. This is not the case for [GHK17] as the mapping is from private elements. As for [Hof17], it uses disjunctive hash-proofs from [ABP15] which require the hash proof to be in the target group; GS-proofs of such statements are only possible in the Witness-Indistinguishable setting.

Our Contributions. We show that a different “OR” system than considered in [AHN+17] (or later works such as [JOR18]) does allow one to give (almost) tight (structure-preserving) USS-QA-NIZK for linear-subspaces with compact proof sizes and compact CRS-es. This “OR” system can be proved in the generic framework of [Ràf15], allowing us to obtain USS-QA-NIZKs under the SXDH assumption in asymmetric pairings groups, which was not previously known even for non-compact CRS. We also mention that while our structure-preserving USS-QA-NIZK construction loses a factor of $O(\lambda )$ in the security reduction, we give another variant employing tags (and hence not structure-preserving) that only has a $O(\log { Q})$ factor loss in security reduction, where Q is the number of adversarial requests for simulated proofs. In yet another variant, we consider the “designated prover” setting as described above, and give a leaner structure-preserving construction with a tighter reduction as well, i.e. with only a $O(\log {Q})$ factor loss.

As a first application, we show that a labeled version of our tight USS-QA-NIZK construction gives us a tight CCA2-secure publicly-verifiable labelled PKE in the multi-user multi-challenge setting¹. In Table 1, we compare our scheme with the state of the art schemes in [GHKW16, Hof17, GHK17] with the smallest possible assumption for each. While being practical by itself, our scheme is not the best one in terms of efficiency. What separates our scheme from other tightly secure schemes is the public verifiability, which allows anyone, without knowing the secret key, to check if a ciphertext decrypts to some plaintext. Feasibility results for publicly-verifiable tight CCA-PKE can be found in [HJ16] and [ADKNO13], but their ciphertext overhead is hundreds or even more than a thousand of group elements. Ours is the first practical publicly-verifiable scheme having only 19 elements of ciphertext overhead. Our scheme is also secure under the SXDH assumption with only a $O(\log {Q})$ loss in security reduction, where Q is the total number of (multi-challenge, multi-user) encryption-oracle requests by the adversary. CCA2-secure PKE and its variants that encrypt long messages have further applications, such as UC commitments, and we refer the reader to [LPJY15] for a good introduction.

Table 1. Comparison of tightly-secure public-key encryption schemes when the underlying assumptions are set to minimum ones, SXDH or DDH. Sizes count the number of group elements and $(n_1, n_2)$ denotes $n_1$ and $n_2$ elements in $\mathbb {G}_1$ and $\mathbb {G}_2$, respectively. Column ‘Pairings?’ shows necessity of pairing groups. SAE stands for symmetric authenticated encryption.

As a second application, we show that our designated-prover variant of structure-preserving USS-QA-NIZK from Sect. 5.2 yields an SPS scheme with the shortest signature size in the literature. Recall that unbounded simulation-soundness guarantees that it is hard to create a valid proof for any no-instances taken out of the legitimate subspace even after seeing simulated proofs for (also no-) instances of one’s choice. If we look at the simulation trapdoor as a secret-key and the simulated proofs as signatures, the USS-QA-NIZK can be considered as a signature scheme for message space consisting of no-instances, and the notion of unbounded simulation-soundness is exactly the same as existential unforgeability against adaptive chosen-message attacks. As formally proven in [AAO18], for bringing this idea to reality, we need an efficient mapping from desired message space to these no-instances. Since our USS-QA-NIZK allows simulation of fake proofs and we present a simple and efficient construction of injective mapping from a sequence of group elements to no-instances, this construction suffers no overhead for unilateral messages. This, along with the more efficient (designated-prover) USS-QA-NIZK gives us the shortest SPS known under the SXDH assumption, and with only a $O(\log {Q})$ factor loss in security-reduction (see Table 2).

Table 2. Comparison with existing SPS schemes for unilateral messages when assumptions are set to minimal ones. Columns labeled as |M|, $|\sigma |$, and |pk| show number of group elements in a message, a signature and a public key. For [HJ16], the parameter d limits number of signing queries to $2^d$.

Finally, we mention some plug-in applications of our tightly-secure PKE and SPS without details. Combining these two applications, we have the first (almost) tightly-secure CCA-anonymous dynamic group signature scheme with compact signature sizes and compact public keys under standard assumptions. Also we can instantiate a generic structure-preserving blind signature scheme of [Fis06] using our SPS to get an (almost) tight round-optimal scheme under $\mathcal{D}_k\text {-}{\textsc {mddh}}$ with compact signature size, whereas previous schemes in standard model were based on non-static assumptions [Fuc09, AO09b]. Finally, our (almost) tight CCA2-secure PKE scheme along with the generic construction of [CCS09], leads to a first (almost) tightly-secure unbounded simulation-sound Groth-Sahai NIZK proof system with compact CRS and proofs.

2 Preliminaries

We will consider cyclic groups $\mathbb {G}_1, \mathbb {G}_2$ and $\mathbb {G}_T$ of prime order q, with an efficient bilinear map $\textsf {e}: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T$. Group elements and will typically denote generators of the group $\mathbb {G}_1$ and $\mathbb {G}_2$ respectively. Following [EHK+13], we will use the notations $[a]_1, [a]_2$ and $[a]_T$ to denote , and respectively and use additive notations for group operations. When talking about a general group $\mathbb {G}$ with generator , we will just use the notation [a] to denote . The notation generalizes to vectors and matrices in a natural component-wise way.

For two vector or matrices A and B, we will denote the product $A^\top B$ as $A \cdot B$. The pairing product $\textsf {e}([A]_1, [B]_2)$ evaluates to the matrix product $[AB]_T$ in the target group with pairing as multiplication and target group operation as addition.

2.1 Matrix-DDH Assumptions and Boosting

We recall the Matrix Decisional Diffie-Hellman or MDDH assumptions from [EHK+13]. A matrix distribution $\mathcal{D}_{l, k}$, where $l > k$, is defined to be an efficiently samplable distribution on $\mathbb {Z}_q^{l \times k}$ which is full-ranked with overwhelming probability. The $\mathcal{D}_{l, k}$-MDDH assumption in group $\mathbb {G}$ states that with samples and $\text{ s }' \leftarrow \mathbb {Z}_q^l$, the tuple is computationally indistinguishable from . A matrix distribution $\mathcal{D}_{k+1, k}$ is simply denoted by $\mathcal{D}_k$.

It was shown in [JR16] that a $\mathcal{D}_k$-MDDH assumption can be boosted to generate additional (computationally) independently random elements.

For an $l \times k$ matrix , we denote to be the top $k \times k$ square sub-matrix of and to be the bottom $(l-k) \times k$ sub-matrix of .

Theorem 1

(Boosting [JR16]). Let $\mathcal{D}_k$ be a matrix distribution on $\mathbb {Z}_q^{(k+1) \times k}$. Define another matrix distribution $\mathcal{D}_{l,k}$ on $\mathbb {Z}_q^{l \times k}$ as follows: First sample matrices and and then output . Then the $\mathcal{D}_k$-MDDH assumption implies the $\mathcal{D}_{l, k}$-MDDH assumption with an $(l-k)$ security reduction.

They called boosting to be the process of stretching $\mathcal{D}_k$ to $\mathcal{D}_{l,k}$ as above. In our construction we will need to boost $\mathcal{D}_k$ to $\mathcal{D}_{2k, k}$.

2.2 Quasi-Adaptive NIZK Proofs

A witness relation is a binary relation on pairs of inputs, the first called a word and the second called a witness. Each witness relation R defines a corresponding language L which is the set of all words x for which there exists a witness w, such that R(x, w) holds.

We will consider Quasi-Adaptive NIZK proofs [JR13] for a probability distribution $\mathcal{D}$ on a collection of (witness-) relations $\mathcal{{R}}= \{R_\rho \}$ (with corresponding languages $L_\rho$). Recall that in a quasi-adaptive NIZK, the CRS can be set after the language parameter has been chosen according to $\mathcal{D}$. Please refer to [JR13] for detailed definitions.

For our USS-QA-NIZK construction we will also need a property called true-simulation-soundness. We recall the definitions of these concepts below.

Definition 1

(QA-NIZK [JR13]). We call a tuple of efficient algorithms $(\mathsf {pargen}, {\mathsf {crsgen}}, {\mathsf {prover}}, {\mathsf {ver}})$ a quasi-adaptive non-interactive zero-knowledge (QA-NIZK) proof system for witness-relations $\mathcal{{R}}_\eta = \{R_\rho \}$ with parameters sampled from a distribution $\mathcal{D}$ over associated parameter language $\mathsf {Lpar}$, if there exist simulators ${\mathsf {crssim}}$ and ${\mathsf {sim}}$ such that for all non-uniform PPT adversaries $\mathcal{A}_1, \mathcal{A}_2, \mathcal{A}_3,$ we have (in all of the following probabilistic experiments, the experiment starts by setting $\eta$ as $\eta \leftarrow \mathsf {pargen}(1^{\lambda })$, and choosing $\rho$ as $\rho \leftarrow \mathcal{D}_\eta$):  

Quasi-Adaptive Completeness: :

$$ \Pr \left[ \begin{array}{l} {\textsc {crs}}\leftarrow {\mathsf {crsgen}}(\eta ,\rho ) \\ (x, w) \leftarrow \mathcal{A}_1({\textsc {crs}}, \rho ) \\ \pi \leftarrow {\mathsf {prover}}({\textsc {crs}}, x, w) \end{array} \ :\ \begin{array}{c} {\mathsf {ver}}({\textsc {crs}}, x, \pi ) =1 \ \mathbf {if} \\ R_\rho (x,w) \end{array} \right] = 1 $$

Quasi-Adaptive Soundness: :

$$ \Pr \left[ \begin{array}{l} {\textsc {crs}}\leftarrow {\mathsf {crsgen}}(\eta ,\rho ) \\ (x, \pi ) \leftarrow \mathcal{A}_2({\textsc {crs}}, \rho ) \end{array} \ :\ \begin{array}{c} x \notin L_\rho \ \mathbf {and} \\ {\mathsf {ver}}({\textsc {crs}}, x, \pi ) =1] \end{array} \right] \approx 0 $$

Quasi-Adaptive Zero-Knowledge: :

$$ \begin{array}{c} \Pr \left[ {\textsc {crs}}\leftarrow {\mathsf {crsgen}}(\eta ,\rho ) \ :\ \mathcal{A}_3^{{\mathsf {prover}}({\textsc {crs}}, \cdot , \cdot )}({\textsc {crs}}, \rho ) = 1 \right] \\ \approx \\ \Pr \left[ ({\textsc {crs}}, {\mathsf {trap}}) \leftarrow {\mathsf {crssim}}(\eta , \rho ) \ :\ \mathcal{A}_3^{{{\mathsf {sim}^*}}({\textsc {crs}}, {\mathsf {trap}}, \cdot , \cdot )}({\textsc {crs}}, \rho ) = 1 \right] , \end{array} $$

where ${{\mathsf {sim}^*}}({\textsc {crs}}, {\mathsf {trap}}, x, w) = {\mathsf {sim}}({\textsc {crs}}, {\mathsf {trap}}, x)$ for $(x, w)\in R_\rho$ and both oracles (i.e. ${\mathsf {prover}}$ and ${{\mathsf {sim}^*}}$) output failure if $(x, w)\not \in R_\rho$.

 

Definition 2

(True-Simulation-Sound [Har11]). A QA-NIZK is called true -simulation-sound if soundness holds even when an adaptive adversary has access to simulated proofs on language members. More precisely, for all PPT $\mathcal{A}$,

$$ \Pr \left[ \begin{array}{l} ({\textsc {crs}}, {\mathsf {trap}}) \leftarrow {\mathsf {crssim}}(\eta , \rho ) \\ (x, \pi ) \leftarrow \mathcal{A}^{{\mathsf {sim}}({\textsc {crs}}, {\mathsf {trap}}, \cdot , \cdot )}({\textsc {crs}}, \rho ) \end{array} \ :\ \begin{array}{c} x \not \in L_\rho \ \mathbf {and} \\ {\mathsf {ver}}({\textsc {crs}}, x, \pi ) = 1 \end{array} \right] \approx 0, $$

where the experiment aborts if the oracle is called with some $x \not \in L_\rho$.

The construction of [JR14] yielded k element proofs of any linear subspace language membership and [KW15] generalized it to any $\mathcal{D}_k\text {-}{\textsc {mddh}}$ assumption. Both constructions are true-simulation-sound.

We now define the unbounded simulation-soundness (USS) property, which we seek to achieve in this paper. The prover and verifier can additionally accept a label which is bound to the proof.

Definition 3

(Unbounded Simulation-Soundness). A QA-NIZK is called (labeled) unbounded simulation sound if soundness holds even when an adaptive adversary has access to simulated proofs on arbitrary words of its choice. More precisely, for all PPT $\mathcal{A}$,

$$ \Pr \left[ \begin{array}{l} ({\textsc {crs}}, {\mathsf {trap}}) \leftarrow {\mathsf {crssim}}(\eta , \rho ) \\ (x, \mathtt {lbl}, \pi ) \leftarrow \mathcal{A}^{{\mathsf {sim}}({\textsc {crs}}, {\mathsf {trap}}, \cdot , \cdot )}({\textsc {crs}}, \rho ) \end{array} \ :\ \begin{array}{c} x \not \in L_\rho \ \wedge (x, \mathtt {lbl}) \notin \mathcal{Q} \\ {\mathsf {ver}}({\textsc {crs}}, x, \pi ) = 1 \end{array} \right] \approx 0, $$

where the set $\mathcal{Q}$ records (word, label) tuples queried to the simulator.

A stronger notion called Enhanced Unbounded Simulation-Soundness in the multi-CRS setting was formalized by [LPJY15], where soundness holds even if the discrete logs of the language are given to the adversary and the adversary has access to multiple CRS-es and corresponding oracles. We note that our construction satisfies this property as well.

Our main construction is also Structure-Preserving as the CRS and proof elements are all in the base groups of the bilinear map and verification consists only of pairing product equations.

2.3 Public-Key Encryption Schemes

Let $\mathsf {GEN}$ be an algorithm that, on input security parameter $\lambda$, outputs $\mathsf {par}$ that includes parameters of pairing groups.

Definition 4

(Public-key encryption). A Public-Key Encryption (PKE) scheme consists of probabilistic polynomial-time algorithms $\mathsf {PKE}:= (\mathsf {KeyGen},\mathsf {Enc},\mathsf {Dec})$:

• Key generation algorithm $\mathsf {KeyGen}(\mathsf {par})$ takes $\mathsf {par}\leftarrow \mathsf {GEN}(1^{\lambda })$ as input and generates a pair of public and secret keys $({\mathsf { pk}},{\mathsf { sk}})$. Message space $\mathcal {M}$ is determined by ${\mathsf { pk}}$.

• Encryption algorithm $\mathsf {Enc}({\mathsf { pk}},\mathsf {M})$ returns a ciphertext ${\mathsf {ct}}$.

• Decryption algorithm $\mathsf {Dec}({\mathsf { sk}},{\mathsf {ct}})$ is deterministic and returns a message $\mathsf {M}$.

For correctness, it must hold that, for all $\mathsf {par}\leftarrow \mathsf {GEN}(1^{\lambda })$, $({\mathsf { pk}},{\mathsf { sk}})\leftarrow \mathsf {KeyGen}(\mathsf {par})$, messages $\mathsf {M}\in \mathcal {M}$, and ${\mathsf {ct}}\leftarrow \mathsf {Enc}({\mathsf { pk}},\mathsf {M})$, $\mathsf {Dec}({\mathsf { sk}},{\mathsf {ct}})=\mathsf {M}$.

Definition 5

( $\mathsf {IND{\text {-}}mCPA}$ Security [BBM00]). A PKE scheme $\mathsf {PKE}$ is indistinguishable against multi-instance chosen-plaintext attack ($\mathsf {IND{\text {-}}mCPA}$-secure) if for any $q_e \ge 0$ and for all ${\textsc {ppt}}$ adversaries $\mathcal{{A}}$ with access to oracle ${\mathcal {O}}_e$ at most $q_e$ times the following advantage function ${\mathsf {Adv}}^{\mathsf {mcpa}}_{\mathsf {PKE}}(\mathcal{{A}})$ is negligible,

$$\begin{aligned} {\mathsf {Adv}}^{\mathsf {mcpa}}_{\mathsf {PKE}}(\mathcal{{A}}) := \left| \Pr \left[ b' = b \left| \begin{array}{l} \mathsf {par}\leftarrow \mathsf {GEN}(1^\lambda ); ({\mathsf { pk}},{\mathsf { sk}})\leftarrow \mathsf {KeyGen}(\mathsf {par}); \\ b \leftarrow \{0,1\}; b' \leftarrow \mathcal{{A}}^{{\mathcal {O}}_e(\cdot ,\cdot )}({\mathsf { pk}}) \end{array} \right. \right] - \frac{1}{2} \right| , \end{aligned}$$

where ${\mathcal {O}}_e(\mathsf {M}_0,\mathsf {M}_1)$ runs ${\mathsf {ct}}^* \leftarrow \mathsf {Enc}({\mathsf { pk}},\mathsf {M}_b)$, and returns ${\mathsf {ct}}^*$ to $\mathcal{{A}}$.

There exist public-key encryption schemes that are structure-preserving, $\mathsf {IND{\text {-}}mCPA}$ secure, and have tight reductions based on compact assumptions. Examples are ElGamal encryption [ElG84] and Linear encryption [BBS04] based on the DDH assumption and the Decision Linear assumption, respectively. In particular, we will use the scheme of [EHK+13], which is based on the $\mathcal{D}_k\text {-}{\textsc {mddh}}$ assumption. We will use the linear homomorphic property of this PKE in the construction - adding the ciphertexts implicitly adds the underlying plaintexts.

We now recall the definition of IND-CCA2 secure public key encryption scheme in the multi-challenge multi-user setting [BBM00], where the $\mathsf {par}$ are shared by multiple users while generating their own keys using $\mathsf {KeyGen}$.

Definition 6

(Multi-CCA [BBM00] (or see [LPJY15])).

A public-key encryption scheme is $(\mu , q_e)$-IND-CCA secure, for integers $\mu , q_e \in$ poly$(\lambda )$, if no PPT adversary has non-negligible advantage in the following game:

• 1. The challenger first generates $\mathsf {par}\leftarrow \mathsf {GEN}(1^{\lambda })$ and runs $({\mathsf { sk}}^{(i)}, {\mathsf { pk}}^{(i)})$ $\leftarrow$ $\mathsf {KeyGen}(\mathsf {par})$ for $i = 1$ to $\mu$. It gives $\{{\mathsf { pk}}^{(i)}\}_{i=1}^{\mu }$ to the adversary $\mathcal{{A}}$ and retains $\{{\mathsf { sk}}^{(i)}\}_{i=1}^{\mu }$. In addition, the challenger initializes a set $\mathcal{D}\leftarrow \phi$ and a counter $j_q \leftarrow 0$. Finally, it chooses a random bit $d \leftarrow \{0,1\}$.

• 2. The adversary $\mathcal{{A}}$ adaptively makes queries to the following oracles on multiple occasions:

  • Encryption query: $\mathcal{{A}}$ chooses an index $i \in [1..\mu ]$ and a pair $(M_0,M_1)$ of equal length messages. If $j_q = q_e$, the oracle returns $\bot$. Otherwise, it computes $C \leftarrow \mathsf {Enc}({\mathsf { pk}}^{(i)}, M_d)$ and returns C. In addition, it sets $\mathcal{D}:= \mathcal{D}\cup \{(i,C)\}$ and $j_q := j_q +1$.

  • Decryption query: $\mathcal{{A}}$ can also invoke the decryption oracle on arbitrary ciphertexts C and indices $i \in [1..\mu ]$. If $(i,C) \in \mathcal{D}$, the oracle returns $\bot$. Otherwise, the oracle returns $M \leftarrow \mathsf {Dec}({\mathsf { sk}}^{(i)},C)$, which may be $\bot$ if C is an invalid ciphertext.

• 3. The adversary $\mathcal{{A}}$ outputs a bit $d'$ and is deemed successful if $d' = d$. As usual, $\mathcal{{A}}$’s advantage is measured as the distance $\mathsf {Adv}^{\mathsf {mcca}}(\mathcal{{A}}) = | 2\, \Pr [d'=d] -1|$.

2.4 Structure-Preserving Signatures

Let $\mathsf {GEN}$ be a common parameter generation algorithm that outputs $\mathsf {par}$ for given security parameter $\lambda$.

Definition 7

(Structure-Preserving Signature). A structure-preserving signature scheme SPS is a triple of probabilistic polynomial time (PPT) algorithms $\mathsf {SPS}= ({\mathsf {KeyGen}}, {\mathsf {Sign}}, {\mathsf {Verify}})$:

• Key generation algorithm ${\mathsf {KeyGen}}(\mathsf {par})$ takes common parameter $\mathsf {par}$ and returns a public/secret key, (pk, sk), where $pk \in \mathbb {G}^{n_{pk}}$ for some $n_{pk} \in poly(\lambda )$. It is assumed that pk implicitly defines a message space $\mathcal {M} := \mathbb {G}^n$ for some $n \in poly(\lambda )$.

• Signing algorithm ${\mathsf {Sign}}(sk, M)$ takes secret key sk and a message $M \in \mathcal {M}$ as input and returns a signature $\sigma \in \mathbb {G}^{n_\sigma }$ for $n_\sigma \in poly(\lambda )$.

• Verification algorithm ${\mathsf {Verify}}(pk, M, \sigma )$ takes public key pk, message $M \in \mathcal {M}$, and signature $\sigma$ and outputs 1 or 0. It only evaluates group membership operations and pairing product equations.

Perfect correctness holds if for all $(pk,sk)\leftarrow {\mathsf {KeyGen}}(\mathsf {par})$ and all messages $M\in \mathcal {M}$ and all $\sigma \leftarrow {\mathsf {Sign}}(sk, M)$ we have ${\mathsf {Verify}}(pk, M, \sigma ) = 1$.

Definition 8

(Existential Unforgeability against Chosen Message Attack). To an adversary A and scheme SPS we associate the advantage function:

$$ \mathsf {Adv}^{\mathsf {cma}}_{\mathsf {SPS}}(A) := \Pr \left[ \begin{array}{l} \mathsf {par}\leftarrow \mathsf {GEN}(1^\lambda )\\ (pk,sk) \leftarrow {\mathsf {KeyGen}}(\mathsf {par}) \\ (M^*, \sigma ^*) \leftarrow A^{SignO(\cdot )}(pk) \end{array} \ :\ \begin{array}{c} M^* \notin Q_{msg} \ \mathbf {and} \\ {\mathsf {Verify}}(pk, M^*, \sigma ^*) = 1 \end{array} \right] $$

where SignO(M) runs $\sigma \leftarrow {\mathsf {Sign}}(sk, M)$, adds M to $Q_{msg}$ (initialized with $\emptyset$) and returns $\sigma$ to A. An SPS is said to be (unbounded) EUF-CMA-secure if for all PPT adversaries A, $\mathsf {Adv}^{\mathsf {cma}}_{\mathsf {SPS}}(A)$ is negligible.

3 The New (Almost) Tightly-Secure USS-QA-NIZK

The new USS-QA-NIZK scheme is formally described in Fig. 1, with the CRS and proof simulators described in Fig. 2. While a brief overview of the new scheme was given in the introduction, we now describe it in more detail.

We essentially combine techniques from the USS-QA-NIZK scheme of Kiltz and Wee [KW15] and the tightly secure SPS scheme of Jutla, Ohkubo and Roy [JOR18]. Following [KW15], we encrypt a basic QA-NIZK proof of the given word using an augmented ElGamal encryption scheme:

Notice that unlike [KW15], we did not use an integer tag in the encryption. This helps us keep the construction structure preserving. We also include a QA-NIZK $\varPi _2$ certifying that $(\varvec{\rho }, \hat{\varvec{\rho }}, \gamma )$ is well-formed. Now we extend this tuple with elements which enable adaptive partitioning as in [JOR18]. This includes a double ElGamal encryption of a bit z, along with a QA-NIZK proof of equality of plaintexts. The final piece is an OR-NIZK proof that proves either $(\varvec{\rho }, \hat{\varvec{\rho }})$ is consistent, or that z is same as a bit x which is given encrypted in the public key. Intuitively, in several games in the proof, the OR proof enables us to randomize the ciphertexts in the partitions where the disjunct $z=x$ holds, while restricting the adversary to attempt a win only in the other partitions. Instantiations of OR-NIZKs are given in Sect. 4.

The (almost) tight security of this scheme is proved in the next section. We prove that this construction has an $O(\lambda )$ reduction to $\mathcal{D}_k\text {-}{\textsc {mddh}}$. In Sect. 3.2, we provide another construction which builds upon this one and enjoys a better $O(\log Q)$ reduction, where Q is the number of simulated proofs given out. Finally, in Sect. 3.3, we describe some optimizations which reduce the size of the proofs even further.

Fig. 1.

Tightly-secure USS-QA-NIZK $\varPi$.

Fig. 2.

CRS and Proof simulators for $\varPi$.

3.1 Security of the USS-QA-NIZK Scheme

In this section we state and prove the security of the USS-QA-NIZK scheme $\varPi$ described in Fig. 1, with simulators described in Fig. 2.

Theorem 2

For any efficient adversary $\mathcal{A}$, which makes at most Q simulator queries before attempting a forged proof, its probability of success (${\textsc {adv}}_{\varPi }^{\mathsf {{uss}}}(Q)$) in the USS game against the scheme $\varPi$ is at most

$$ {\textsc {adv}}_{\varPi _2}^{\mathsf {{tss}}} + 12L \cdot {\textsc {adv}}_{\varPi _1}^{\mathsf {{tss}}} + 8L \cdot {\textsc {adv}}_{\mathcal{D}_{2k,k}\text {-}{\textsc {mddh}}} + (12L+1) {\textsc {adv}}^{\mathsf {{zk}}}_{\varPi _0} $$

$$ + 4L \cdot {\textsc {adv}}^{\mathsf {mcpa}}_{\mathsf {PKE}} + \frac{6L + (Q+1)^2 + 1}{q} + \frac{Q}{2^L} $$

Here L is the least integer greater than the bit size of q and hence is $O(\lambda )$.

Remark 1

${\textsc {adv}}_{\varPi _i}^{\mathsf {{tss}}}$ of a QA-NIZK $\varPi _i$ reduces to $\mathcal{D}_k\text {-}{\textsc {mddh}}$ by a factor of $(n-t)$ where the (affine) linear subspace language is of dimension t within a full space of dimension n. Also, ${\textsc {adv}}^{\mathsf {{zk}}}_{\varPi _0}$ of the OR-NIZK $\varPi _0$ reduces to $\mathcal{D}_k\text {-}{\textsc {mddh}}$ by a factor of 1.

Finally, $\mathcal{D}_{2k,k}\text {-}{\textsc {mddh}}$ reduces to $\mathcal{D}_k\text {-}{\textsc {mddh}}$ by a factor of k by boosting (See Sect. 2.1). Thus the overall reduction in Theorem 2 to $\mathcal{D}_k\text {-}{\textsc {mddh}}$ is $O(\lambda )$.

Proof Intuition. At the highest level, we go through a sequence of games (0–4), starting from Game 0 which is the NIZK simulator of Fig. 2 playing against a USS adversary and ending with Game 4, where the adversary has information theoretically negligible chance of winning. Essentially, in going from Game 2 to Game 3, the $\gamma$ component is masked with an independently random element which depends on the input word, except for a randomly chosen point $\tau$, where the mask is 0. Then finally in Game 4, the quantity is shifted by a random vector in the kernel of the language matrix . This still keeps the CRS unchanged and since the simulated proofs have been masked by independently random elements (except at the point $\tau$ which occurs with negligible probability), they are also independent of this random kernel vector. However, the random kernel vector shows up in the winning condition of Game 4 and makes it statistically hard for the adversary to satisfy verification with a non-member word.

Going from Game 2 to 3 requires another set of hybrid games in which we introduce the mask elements into the $\gamma$’s. The games proceed bit by bit based on a random bit-string of length L, which is obtained by applying a random injective function ${\textsc {{rp}}}$ to the input word . In every hybrid j, which runs from 0 to L, the mask depends on the first j bits of . The mask function is inductively defined as follows:

where ${\textsc {{rf}}}_j$ is a random function from $\{0,1\}^j$ to $\mathbb {Z}_q$, except at a point $\tau |_j$, the first j bits of $\tau$, where its value is 0. ${\textsc {{rf}}}'_{j-1}$ is another independently random function from $\{0,1\}^{j-1}$ to $\mathbb {Z}_q$. The 0-th hybrids start as Game 2 with the ‘0’ mask, which is the value of ${\textsc {{rf}}}_0(\epsilon )$. The L-th hybrids end in Game 3 with the mask depending on all the bits of , hence essentially the whole word.

The adaptive partitioning technique of [Hof17] helps us switching from ${\textsc {{rf}}}_{j-1}$ to ${\textsc {{rf}}}_{j}$ with a constant number of $\texttt {MDDH}$ reductions. Essentially, in the j-th hybrid, the j-th bit of induces two partitions of the message space: (1) where the bit is $\tau _j$, soundness is enforced to hold in the winning condition and (2) where the bit is $1-\tau _j$, all such simulated proofs can be switched in one go with a constant number of $\texttt {MDDH}$ transitions. Formal details follow.

Proof

We go through a sequence of Games to which are described below and summarized in Fig. 3. In the following, $\text{ Pr }_i[X]$ will denote probability of predicate X holding in probability space defined in game and $\textsf {WIN} _i$ will denote the winning condition for the adversary in game .

Fig. 3.

Top level games and winning conditions

Game : This game exactly replicates the simulator in Fig. 2 to the adversary. So the adversary’s advantage in (defined as $\textsf {WIN} _0$ below) is the USS advantage we seek to bound.

Game : In Game , the challenger lazily simulates (by maintaining a table) a random function ${\textsc {{rp}}}$ from $\mathbb {G}_1^n$ to $\{0,1\} ^L$. Define $\textsf {Col}$ to be the predicate which returns true when there is a collision, i.e., when any pair of message vectors from the set of signature queries union the adversarial response message at the end get mapped to the same output L-bit string. In this game, the adversary is allowed to win outright if $\textsf {Col}$ is true at the end:

The difference in advantage is at most the collision probability, which is bounded by $(Q+1)^2/q$.

Game : In this game the CRS of $\varPi _2$ is generated in the simulation mode and the trapdoor is kept by the challenger to generate simulated proofs. The challenge-response in this game is the same as . The winning condition is now defined as:

The difference in advantages of the adversary is upper bounded by the unbounded true-simulation-soundness of $\varPi _2$:

$$\begin{aligned} | \text{ Pr }_{1} [ \textsf {WIN} _1 ] - \text{ Pr }_{0} [ \textsf {WIN} _0] | \le {\textsc {adv}}_{\varPi _2}^{\mathsf {{tss}}} \end{aligned}$$

(1)

Game : In this game, the OR-NIZK CRS is generated as a simulation CRS and the witness of $(\varvec{\rho }^i, \hat{\varvec{\rho }}^i, {\mathsf {ct}}_z^{1i} - {\mathsf {ct}}_x) \in L_0$, is switched to . The winning condition $\textsf {WIN} _2$ remains the same as $\textsf {WIN} _1$.

$$\begin{aligned} | \text{ Pr }_{2} [ \textsf {WIN} _2 ] - \text{ Pr }_{1} [ \textsf {WIN} _1] | \le {\textsc {adv}}_{\varPi _0}^{\mathsf {{zk}}} \end{aligned}$$

(2)

Game : In this game, the challenger first chooses a uniformly random string $\tau \in \{0,1\} ^L$ and also lazily maintains a function ${\textsc {{rf}}}_L$ mapping $\{0,1\} ^L$ to $\mathbb {Z}_q$. The function ${\textsc {{rf}}}_L$ has the property that it is a random and independent function from $\{0,1\} ^L$ to $\mathbb {Z}_q$, except at $\tau$ where its value is 0. In , each signature component $\gamma ^i$ is generated as , instead of . For ease of exposition, we will denote as $\nu ^i$. The winning condition $\textsf {WIN} _3$ remains the same as $\textsf {WIN} _2$.

Lemma 1

$| \text{ Pr }_{3} [ \textsf {WIN} _3 ] - \text{ Pr }_{2} [ \textsf {WIN} _2] | \le$

$$ 12L \cdot {\textsc {adv}}_{\varPi _1}^{\mathsf {{tss}}} + 8L \cdot {\textsc {adv}}_{\mathcal{D}_{2k,k}\text {-}{\textsc {mddh}}} $$

$$ + 12L \cdot {\textsc {adv}}^{\mathsf {{zk}}}_{\varPi _0} + 4L \cdot {\textsc {adv}}^{\mathsf {mcpa}}_{\mathsf {PKE}} + \frac{6L}{q} $$

We prove this lemma in the full paper by going through a finer set of hybrid games.

Game : In this game, the challenger samples , and generates differently as , where matrix such that . Observe that the public key component becomes . So does not show up in the public key.

Consequently, the computations of $\gamma ^i$’s are changed to . Also, the winning condition check on $\gamma ^*$ is modified accordingly to .

We now claim that $\text{ Pr }_4 [\textsf {WIN} _4] \le \frac{1}{q} + \frac{Q}{2^L}$. To see this, recall that ${\textsc {{rf}}}$ maps any element of $\{0,1\} ^L$ to a uniformly random element of $\mathbb {Z}_q$, except $\tau$, which it maps to 0. Now, if none of the adversary queries is actually mapped to $\tau$ by ${\textsc {{rp}}}$, no information about it is leaked to the adversary. The probability that for any i, , is upper bounded by $\frac{Q}{2^L}$.

Now, in the case that is not $\tau$ for any i, we have that is uniformly random and independent of everything else. This means that it completely hides the term in the $\gamma ^i$ components of the signature responses.

As for the adversary’s forged proof, is non-zero if is not in the span of . Also, is not shown in any public key and as we reasoned in the last paragraph, it doesn’t show up (whp) in any signature either. Consequently, is uniformly random in $\mathbb {Z}_q$ and independent of the adversary’s view. Therefore, the probability of satisfying is upper bounded by $1 \slash q$. This proves the claim.

3.2 USS-QA-NIZK Scheme with $O(\log Q)$ Reduction

The scheme is given in Fig. 4 and the top level proof game table is given in the full paper. Since this scheme is very similar to the one given earlier, we only point out the essential points of difference in the construction and proof.

The scheme uses a similar augmented ElGamal encryption of a basic QA-NIZK proof:

The additional part is a tagged component reminiscent of the Cramer-Shoup CCA2 encryption scheme [CS02], where $\tau$ is a collision resistant hash on rest of the proof components. Rest of it is fairly similar to the earlier construction. Unfortunately, this construction is no longer structure-preserving due to the tag computation.

To prove $O(\log Q)$ reduction, we follow the partitioning strategy of [GHKP18], where the partition is done on the bits of the query index i, instead of a random function applied to the argument. This strategy did not work for our earlier construction because ${\textsc {{rf}}}$ mapped to 0 at one point of it’s domain and the proof relied on the fact that such a point is exponentially hard to determine since the domain size is exponential in $\lambda$.

In the proof of security of this construction, we take account of the fact that ${\textsc {{rf}}}$ could map to 0 at a point which can non-negligibly occur in a query. We instead argue that since the tag of such a query response would be different from the tag of the adversary’s output proof, the response can still be randomized due to pairwise independence. A detailed proof will be in the full version of the paper.

Theorem 3

For any efficient adversary $\mathcal{A}$, which makes at most Q simulator queries before attempting a forged proof, its probability of success (${\textsc {adv}}_{\varPi '}^{\mathsf {{uss}}}(Q)$) in the USS game against the scheme $\varPi '$ is at most (Here L is $\log Q$):

$$ {\textsc {adv}}_{\varPi _2}^{\mathsf {{tss}}} + 12L \cdot {\textsc {adv}}_{\varPi _1}^{\mathsf {{tss}}} + 8L \cdot {\textsc {adv}}_{\mathcal{D}_{2k,k}\text {-}{\textsc {mddh}}} + (12L+1) {\textsc {adv}}^{\mathsf {{zk}}}_{\varPi _0} $$

$$ + 4L \cdot {\textsc {adv}}^{\mathsf {mcpa}}_{\mathsf {PKE}} + \frac{6L + (Q+1)^2 + 1}{q}. $$

Fig. 4.

Labeled Tightly-secure USS-QA-NIZK $\varPi '$, with $O(\log Q)$ reduction to $\mathcal{D}_k\text {-}{\textsc {mddh}}$.

3.3 Optimizations

In this section, we describe two optimizations which reduce the size of the proofs further by 2k elements under the $\mathcal{D}_k\text {-}{\textsc {mddh}}$ assumption.

ElGamal Encryption with Common Randomness. As described in [AHN+17], the randomnesses and of ciphertexts ${\mathsf {ct}}_z^1$ and ${\mathsf {ct}}_z^2$ can be shared and merged into a single k-element . In more details, let’s say and , which are encryptions of z under public keys and . Then instead of computing the ciphertexts independently, we can merge them into . This saves us k elements. Importantly, we can still enable transitions where we can hold the decryption key of one system, while switching the plaintext of the other.

Merge QA-NIZKs in the Same Group. The reason we did not combine $\varPi _1$ and $\varPi _2$ is that we needed to use the true-simulation-soundness of one system, while producing proofs over fake instances with the other. However, we show in the full paper, that we can still merge the proofs into one proof over the combined linear system, and still be independently able to use the true-simulation-soundness of its parts. This saves us k elements from $\varPi$.

In more details, let the combined language be defined by the matrix , where both $n_1$ and $n_2$ are greater than t. What we show is, provided the words corresponding to are not faked then even if the words corresponding to are faked, true-simulation-soundness holds for the components.

4 NIZK for Disjunction of Linear Subspaces

We have critically used an “OR”-NIZK in our USS-QA-NIZK construction. In this section we describe three flavors of OR-NIZKs. The first one is a standard NIZK where both the prover and verifier are public algorithms. The second one is a designated prover system where only the verifier is public - this flavor is useful for signature schemes where the signing key is held private. The final one is a designated verifier system where the prover is public, but the verifier is private - this is useful in public-key encryption schemes where the public encryption algorithm is required to prove consistency, but only the private decryption algorithm needs to check a proof.

4.1 Public CRS Setting

In this section we describe a NIZK proof system for languages of the following type:

The system is described in Fig. 5 and is based on [Ràf15] with syntax based on [GHKP18]. The proofs of completeness, zero-knowledge and soundness are similar to these papers. We only give a sketch below.

Fig. 5.

NIZK for OR languages based on [Ràf15].

The completeness of the system is straightforward. Zero-knowledge is proved by transitioning to a different way of generating the CRS along with a trapdoor. The transition is enabled by the $\mathcal{D}_k\text {-}{\textsc {mddh}}$ assumption on and the resulting CRS and proof simulators are also given in the same figure.

We now prove perfect soundness. Since , at least one of and should be outside the span of . WLOG, let this be . Therefore, there should be a vector , such that and . Right multiplying this vector to the verification equation gives us . This means satisfies the disjunct .

4.2 Designated Prover Setting

In Fig. 5 we saw an efficient NIZK proof for the “OR” language of Fig. 1, where one of the disjuncts was a predicate on group elements in the CRS of the USS-QA-NIZK, namely that ${\mathsf {ct}}_x$ was a binding commitment to x (using randomness $r_x$). The quantity $r_x$ cannot be made public in this general setting as proving simulation-soundness requires us to hide x from the public. However, in the application of USS-QA-NIZK to build SPS, the quantity $r_x$ can indeed be given to a “designated” prover, i.e. the signer, and the quantity still remains private. In particular, in a forgery attempt, the adversary does not have access to $r_x$, as the signer is an honest party. In such a situation, i.e. where $r_x$ in the commitment to x is available to the designated prover, we can give an even more efficient NIZK. For ease of exposition, we will restrict ourselves to the SXDH asymmetric pairings-group setting in this section. The results can easily be generalized to $\mathcal{D}_k\text {-}{\textsc {mddh}}$ setting.

Consider the “OR” language,

$$ \mathcal{L} = \begin{Bmatrix} \varvec{\alpha }, \hat{\varvec{\alpha }}, \varvec{x} \,|\, \exists r, r_x \in \mathbb {Z}_q: \\ (\varvec{\alpha } = r[1]_1 \ \mathbf{and } \ \hat{\varvec{\alpha }} = r[b]_1) \ \mathbf{or } \ \varvec{x} = \text{ com }(0; r_x) \end{Bmatrix} $$

where com$(x; r_x)$ is a binding commitment to x using randomness $r_x$ (e.g. a GS-commitment or ElGamal encryption), and $[b]_1$ is public.

It is not difficult to see that the above is implied by the following (i.e. $\mathcal{L}_1 \subseteq \mathcal{L}$)

$$ \mathcal{L}_1 = \begin{Bmatrix} \varvec{\alpha }, \hat{\varvec{\alpha }}, \varvec{x} \,|\, \exists x, r_x, \hat{x} \in \mathbb {Z}_q: \\ \hat{\varvec{\alpha }} \cdot x - [b]_1 \cdot \hat{x} =0 \ \mathbf{and } \ [1]_1 \cdot \hat{x} - \varvec{\alpha } \cdot x =0 \ \mathbf{and } \ \varvec{x} = \text{ com }(x; r_x) \end{Bmatrix} $$

since if $x\ne 0$ in $\mathcal{L}_1$, one can take $r = \hat{x}/x$, and otherwise $\varvec{x}$ is commitment to zero with $r_x$. Thus soundness of NIZK proof of $\mathcal{L}_1$ implies the tuple is in $\mathcal{L}$.

Now, consider another language $\mathcal{L}_2$,

$$ \mathcal{L}_2 = \begin{Bmatrix} \varvec{\alpha }, \hat{\varvec{\alpha }}, \varvec{x} \,|\, \exists r,x, r_x \in \mathbb {Z}_q: \\ ((\varvec{\alpha } = r[1]_1 \ \mathbf{and } \ \hat{\varvec{\alpha }} = r[b]_1) \ \mathbf{or } \ (x=0)) \ \mathbf{and } \ \varvec{x} = \text{ com }(x; r_x) \end{Bmatrix} $$

Thus, in the language the value $\varvec{x}$ is always a commitment to x under $r_x$. First note that $\mathcal{L}_2$ implies $\mathcal{L}_1$, i.e. $\mathcal{L}_2 \subseteq \mathcal{L}_1$. This is so because if $x=0$ in $\mathcal{L}_2$, then we just set $\hat{x}=0$ as well, and if there is a good r, then we set $\hat{x} = r \cdot x$.

Since the “designated” prover always knows x and $r_x$ in the commitment $\varvec{x}$, then if it has an (r, x) which satisfies the “or” part of $\mathcal{L}_2$, it can generate the witnesses required to satisfy membership in $\mathcal{L}_1$ and hence give a valid NIZK proof.

Under the SXDH assumption, $\mathcal{L}_1$ can be proved by using two group elements and in addition two elements for commitment to $\hat{x}$ (and not counting the two for $\varvec{x}$ which is commitment to x) using the technique by Escala and Groth in [EG14]. Namely, the size of $\pi _0$ is (2, 2). For this to work, we also need to sample public keys ${\mathsf { pk}}_1$ of ElGamal encryption (i.e. com) from $\mathbb {G}_2$. Furthermore, ${\mathsf { pk}}_1$ is taken from ${\textsc {crs}}^1$ (see Fig. 1). We note that this dependency of ${\mathsf { pk}}_1$ to ${\textsc {crs}}^1$ does not affect the security proof since we can use ciphertext with respect to ${\mathsf { pk}}_2$ when ${\textsc {crs}}^1$ is set to the simulation mode. We further optimize ${\mathsf {ct}}_z^1$ and ${\mathsf {ct}}_z^2$ by applying the common randomness technique from Sect. 3.3. With these modifications, ${\mathsf {ct}}_z^1$ and ${\mathsf {ct}}_z^2$ together consist of (0, 3) elements, and proof $\pi _1$ is a single element in $\mathbb {G}_2$ (rather than in $\mathbb {G}_1$ in the original construction). Other components, $\varvec{\rho }$, $\hat{\varvec{\rho }}$, $\gamma$, and $\pi _2$ are unchanged; each of them is represented by a single element in $\mathbb {G}_1$. In total, the proof size will be (6, 6). Under general $\mathcal{D}_k\text {-}{\textsc {mddh}}$ assumption, the optimized proof will consist of $(5k+1,4k+2)$ elements.

Finally we note that in the designated prover setting, the scheme $\varPi _1$ can be made $O(\log Q)$-reduction secure, while maintaining its structure-preserving property. Essentially we add an affine constant to $\gamma$ as done in [JOR18]. In the split-CRS QA-NIZK setting, this constant would only appear in the prover CRS. This still lets the security proof go through as the adversary’s view at the final game would be independent of this affine constant.

4.3 Designated Verifier Setting

As the most expensive part (from the size of USS-QA-NIZK perspective and applications) is the size of the “OR”-proof considered in our general construction, we now consider the designated-verifier setting [ES02]. In the designated-verifier setting of a NIZK, the CRS is split into two parts, $\textsc {crs}_p$ and $\textsc {crs}_v$, and only a designated-verifier gets access to $\textsc {crs}_v$ and the public information is only $\textsc {crs}_p$ (required by the prover). Alternatively, one can think of designated-verifier NIZKs as hash-proof systems, as the $\textsc {crs}_v$ is just the secret hash-key, and $\textsc {crs}_p$ is the projection hash-key – by the fact that hash-proofs can be generated without the witness (but using the secret hash-key), zero-knowledge is automatic; further, soundness is information-theoretic. Since hash-proofs for linear subspace languages are well known [CS98], and we even have hash-proofs for “OR”-languages [ABP15], so we have designated-verifier NIZK proofs for our “OR”-language used in the USS-QA-NIZK construction. Consequently, we have smaller sized (almost) tightly-secure designated-verifier USS-QA-NIZKs.

For this idea to work, we instantiate PKE in $\mathbb {G}_2$ in our construction so that the OR-language consists of relations from both $\mathbb {G}_1$ and $\mathbb {G}_2$. This allows us to use the hash proof system of [ABP15]. The downside of such a construction is that we have more $\mathbb {G}_2$ elements in the proof and the USS-QA-NIZK is itself in the target group $\mathbb {G}_T$, as the construction of [ABP15] generates hashes in the target group. Since these elements require much longer representation we give a more precise estimation. In the original construction of our USS-QA-NIZK with optimizations in Sect. 3.3, a proof consists of (11, 6) elements in the SXDH setting, of which (3, 6) are for proof $\pi _0$. In remaining (8, 0) elements, (4, 0) are the ciphertext of PKE and proof $\pi _1$. Moving the (4, 0) elements to $\mathbb {G}_2$ and replacing (3, 6) of $\pi _0$ with a target group element, the proof size of our designated-verifier USS-QA-NIZK will be (4, 4) source group elements and 1 target group element. Thus it saves (7, 2) elements in exchange of having an extra target group element. Since the target group element is computed from a product of four pairings, it can also be represented by randomized (4, 4) group elements by using the PPE randomization technique of [AFG+16]. However, either representation requires larger space than original (7, 2) elements. Thus, the known approach with [ABP15] does not seem to yield shorter proofs than our original construction in the designated verifier setting.

5 Applications

In this section, we demonstrate that our tightly secure USS-QA-NIZK can be used to develop CCA2-secure public key encryption and structure-preserving signatures (SPS). Besides being (almost) tightly secure under standard matrix assumptions in bilinear groups, these applications have particular advantage over previous constructions. Our CCA2-secure public-key encryption is publicly verifiable and our SPS scheme yields the shortest signatures. By plugging our CCA2-secure public key encryption and SPS into the generic frameworks of blind signatures [Fis06], group signatures [Gro07], and simulation-sound NIZKs [CCS09] we have blind SPS, group SPS, and simulation-sound Groth-Sahai proofs, all of which have (almost) tight reduction to standard matrix assumptions in bilinear groups and efficiency improvements over known schemes. Details for these plug-in applications are given in the full version of this paper.

5.1 (Almost) Tight CCA2-Secure PKE Scheme

In this section we show that the labelled (enhanced) USS-QANIZK for linear-subspaces can be used to build a publicly verifiable labeled CCA-secure public-key encryption (PKE) scheme (described in Fig. 6) which is (almost) tightly-secure in the multi-user, multi-challenge setting. The security reduction to USS-QANIZK is tight and is independent of the number of decryption-oracle requests of the CCA2 adversary.

Fig. 6.

CCA2 Public-Key Encryption using labelled (strong) USS-QA-NIZK.

Theorem 4

Under the $\mathcal{D}_k$-MDDH assumption, and using the labeled USS-QANIZK $\varPi '$ of Fig. 4, the public-key encryption scheme described in Fig. 6 is $(\mu , q_e)$ IND-CCA secure with Adversary’s advantage $\mathcal{{A}}$ upper-bounded by

$$\begin{aligned} 2 \cdot {\textsc {adv}}_{\varPi '}^{\mathsf {{tss}}} + 6k \cdot {\textsc {adv}}_{\mathcal{D}_k\text {-}{\textsc {mddh}}} + 2 \cdot {\textsc {adv}}_{\varPi '}^{\mathsf {{uss}}}(q_e) + O(1/q) . \end{aligned}$$

The proof of this theorem can be found in the full paper.

Remark. The public-key encryption construction in Fig. 6, during encryption, uses randomness to construct $\varvec{\rho }$. Then, it calls USS-QA-NIZK prover in a black-box manner to obtain $\pi$. The USS-QANIZK construction itself picks another and constructs its own $\varvec{\rho }$. We remark that in a non-black box construction of tight CCA2-secure public key encryption scheme, i.e. by utilizing the USS-QA-NIZK construction in a non-black fashion, one can use the same matrix in the PKE construction above and the USS-QANIZK construction, while keeping matrices sampled randomly and independently. This leads to a savings of k group elements. The proof of the (almost) tight security of this scheme combines the proof given in the full paper with the proof of the USS-QANIZK tight-security (Theorem 2).

5.2 Direct Construction of Tight SPS from Tight USS-QA-NIZK

Recall that unbounded simulation-soundness assures that, after having simulated proofs for any instances of adversary’s choice, it is hard for the adversary to find a valid proof for any fresh no-instances. This corresponds to the notion of unforgeability against adaptive chosen message attacks of a signature scheme where no adversary can find a valid signature for any fresh messages after seeing signatures for any chosen messages. Indeed, syntactically, an unbounded simulation-sound NIZK system can be seen as a signature scheme whose key generation, signature generation, and signature verification functions correspond to CRS simulation, proof simulation, and proof verification functions of the NIZK system, respectively. For this translation to work in reality, it is required that the NIZK system allows simulation for any no-instance in a certain set and there exists a collision resistant mapping (ideally injection) from the desired message space for the signature scheme to the set of no-instances. In [AAO18], this intuition is proven formally in a more general setting (allowing errors in correctness, etc). We use the simplest form of their result with adjustment to the syntax of USS-QA-NIZK.

Let $\varPi := (\mathsf {pargen}, {\mathsf {crsgen}}, \mathsf {prover}, \mathsf{{ver}}, {\mathsf {crssim}}, \mathsf{{sim}})$ be a designated prover USS-QANIZK system for with soundness advantage $\mathsf {Adv}^{\mathsf {uss}}_{ \varPi }(A)$. We assume that $\varPi$ is perfectly no-instance simulation correct with respect to which means that, for any $\textsc {crs}_v$ and ${\mathsf {trap}}$ generated by $\varPi .{\mathsf {crssim}}$, $y \in {\mathcal C}$, $\pi \leftarrow \varPi .\mathsf{{sim}}({{\mathsf {trap}}}, y )$, $1 \leftarrow \varPi .\mathsf{{ver}}({\textsc {crs}_v}, y , \pi )$ holds with probability 1.

Let denote a sampling where matrix is chosen uniformly with constraint that its upper square sub-matrix is full rank. For message space $\mathcal {M} := \mathbb {G}_1^{t}$ and $n \ge 2t+1$, we construct a function $H:\mathcal {M} \rightarrow {\mathcal C}$ as follows. Choose uniformly from $\mathbb {G}_1^{n-t}$. Then define $H( M )$ for $M \in \mathbb {G}_1^t$ as . For any and $M \in \mathbb {G}_1^t$, with probability at least $1-1/q$ over the choice of , there exists no x that satisfies . Thus H is an efficiently computable injection from $\mathcal {M}$ to ${\mathcal C}$. Following this idea, we construct a signature scheme as shown in Fig. 7.

Fig. 7.

Signature scheme $\mathsf {SIG}$ for unilateral messages in $\mathbb {G}_1^t$ based on USS-QA-NIZK $\varPi$ for a linear subspace language.

Fig. 8.

An SPS constructed directly by using the customized USS-QA-NIZK with designated prover (in Sect. 4.2) with optimizations from Sect. 3.3.

Theorem 5

With the above USS-QA-NIZK system $\varPi$, $\mathsf {SIG}$ in Fig. 7 is a signature scheme for message space $\mathcal {M} := \mathbb {G}_1^{t}$. It is tightly unforgeable against adaptive chosen message attacks, i.e., for every ppt adversary $\mathcal{{A}}$ breaking the unforgeability of $\mathsf {SIG}$ with a chosen message attack with advantage $\mathsf {Adv}_{\mathsf {SIG}}^{\mathsf {cma}}(\mathcal{{A}})$, there exists a ppt algorithm $\mathcal{B}$ that breaks the unbounded simulation soundness of $\varPi$ with advantage $\mathsf {Adv}_{ \varPi }^{\mathsf {uss}}(\mathcal{B}) \ge \mathsf {Adv}_{\mathsf {SIG}}^{\mathsf {cma}}(\mathcal{{A}}) - 1/q$ and almost the same running time as $\mathcal{{A}}$. Furthermore, if $\varPi$ is structure preserving, so is $\mathsf {SIG}$.

Proof

To show unforgeability, we construct $\mathcal {B}$ using $\mathcal {A}$ as black-box as follows. Given , $\mathcal {B}$ picks $c \leftarrow \mathbb {G}_1^{n-t}$ and send to $\mathcal {A}$. For message $M$ queried from $\mathcal {A}$, $\mathcal {B}$ sends to its oracle, receives a simulated proof $\pi$, and returns $\sigma := \pi$ to $\mathcal {A}$. Given a forgery $M ^*, \sigma _*$ from $\mathcal {A}$, $\mathcal {B}$ outputs and $\pi ^* := \sigma ^*$. Since is an injection to with probability at least $1-1/q$, is a fresh instance not in , and passes the verification whenever $\mathcal {A}$ succeeds. Hence we have $\mathsf {Adv}_{ \varPi }^{\mathsf {uss}}(\mathcal{B}) \ge \mathsf {Adv}_{\mathsf {SIG}}^{\mathsf {cma}}(\mathcal{{A}}) - 1/q$. Running time of $\mathcal {B}$ is the same as $\mathcal {A}$ except for performing concatenation and parsing. Structure-preserving property is obvious from the construction.

We remark that we can remove the negligible $1 \slash q$ term in the above bound in an enhanced model [LPJY15, JR13] where is given to the adversary playing the simulation soundness game.

In Fig. 8 we present an instantiation of $\mathsf {SIG}$ in Fig. 7 using our optimized designated prover USS-QA-NIZK from Sect. 4.2 under the SXDH assumption. Designated prover is sufficient in this application as the signing key is private. The signature size is exactly the same as the proof size of the underlying USS-QA-NIZK and it retains structure preserving property. Hence the signature scheme in Fig. 8 is an SPS scheme having signatures consisting of (6, 6) elements for unilateral messages. (Under $\mathcal{D}_k\text {-}{\textsc {mddh}}$ assumption, the signature size will be $(5k+1,4k+2)$). For bilateral messages $( M _1, M _2) \in \mathbb {G}^{t_1}_1 \times \mathbb {G}^{t_2}_2$ where $t_1 = t-1$, we follow a generic construction in [ACD+16, Sect. 6.3] that combines partially one-time signature for a part of messages in $\mathbb {G}_2$. It requires extra $(0,t_2)$ public-key elements, and the signature size increases by (1, 2) elements sacrificing one group element in the message space $\mathbb {G}_1^{t_1}$. A signature thus consists of (7, 8) elements for a bilateral message.