Mr NISC: Multiparty Reusable Non-Interac

In this section, we define and construct our new primitive: witness encryption (WE) for NIZK of commitments (for the complexity class $\mathrm {P} $), which is the main component for the construction of our mrNISC scheme.

As explained in Sect. 2.3, from a high-level point of view, WE for NIZK of commitments combines the properties of homomorphic proof commitments with encryption [20] and of functional commitments with witness selector [7]. Compared with the former, it supports general statements in $\mathrm {P} $ (instead of a single NAND gate evaluation). Compared with the latter, it allows for zero-knowledge to hold when multiple NIZK proofs are generated.

3.1 Definition of Witness Encryption for NIZK of Commitments

We start by defining dual-mode commitment schemes (a.k.a., hybrid commitments [12]), where the CRS can be generated in two computationally indistinguishable ways: one yielding perfectly binding commitments and one yielding equivocal (a.k.a., simulatable or trapdoor) commitments. The term “dual-mode commitment” comes from [32].

We may not need dual-mode commitments to construct mrNISC, but just simulatable/equivocal commitments (without a perfectly binding setup). However using dual-mode commitments significantly simplifies definitions and proofs. Since our constructions achieve this stronger security notion, we use it. More precisely, without a dual-mode commitment, we could not use the standard definition of witness encryption: witness encryption indeed just ensures that ciphertexts related to a false statement (about the committed value, in our setting) cannot be decrypted. Without the dual mode, because of equivocality of the commitments, it would be possible to open any commitment to any value. Hence any statement about a committed value would be always true or always false (independently of the committed value).

Definition 4

(Dual-Mode Commitments). A (dual-mode) commitment scheme $\mathsf {COM}$ has a binding mode and a simulation mode, each involves three polynomial-time algorithms.

Binding Setup: $\mathsf {crs}\leftarrow \mathsf {CSetup}_{\mathsf {bind}}(1^\lambda )$ on input the security parameter $\lambda $ generates a binding CRS $\mathsf {crs}$.
Commitment: $(c,d) \leftarrow \mathsf {CCom}(\mathsf {crs},v)$ on input the CRS $\mathsf {crs}$ and a message $v$ in some implicitly defined message set $\mathcal {V}$,^{Footnote 1} generates a commitment $c$ of $v$ and an associated decommitment (a.k.a., opening) $d$.
Verification: on input the CRS $\mathsf {crs}$, a commitment $c$, a message $v\in \mathcal {V}$, and a decommitment $d$, outputs 1 if $c$ indeed commits to $v$, and 0 otherwise.
Simulation Setup: $(\mathsf {crs}, \tau ) \leftarrow \mathsf {CSetup}_{\mathsf {sim}}(1^\lambda )$ on input the security parameter $\lambda $ generates a simulation CRS $\mathsf {crs}$ and an associated trapdoor $\tau $.
Commitment Simulation: $(c,\mathsf {aux}) \leftarrow \mathsf {CSimCom}(\tau )$ on input a simulation trapdoor $\tau $, generates a simulated commitment $c$ and some auxiliary data $\mathsf {aux}$.
Opening Simulation: $d\leftarrow \mathsf {CSimOpen}(\tau ,\mathsf {aux},v)$ on input an auxiliary data $\mathsf {aux}$ and a message $v\in \mathcal {V}$, generates some decommitment $d$ corresponding to an opening of the associated commitment $c$ to $v$.

satisfying the following properties:

Perfect Correctness: For every security parameter $\lambda \in \mathbb {N}$, CRS $\mathsf {crs}\leftarrow \mathsf {CSetup}_{\mathsf {bind}}(1^\lambda )$ or $(\mathsf {crs},\tau ) \leftarrow \mathsf {CSetup}_{\mathsf {sim}}(1^\lambda )$, message $v\in \mathcal {V}$, and commitment $(c,d) \leftarrow \mathsf {CCom}(\mathsf {crs},v)$, we have: $\mathsf {CVer}(\mathsf {crs},c,v,d) = 1$.
Setup Indistinguishability: The following two distributions are computationally indistinguishable:
$$\begin{aligned} {\left\{ \mathsf {crs}\leftarrow \mathsf {CSetup}_{\mathsf {bind}}(1^\lambda ) \ : \ \mathsf {crs}\right\} }_{\lambda } \approx {\left\{ (\mathsf {crs},\tau ) \leftarrow \mathsf {CSetup}_{\mathsf {sim}}(1^\lambda ) \ : \ \mathsf {crs}\right\} }_{\lambda } . \end{aligned}$$
Perfect Binding in Binding Mode: For every security parameter $\lambda \in \mathbb {N}$, binding CRS $\mathsf {crs}\leftarrow \mathsf {CSetup}_{\mathsf {bind}}(1^\lambda )$, message $v\in \mathcal {V}$, commitment $(c,d) \leftarrow \mathsf {CCom}(\mathsf {crs},v)$, message $v' \in \mathcal {V}$, bitstring $d'$, if $v' \ne v$: $\mathsf {CVer}(\mathsf {crs},c,v',d') = 0$.
Perfect Equivocality in Simulation Mode: For every security parameter $\lambda \in \mathbb {N}$, simulation CRS $(\mathsf {crs}, \tau ) \leftarrow \mathsf {CSetup}_{\mathsf {sim}}(1^\lambda )$, message $v\in \mathcal {V}$, the following two distributions are identical:
$$\begin{aligned} \left\{ (c,d) \leftarrow \mathsf {CCom}(\mathsf {crs},v) \ : \ (c,d) \right\} , \\ \left\{ (c,\mathsf {aux}) \leftarrow \mathsf {CSimCom}(\tau ),\; d\leftarrow \mathsf {CSimOpen}(\tau ,\mathsf {aux},v)\ : \ (c,d) \right\} . \end{aligned}$$

We are interested in proving statements “in zero-knowledge” of the form: “$c$ commits to some value $v$ such that $G(v) = y$,” where $G$ is a circuit in some circuit class $\mathcal {G}$ and $y$ is the expected output of the function. In our construction, the trapdoor of the NIZK will actually be the trapdoor of the commitment. That is why we cannot easily rely on a generic definition of NIZK and instead introduce the notion of dual-mode NIZK of commitments. The binding setup yields perfectly sound NIZK proofs, while the simulation setup yields zero-knowledge proofs.

Definition 5

(Dual-Mode NIZK of Commitments). Let $\mathsf {COM}$ be as in Definition 4, and $\mathcal {G}$ be a class of polynomial-size circuits. A dual-mode NIZK $\mathsf {NIZK}$ associated with $\mathsf {COM}$ for $\mathcal {G}$ consists of two polynomial-time algorithms:

Proof: $\pi \leftarrow \mathsf {CProve}(\mathsf {crs},c,G,v,d)$ on input the CRS $\mathsf {crs}$, a commitment $c$, a circuit $G\in \mathcal {G}$,^{Footnote 2} the committed message $v\in \mathcal {V}$, the decommitment $d$, as defined by $\mathsf {COM}$, generates a proof $\pi $ that G on input the value v committed in $c$ outputs $y = G(v)$. Refer to (c, G, y) as the statement and (v, d) the witness.
Proof Verification: on input the CRS $\mathsf {crs}$, a statement (c, G, y), and a proof $\pi $, accepts or rejects the proof.

The algorithms satisfy the following properties:

Perfect Proof Correctness: For every security parameter $\lambda \in \mathbb {N}$, CRS $\mathsf {crs}\leftarrow \mathsf {CSetup}_{\mathsf {bind}}(1^\lambda )$ or $(\mathsf {crs},\tau ) \leftarrow \mathsf {CSetup}_{\mathsf {sim}}(1^\lambda )$, message $v\in \mathcal {V}$, circuit $G\in \mathcal {G}$, commitment $(c,d) \leftarrow \mathsf {CCom}(\mathsf {crs},v)$ and proof $\pi \leftarrow \mathsf {CProve}(\mathsf {crs},c,G,v,d)$, we have: $\mathsf {CPVer}(\mathsf {crs},c,G(v),\pi ) = 1$.
Perfect Soundness in Binding Mode: For every security parameter $\lambda \in \mathbb {N}$, binding CRS $\mathsf {crs}\leftarrow \mathsf {CSetup}_{\mathsf {bind}}(1^\lambda )$, message $v\in \mathcal {V}$, commitment $(c,d) \leftarrow \mathsf {CCom}(\mathsf {crs},v)$, circuit $G\in \mathcal {G}$, incorrect output $y' \ne G(v)$, and bitstring $\pi $, $\mathsf {CPVer}(\mathsf {crs},c,y',\pi ) = 0$.
Zero-Knowledge in Simulation Mode: There exists a PPT simulator algorithm $\mathsf {CPSim}$, such that for any PPT adversary $\mathcal {A}$, the quantity is negligible in $\lambda $:
$$\begin{aligned} \Bigg | \Pr \left[ \begin{array}{l} (\mathsf {crs},\tau ) \leftarrow \mathsf {CSetup}_{\mathsf {sim}}(1^\lambda ),\; (\mathsf {st},v) \leftarrow \mathcal {A}(\mathsf {crs},\tau ),\\ (c,\mathsf {aux}) \leftarrow \mathsf {CSimCom}(\tau ),\; d\leftarrow \mathsf {CSimOpen}(\tau ,\mathsf {aux},v) \end{array} \ : \ \mathcal {A}^{\mathsf {Prove}}(\mathsf {st}) = 1 \right] \\ - \Pr \left[ \begin{array}{l} (\mathsf {crs},\tau ) \leftarrow \mathsf {CSetup}_{\mathsf {sim}}(1^\lambda ),\; (\mathsf {st},v) \leftarrow \mathcal {A}(\mathsf {crs},\tau ),\\ (c,\mathsf {aux}) \leftarrow \mathsf {CSimCom}(\tau ) \end{array} \ : \ \mathcal {A}^{\mathsf {Sim}}(\mathsf {st}) = 1 \right] \Bigg | , \end{aligned}$$
where and .

We remark that our notion of zero-knowledge allows the adversary to see the trapdoor $\tau $ but not the auxiliary data $\mathsf {aux}$, that is why we let the adversary consider a single simulated commitment but as many simulated proofs as it wants. The reason that $\mathsf {aux}$ is not given to the adversary is because we need to store a PRF key in $\mathsf {aux}$, to generate the randomness for simulation, to be sure to use the same randomness if the simulation is called twice with the same circuit $G$ in the construction for $\mathrm {P}$.

Definition 6

(Witness Encryption for NIZK of Commitments). Let $\mathsf {COM}$, $\mathsf {NIZK}$, and $\mathcal {G}$ be as in Definition 4 and 5. A Witness Encryption $\mathsf {WE}$ associated with $\mathsf {COM}, \mathsf {NIZK}$ for $\mathcal {G}$ consists of two polynomial-time algorithms:

Witness Encryption: $\mathsf {ct}\leftarrow \mathsf {CWEnc}(\mathsf {crs},c,G,y,\mathsf {m})$ on input the CRS $\mathsf {crs}$, a statement $(c,G,y)$ where $G\in \mathcal {G}$, and a bitstring $\mathsf {m}$, encrypts $\mathsf {m}$ into a ciphertext $\mathsf {ct}$, under that statement.
Witness Decryption: on input the CRS $\mathsf {crs}$, a ciphertext $\mathsf {ct}$, a statement $(c,G,y)$, and a NIZK proof $\pi $, decrypts $\mathsf {ct}$ into the message $\mathsf {m}$, or outputs $\bot $.

The algorithms satisfy the following properties:

Perfect Encryption Correctness: For every $\lambda \in \mathbb {N}$, CRS $\mathsf {crs}\leftarrow \mathsf {CSetup}_{\mathsf {bind}}(1^\lambda )$ or $(\mathsf {crs},\tau ) \leftarrow \mathsf {CSetup}_{\mathsf {sim}}(1^\lambda )$, message $v\in \mathcal {V}$, circuit $G\in \mathcal {G}$, commitment $(c,d) \leftarrow \mathsf {CCom}(\mathsf {crs},v)$ and proof $\pi \leftarrow \mathsf {CProve}(\mathsf {crs},c,G,v,d)$, bitstring $\mathsf {m}$, and ciphertext $\mathsf {ct}\leftarrow \mathsf {CWEnc}(\mathsf {crs},c,G,G(v),\mathsf {m})$, we have: $\mathsf {CWDec}(\mathsf {crs},\mathsf {ct},c,G,G(v),\pi ) = \mathsf {m}$.
Semantic Security: For any PPT adversary $\mathcal {A}$, the following is negligible in $\lambda $:
where $\rho $ denotes the random tape used by $\mathsf {CCom}$ to generate the commitment $c$ of the message $v$ ($\rho $ is provided by the adversary).

We remark that semantic security of our WE holds even when the binding CRS is generated semi-maliciously, i.e., the adversary chooses the random tape $\rho '$. This is important for our semi-malicious construction of mrNISC schemes, as the adversary generates itself the binding CRS. We also note that our construction for $\mathrm {NC}^1$ actually achieves perfect semantic security for binding CRS, however, our transformation from $\mathrm {NC}^1$ to $\mathrm {P}$ only achieves computational semantic security.

3.2 Bilinear Commitments with Proofs of Quadratic Relations

As a tool to construct witness encryption for NIZK of commitments, we first introduce the notion of bilinear commitments with proofs of quadratic relations. Such commitments essentially allow to “prove linearly and in a strong form of zero-knowledge” that one commitment $c_\times $ commits to the product of the values committed by two commitments $c_1$ and $c_2$ (quadratic proofs), and that one commitment $c_+$ commits to some linear combination of the values committed by two commitments $c_1$ and $c_2$ (linear proofs). These proofs are amenable to be verified by hash proof systems and can be combined to construct WE for NIZK of commitments.

Bilinear Groups and Notations. Denote by $(p,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_t,e,g_1,g_2)$ a bilinear group where $e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_t$ is an efficiently computable bilinear map (called a pairing) such that $e(g_1,g_2)=g_T$ generates $\mathbb {G}_t$. We use the bracket notation to denote the element $g_\iota ^a$ in group $\mathbb {G}_\iota $ for $a \in \mathbb {Z}_p$ and write as applying group exponentiation in $\mathbb {G}_\iota $ and as applying the pairing operation. This notation extends to vectors and matrices. We assume the Symmetric External Diffie-Hellman assumption ( $\mathsf {SXDH}$ ) assumption over asymmetric bilinear pairing groups, which requires the Decisional Diffie-Hellman ($\mathsf {DDH}$) assumption to hold in each source group $\mathbb {G}_1$ and $\mathbb {G}_2$, namely, for any $\iota \in {\{1,2\}}$, , where r, s, t are random scalars sampled from $\mathbb {Z}_p$. All vectors are denoted by bold letters and all matrices are denoted by uppercase letters.

Bilinear Commitments. Our construction starts from the SXDH-based commitment scheme used in Groth-Sahai NIZK [26]. This commitment scheme allows to commit values both in $\mathbb {G}_1$ and $\mathbb {G}_2$. The resulting commitments are dual-mode and called type-1 and type-2 commitments respectively. More formally we define:

Binding Setup: $\mathsf {crs}\leftarrow \mathsf {QSetup}_{\mathsf {bind}}(1^\lambda )$ generates a bilinear group $(p,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_t,e,g_1,g_2)$, and for $\iota \in \{1,2\}$, generates a random matrix $A_\iota \in \mathbb {Z}_p^{2 \times 2}$ of rank 1 such that the vector is not in the column span of $A_\iota $, and outputs .
Simulation Setup: $(\mathsf {crs}, \tau ) \leftarrow \mathsf {QSetup}_{\mathsf {sim}}(1^\lambda )$ is identical to binding setup except that $A_1$ and $A_2$ are chosen of rank 2. The trapdoor is $\tau = (A_1, A_2)$. Note that $\varvec{1}$ is in the column spans of $A_1$ and $A_2$.
Commitment: $(\varvec{c},\varvec{d}) \leftarrow \mathsf {QCom}_\iota (\mathsf {crs},v)$ generates a type-$\iota $ commitment of a message as follows:
Verification: checks whether $\varvec{c}$ is a valid type-$\iota $ commitment of $v$ as follows: it returns 1 if and only if:
Commitment Simulation: $(\varvec{c},\varvec{\mathsf {aux}}) \leftarrow \mathsf {QSimCom}_\iota (\tau )$ simulates a type-$\iota $ commitment as follows:
Opening Simulation: $\varvec{d}\leftarrow \mathsf {QSimOpen}_\iota (\tau =(A_1,A_2),\varvec{\mathsf {aux}},v)$ opens the type-$\iota $ commitment corresponding to $\varvec{\mathsf {aux}}$ as follows:

We have the following lemma following directly from [26].

Lemma 2

(in [26]). The two commitment schemes $(\mathsf {QSetup}_{\mathsf {bind}},\mathsf {QCom}_\iota ,\mathsf {QVer}_\iota ,\mathsf {QSetup}_{\mathsf {sim}},\mathsf {QSimCom}_\iota ,\mathsf {QSimOpen}_\iota )$ (for $\iota \in \{1,2\}$) described above are both dual-mode commitments.

Remark 1

Jumping ahead, for semi-malicious security of mrNISC in the plain model, we want the binding of $\mathsf {COM}$, soundness of NIZK, and semantic security of WE to hold against every CRS in the support of $\mathsf {QSetup}_{\mathsf {bind}}$. This boils down to ensuring that the bilinear group generated by $\mathsf {QSetup}_{\mathsf {bind}}$ is always a valid one: p must be a prime number, $g_1,g_2$ generates the cyclic groups $\mathbb {G}_1$ and $\mathbb {G}_2$ of order p, and it is possible to check in polynomial time whether an element is in $\mathbb {G}_1$ or $\mathbb {G}_2$. This can be done, and we implicitly assume that this is the case.

Bilinear Commitments with Proofs of Linear Relations. We now show how to prove that a type-2 commitment $\varvec{c}_+$ commits to a given linear combination of values committed in two type-2 commitments $\varvec{c}_1$ and $\varvec{c}_2$. Concretely, we want to prove that $\varvec{c}_1,\varvec{c}_2,\varvec{c}_+$ respectively commit to values $v_1,v_2,v_+$ that satisfy the linear relation: $ v_+ = \mu _1 v_1 + \mu _2 v_2$, where $\mu _1,\mu _2 \in \mathbb {Z}_p$ are some public parameters.

$$\begin{aligned} \text {Statement: } (\mathsf {Linear}, \mathsf {crs}, {\{\mu _i,\varvec{c}_i\}}_{i \in {\{1, 2\}}}, \varvec{c}_+),\qquad \text {Witness: } (v_1,\varvec{d}_1,v_2,\varvec{d}_2,\varvec{d}_+) \end{aligned}$$

The main idea of the construction is to remark that the commitments are linearly homomorphic and the above statement is equivalent to proving that is a commitment of 0, where for $i \in \{1,2,+\}$, . Hence the proof $\varvec{\pi }_+$ is the opening of this commitment to the value $v = 0$:

Zero-knowledge comes from the fact that this value $\varvec{\pi }_+$ always exists and is unique in the simulation mode, as the matrix $A_2$ is full rank in that mode.

Formally, the construction is as follows:

Linear Proof: $\mathsf {QLinProve}(\mathsf {crs},{\{\mu _i,\varvec{c}_i,v_i,\varvec{d}_i\}}_{i\in [2]}, (\varvec{c}_+,\varvec{d}_+))$, given information of both statement and witness, outputs:
Linear Proof Verification: $\mathsf {QLinVer}(\mathsf {crs},{\{\mu _i,\varvec{c}_i\}}_{i\in [2]},\varvec{c}_+,\varvec{\pi }_+)$ returns 1 iff:
where for $i \in {\{1,2,+\}}$.

Lemma 3

For any security parameter $\lambda \in \mathbb {N}$, for any CRS $\mathsf {crs}\leftarrow \mathsf {QSetup}_{\mathsf {bind}}(1^\lambda )$ or $(\mathsf {crs},\tau ) \leftarrow \mathsf {QSetup}_{\mathsf {sim}}(1^\lambda )$, messages $v_1,v_2,v_+ \in \mathbb {Z}_p$, scalars $\mu _1,\mu _2,\mu _+ \in \mathbb {Z}_p$, bitstrings $\varvec{c}_1,\varvec{d}_1,\varvec{c}_2,\varvec{d}_2,\varvec{c}_+,\varvec{d}_+$ s.t. $\forall i\in \{1,2,+\}, \mathsf {QVer}_2(\mathsf {crs},\varvec{c}_i,v_i,\varvec{d}_i) = 1$,

Perfect Correctness: If $v_+ = \mu _1 v_1 + \mu _2 v_2$, a proof $\pi _+ \leftarrow \mathsf {QLinProve}(\mathsf {crs},\{\mu _i,\varvec{c}_i,v_i,\varvec{d}_i\}_{i}, (\varvec{c}_+,\varvec{d}_+))$ passes verification: $\mathsf {QLinVer}(\mathsf {crs},{\{\mu _i,\varvec{c}_i\}}_{i \in [2]},\varvec{c}_+,\varvec{\pi }_+) = 1$
Perfect Uniqueness: If $v_+ = \mu _1 v_1 + \mu _2 v_2$ and the CRS is simulated, then there is a unique vector $\varvec{\pi }_+ = (\tilde{\varvec{c}}_+ - \mu _1 \tilde{\varvec{c}}_1 - \mu _2 \tilde{\varvec{c}}_2)A_2^{-1} \in \mathbb {Z}_p^2$ that passes verification.
Perfect Soundness: If $v_+ \ne \mu _1 v_1 + \mu _2 v_2$ and the CRS is binding, then no vector $\varvec{\pi }_+ \in \mathbb {Z}_p^2$ passes verification: $\mathsf {QLinVer}(\mathsf {crs},{\{\mu _i,\varvec{c}_i\}}_{i \in [2]},\varvec{c}_+,\varvec{\pi }_+) = 0$ for all $\varvec{\pi }_+ \in \mathbb {Z}_p^2$.

Proof

Perfect correctness is straightforward. Perfect uniqueness follows from Eq. (11) and the fact that when the CRS is simulated, the matrix $A_2$ is full rank. Perfect soundness comes from the fact that:

is a (perfectly binding) commitment of $\mu _1 v_1 + \mu _2 v_2 \ne v_+$. $\square $

Remark 2

(Zero-knowledge of the linear proof $\varvec{\pi }_+$ in simulation mode). Perfect uniqueness of the proof $\varvec{\pi }_+$ in simulation mode is a very strong form of witness indistinguishability: whatever witness $(v_1,\varvec{d}_1,v_2,\varvec{d}_2,\varvec{d}_+)$ is used, the proof is exactly the same $\varvec{\pi }_+ = (\tilde{\varvec{c}}_+ - \mu _1 \tilde{\varvec{c}}_1 - \mu _2 \tilde{\varvec{c}}_2)A_2^{-1}$. To show further that it is ZK, we need to argue that $\varvec{\pi }_+$ is also efficiently computable. This the case when the commitments are simulated with $\mathsf {QSimCom}$, as the simulator can then equivocate $\varvec{c}_1,\varvec{c}_2,\varvec{c}_+$ to any $v'_1,v'_2,v'_+$ satisfying $v'_+ = \mu _1 v'_1 + \mu _2 v'_2$ with decommitments $\varvec{d}'_1, \varvec{d}'_2, \varvec{d}'_+$ using $\mathsf {QSimOpen}$. This gives a valid witness $(v'_1,\varvec{d}'_1,v'_2,\varvec{d}'_2,\varvec{d}'_+)$ for the statement and a simulated proof can be generated by running the honest prover algorithm $\mathsf {QLinProve}$ with this witness.

Bilinear Commitments with Proofs of Quadratic Relations. We now show how to prove that a type-2 commitment $\varvec{c}_\times $ commits to the product of values committed in a type-1 commitment $\varvec{c}_1$ and a type-2 commitment $\varvec{c}_2$. Concretely, we want to prove that $\varvec{c}_1,\varvec{c}_2,\varvec{c}_+$ respectively commit to values $v_1,v_2,v_\times $ that satisfy the quadratic relation $v_\times = v_1 \cdot v_2$.

$$\begin{aligned} \text {Statement: } (\mathsf {Mult}, \mathsf {crs}, {\{\varvec{c}_i\}}_{i \in {\{1, 2, \times \}}}),\qquad \text {Witness:} (v_1,\varvec{d}_1,v_2,\varvec{d}_2,\varvec{d}_\times ) \end{aligned}$$

(12)

The main idea of the construction is to construct from and a commitment of $v_1\cdot v_2$. Remember that in the technical overview Sect. 2.3, we could multiply commitments $\varvec{c}_1$ and $\varvec{c}_2$ directly (by using a pairing operation) to get a commitment of $v_1 \cdot v_2$, as commitments were a single group element. Intuitively, the equivalent of this multiplication to vector of group elements $\varvec{c}_1$ and $\varvec{c}_2$ is the tensor product operation $\otimes $. And we want to prove that is a “commitment” of 0 in $\mathbb {G}_t$, where $\varvec{1}$ is used as a type-1 commitment of 1.^{Footnote 3} Similar to multiplication of commitments in Sect. 2.3, computing these tensor products uses pairings.

The basic idea is then that the proof is a decommitment of this commitment to 0. Unfortunately, this would not be zero-knowledge since there are multiple possible decommitments and choosing one may reveal information about the witness $(v_1,\varvec{d}_1,v_2,\varvec{d}_2,\varvec{d}_\times )$. To tackle this subtle issue (which does not happen with the commitments from the technical overview in Sect. 2.3 nor with proof of linear relations), the prover needs to rerandomize this decommitment, similarly to what is done in [26] to get perfect witness indistinguishability. This is the purpose of the vector $\varvec{\rho }$ in Eq. (14).

We first need to briefly recall the notion of tensor products. The tensor product of two matrices $M \in \mathbb {Z}_p^{k \times m}$ and $M' \in \mathbb {Z}_p^{k' \times m'}$ is the matrix $T = M \otimes M' \in \mathbb {Z}_p^{kk' \times mm'}$ defined as:

$$ T = \begin{pmatrix} M_{1,1} \cdot M' &{} \cdots &{} M_{1,m} \cdot M' \\ \vdots &{} &{} \vdots \\ M_{k,1} \cdot M' &{} \cdots &{} M_{k,m} \cdot M' \end{pmatrix}. $$

We extensively use the following identity: if $M \in \mathbb {Z}_p^{k \times m}$, $M' \in \mathbb {Z}_p^{k' \times m'}$, $N \in \mathbb {Z}_p^{m \times n}$ and $N' \in \mathbb {Z}_p^{m' \times n'}$, then we have,

$$\begin{aligned} (M \otimes M') \cdot (N \otimes N') = (M \cdot N) \otimes (M' \cdot N') . \end{aligned}$$

(13)

Recall that the construction essentially consists of proving that is a commitment of 0, which is what Eq. (15) below ensures. To better understand how this value is computed (in term of group elements, pairings, and exponentiations), we explicitly write it down:

The construction is as follows:

Quadratic Proof: $\varvec{\pi }_\times \leftarrow \mathsf {QQuadProve}(\mathsf {crs},{\{\varvec{c}_i,v_i,\varvec{d}_i\}}_{i \in [2]}, \varvec{c}_\times ,\varvec{d}_\times )$ picks $\varvec{\rho }\in \mathbb {Z}_p^4$ and outputs:
where $\mathsf {Id}\in \mathbb {Z}_p^{2 \times 2}$ is the identity matrix. Recall that the vector $\varvec{\rho }$ is used to randomize the proof so that it is uniformly random among the valid proofs, and hence is perfectly witness indistinguishable.
Quadratic Proof Verification: returns 1 if and only if:
where $\mathsf {Id}\in \mathbb {Z}_p^{2 \times 2}$ is the identity matrix. Note that computing involves pairing operations between elements of vectors $\varvec{c}_1 \in \mathbb {G}_1^2$ and $\varvec{c}_2 \in \mathbb {G}_2^2$. Computing the right hand side also involves pairing operations.

Remark 3

Quadratic proof verification just consists of checking a linear equation in $(\varvec{c}_2,\varvec{c}_\times ,\varvec{\pi }_\times )$. Indeed, thanks to Eq. (13), Eq. (15) is equivalent to:

Lemma 4

For any security parameter $\lambda \in \mathbb {N}$, for any CRS $\mathsf {crs}\leftarrow \mathsf {QSetup}_{\mathsf {bind}}(1^\lambda )$ or $(\mathsf {crs},\tau ) \leftarrow \mathsf {QSetup}_{\mathsf {sim}}(1^\lambda )$, messages $v_1,v_2,v_\times \in \mathbb {Z}_p$, bitstrings $\varvec{c}_1,\varvec{d}_1,\varvec{c}_2,\varvec{d}_2,\varvec{c}_\times ,\varvec{d}_\times $ such that $ \forall i\in \{1,2,\times \},\mathsf {QVer}_i(\mathsf {crs},\varvec{c}_i,v_i,\varvec{d}_i) = 1$, we have:

Perfect Correctness: If $v_\times = v_1 v_2$, a proof $\mathsf {QQuadProve}(\mathsf {crs},\{\varvec{c}_i,v_i,\varvec{d}_i\}_{i\in [2]}, (\varvec{c}_\times ,\varvec{d}_\times ))$ passes verification: $\mathsf {QQuadVer}(\mathsf {crs},{\{\mu _i,\varvec{c}_i\}}_{i \in [2]},\varvec{c}_\times ,\varvec{\pi }_\times ) = 1$
Perfect Uniformity: If $v_\times = v_1 v_2$ and the CRS is simulated, then the vector $\varvec{\pi }_\times $ generated by $\mathsf {QQuadProve}$ follows a uniform distribution among the solutions of Eq. (15).
Perfect Soundness: If $v_\times \ne v_1 v_2$ and the CRS is binding, then no $\varvec{\pi }_\times \in \mathbb {Z}_p^8$ passes verification: $\mathsf {QQuadVer}(\mathsf {crs},\varvec{c}_1,\varvec{c}_2,\varvec{c}_\times ,\varvec{\pi }_\times ) = 0$ for all $\varvec{\pi }_\times \in \mathbb {Z}_p^8$.

Proof

To prove perfect correctness, we use Eqs. (13) and (14) and remark:

$$\begin{aligned}&\varvec{1} \otimes \tilde{\varvec{c}}_\times - \tilde{\varvec{c}}_1 \otimes \tilde{\varvec{c}}_2 = \varvec{1} \otimes (A_2 \varvec{d}_\times + v_\times \cdot \varvec{1}) - \tilde{\varvec{c}}_1 \otimes (A_2 \varvec{d}_2 + v_2 \cdot \varvec{1}) \nonumber \\&= \varvec{1} \otimes (A_2 \varvec{d}_\times ) + v_\times \cdot \varvec{1} \otimes \varvec{1} - \tilde{\varvec{c}}_1 \otimes (A_2 \varvec{d}_2) - (A_1 \varvec{d}_1 + v_1 \cdot \varvec{1}) \otimes (v_2 \cdot \varvec{1}) \nonumber \\&= \varvec{1} \otimes (A_2 \varvec{d}_\times ) - \tilde{\varvec{c}}_1 \otimes (A_2 \varvec{d}_2) - (A_1 \varvec{d}_1) \otimes (v_2 \cdot \varvec{1}) + (v_\times - v_1 v_2) \cdot (\varvec{1} \otimes \varvec{1}) \nonumber \\&= (\mathsf {Id}\otimes A_2) \cdot (\varvec{1} \otimes \varvec{d}_\times ) - (\mathsf {Id}\otimes A_2) \cdot (\tilde{\varvec{c}}_1 \otimes \varvec{d}_2) \nonumber \\&\qquad \qquad - (A_1 \otimes \mathsf {Id}) \cdot (v_2 \varvec{d}_1 \otimes \varvec{1}) + (v_\times - v_1 v_2) \cdot (\varvec{1} \otimes \varvec{1}). \end{aligned}$$

(16)

We conclude by remarking that $v_\times = v_1 v_2$ and that:

Perfect soundness follows from Eq. (16) and the fact that $\varvec{1}\otimes \varvec{1}$ is not in the subspace generated by the columns of the matrix

when the CRS is binding, because if $\varvec{a}_1,\varvec{a}_2 \in \mathbb {Z}_p^2$ are two vectors generating the column space of $A_1$ and $A_2$ respectively, then $(\varvec{a}_1 \otimes \varvec{a}_2,\ \varvec{a}_1 \otimes \varvec{1},\ \varvec{1} \otimes \varvec{a}_2, \ \varvec{1} \otimes \varvec{1})$ is a basis of $\mathbb {Z}_p^4$.

Finally, perfect uniformity comes from the fact that the kernel of the matrix B (from Eq. (17)) consists of all the vectors:

$$ \begin{pmatrix} (\mathsf {Id}\otimes A_2) \cdot \varvec{\rho }\\ - (A_1 \otimes \mathsf {Id}) \cdot \varvec{\rho }\end{pmatrix}, $$

for $\varvec{\rho }\in \mathbb {Z}_p^4$, since these elements are clearly in the kernel and form a subspace of dimension 4, and the kernel is of dimension 4 as $B \in \mathbb {Z}_p^{8 \times 4}$ is of rank 4 (because $A_1$ is of full rank and hence $A_1 \otimes \mathsf {Id}\in \mathbb {Z}_p^{4 \times 4}$ is of full rank).

Remark 4

(Zero-knowledge of the quadratic proof $\varvec{\pi }_\times $ in simulation mode). Perfect uniformity in the simulation mode is a very strong form of witness indistinguishability: whatever witness is used, the proof follows exactly the same uniform distribution over solutions of Eq. 15. To show that $\varvec{\pi }_\times $ is zero-knowledge, it remains to argue that this distribution can be efficiently sampled. This can be done similarly as in Remark 2: for simulated commitments $\varvec{c}_i$, the simulator can equivocate $\varvec{c}_1,\varvec{c}_2,\varvec{c}_\times $ to any $ v'_1, v'_2, v'_\times $ satisfying $ v'_\times = v'_1 v'_2$ with decommitment $\varvec{d}'_1, \varvec{d}'_2, \varvec{d}'_\times $ using $\mathsf {QSimOpen}$. This gives a valid witness $(v'_1,\varvec{d}'_1,v'_2,\varvec{d}'_2,\varvec{d}'_\times )$ for the statement and a simulated proof can be generated by running the honest prover algorithm $\mathsf {QQuadProve}$ with this witness.

3.3 WE for NIZK of Commitments for $\mathrm {NC}^1$

We now describe our construction of WE for NIZK of commitments for $\mathrm {NC}^1$. It follows the technical overview Sect. 2.3. The idea is to represent the function by a Restricted Multiplication Straight-line (RMS) Program [10, 14], which only performs multiplications or quadratic operations between an intermediate variable and an input. We start with defining a variant of RMS where operations are done modulo some prime number p.

Definition 7

(RMS Programs). Let p be a prime. A Restricted Multiplication Straight-line (RMS) program modulo p with input $v = v_1 \Vert \cdots \Vert v_n\in {\{0,1\}}^n$ and output $y= y_1 \Vert \cdots \Vert y_m \in {\{0,1\}}^m$ is a sequence of the following instructions:

Load a constant $\omega \in \mathbb {Z}_p$ into the memory value $u_j$: $(u_j \leftarrow \omega )$.
Linearly combine memory values $u_i$ and $u_j$ into the memory value $u_k$: $(u_k \leftarrow \mu u_i + \mu ' u_j \bmod p)$, with $(\mu ,\mu ') \in \mathbb {Z}^2_p \setminus {\{(0,0)\}}$ a non-zero pair of constants.
Multiply the input value $v_i$ by the memory value $u_j$ into the memory value $u_k$: $(u_k \leftarrow v_i \cdot u_j \bmod p)$.

where each memory value is written at most once and each memory value that is read was written before. The program aborts if one memory value $u_k$ is not in ${\{0,1\}}$. If it does not abort, it outputs $y= y_1 \Vert \cdots \Vert y_m = u_1 \Vert \dots \Vert u_m$.

The size of an RMS is the number of instructions. Furthermore, any $\mathrm {NC}^1$ circuit $G$ can be written as an RMS program of polynomial size, because deterministic branching programs can be encoded into RMS with constant overhead [10, Claim A.2]. The resulting RMS program outputs the correct value when evaluated modulo any prime number p, as when evaluated without modulo, all the memory values are in ${\{0,1\}}$.

Construction. Let $\mathsf {QC}= (\mathsf {QSetup}_{\mathsf {bind}},\mathsf {QSetup}_{\mathsf {sim}},\{\mathsf {QCom}_i,\mathsf {QVer}_i,\mathsf {QSimCom}_i,$ ${\mathsf {QSimOpen}_i\}}_{i \in \{1,2\}},\mathsf {QQuadProve},\mathsf {QQuadVer})$ be the bilinear commitment scheme with proofs of quadratic relations from the previous section. We construct a witness encryption $\mathsf {WE}$ for NIZK of commitments for $\mathrm {NC}^1$ below. To help differentiate type-1 and type-2 commitments, all type-$\iota $ commitments have subscript starting with $\iota $, such as, $\varvec{c}_{\iota ,k}$.

Commitment: $(c,d) \leftarrow \mathsf {CCom}(\mathsf {crs},v)$ for , generates type-1 commitments for each bit of $v= v_1 \Vert \dots \Vert v_n$. More formally, $c= (\varvec{c}_{1,1},\dots ,\varvec{c}_{1,n}$ and $d= (\varvec{d}_{1,1},\dots ,\varvec{d}_{1,n})$, where for $i \in [n]$, $(\varvec{c}_{1,i},\varvec{d}_{1,i}) \leftarrow \mathsf {QCom}_1(\mathsf {crs},v_i)$.
Verification, Commitment Simulation and Opening: just consist in running the respective algorithms $\mathsf {QVer}_1,\mathsf {QSimCom}_1,\mathsf {QSimOpen}_1$ in parallel for each commitment $\varvec{c}_{1,i}$.
Proof $\pi \leftarrow \mathsf {CProve}(\mathsf {crs},c,G,v,d)$, for an $\mathrm {NC}^1$ circuit $G$ represented as an RMS program with n-bit input and m-bit output works as follows. Let $S_\omega $, $S_+$, and $S_\times $ be the sets of memory indexes written by constant loading, linear, and multiplication instructions respectively. We suppose that the used memory values are $u_1,\dots ,u_L$. The proof $\pi $ is a tuple $({\{\varvec{c}_{2,k}\}}_{k \in [L]}, {\{\varvec{d}_{2,k}\}}_{k \in [m] \cup S_\omega }, {\{\varvec{\pi }_{k}\}}_{k \in S_+ \cup S_\times })$ where these values are generated as follows, for each instruction
- $(u_k \leftarrow \omega )$: generate $(\varvec{c}_{2,k},\varvec{d}_{2,k}) \leftarrow \mathsf {QCom}_2(\mathsf {crs},\omega )$.
- $(u_k \leftarrow \mu u_i + \mu ' u_j \bmod p)$: compute
- $(u_k \leftarrow v_i \cdot u_j \bmod p)$: compute
  (Note that values $v_i$ and $u_j$ are known by the prover.)
Proof Verification: just consists in verifying the provided openings and quadratic proofs. More formally, $\mathsf {CPVer}(\mathsf {crs},c,G,y,\pi )$ where $y= y_1 \Vert \cdots \Vert y_m$ returns 1 if and only if all the following tests pass:
- For every $i \in [m]$, check that $\mathsf {QVer}_2(\mathsf {crs},\varvec{c}_{2,i},y_i,\varvec{d}_{2,i}) \overset{{}_{?}}{=}1$.
- For every instruction:
- * $(u_k \leftarrow \omega )$: check $\mathsf {QVer}_2(\mathsf {crs},\varvec{c}_{2,k},\omega ,\varvec{d}_{2,k}) \overset{{}_{?}}{=}1$.
- * $(u_k \leftarrow \mu u_i + \mu ' u_j \bmod p)$: check $ \mathsf {QLinVer}(\mathsf {crs},(\mu ,\varvec{c}_{2,i}),(\mu ',\varvec{c}_{2,j}),$ $\varvec{c}_{2,k},\varvec{\pi }_k) \overset{{}_{?}}{=}1$.
- * $(u_k \leftarrow v_i \cdot u_j \bmod p)$: check $\mathsf {QQuadVer}(\mathsf {crs},\varvec{c}_{1,i},\varvec{c}_{2,j},\varvec{c}_{2,k},\varvec{\pi }_k) \overset{{}_{?}}{=}1$.
Proof Simulation: $\pi \leftarrow \mathsf {CPSim}(\tau , \mathsf {aux}, c, G,y)$ where $c= (\varvec{c}_{1,1}, \dots , \varvec{c}_{1,n})$ are simulated with auxiliary data $\mathsf {aux}= (\varvec{\mathsf {aux}}_{1,1},\dots ,\varvec{\mathsf {aux}}_{1,n})$, simulates a proof $\pi = ({\{\varvec{c}_{2,k}\}}_{k \in [L]}, {\{\varvec{d}_{2,k}\}}_{k \in [m] \cup S_\omega }, {\{\varvec{\pi }_{k}\}}_{k \in S_+ \cup S_\times })$ as follows: Run through the instructions in RMS in order and for each instruction do:
- $(u_k \leftarrow \omega )$: generate
  $$\begin{aligned} (\varvec{c}_{2,k},\varvec{\mathsf {aux}}_{2,k})\leftarrow \mathsf {QSimCom}_2(\tau )~, \quad \varvec{d}_{2,k} \leftarrow \mathsf {QSimOpen}_2(\tau ,\varvec{\mathsf {aux}}_{2,k},\omega )~. \end{aligned}$$
- $(u_k \leftarrow \mu u_i + \mu ' u_j \bmod p)$: set if $k \in [m]$ or 0 otherwise, and let $u'_i,u'_j \in \mathbb {Z}_p$ be arbitrary scalars such that $\mu u'_i + \mu ' u'_j = u'_k$ (which is possible as $(\mu ,\mu ') \ne 0$), and compute:
  
  Note: values $u'_i$, $u'_j$, $u'_k$ are local and may be different for different instructions.
- $(u_k \leftarrow v_i \cdot u_j \bmod p)$: set is $k \in [m]$ or 0 otherwise, as well as and (so that $u'_k = u'_i u'_j$—again values $u'_i$, $u'_j$, $u'_k$ are local) and compute:
  $$\begin{aligned} (\varvec{c}_{2,k},\varvec{\mathsf {aux}}_{2,k})&\leftarrow \mathsf {QSimCom}_2(\tau ), \nonumber \\ \varvec{d}'_{1,i}&\leftarrow \mathsf {QSimOpen}_1(\tau ,\varvec{\mathsf {aux}}_{1,i},u'_i) \end{aligned}$$
  (19)
  
  $$\begin{aligned} \varvec{d}'_{2,\ell }&\leftarrow \mathsf {QSimOpen}_2(\tau ,\varvec{\mathsf {aux}}_{2,\ell },u'_\ell ) \quad \text {for } \ell \in \{j,k\}, \end{aligned}$$
  (20)
Witness Encryption: Looking at Eqs. (7) and (11) and Remark 3, we remark that the proof verification $\mathsf {CPVer}(\mathsf {crs},c,G,y,\pi )$ is affine in the vector $\pi $. Concretely, there exists a matrix and a vector (both only depend on $\mathsf {crs},c,G,y$ and can be efficiently computed from these three values—the star $\star $ denotes the fact that elements are not necessarily in the same group), such that, seeing $\pi $ as a vector of elements in $\mathbb {Z}_p,\mathbb {G}_1,\mathbb {G}_2$ of length $\beta $, and denoting by ${\tilde{\varvec{\pi }}} \in \mathbb {Z}_p^\beta $ the vector derived from $\pi $ by replacing every $\mathbb {G}_\iota $ element with its discrete logarithm, we have:
(Note: This is because: By Eq. 7and 11, verification of opening and verification of a linear proof are both linear equations whose coefficients are either constants or elements in $\mathsf {crs}$. By Remark 3, verification of a quadratic proof is a linear equation whose coefficients are constants, or elements in $\mathsf {crs}$, or commitments $\varvec{c}_{1,i}$ (as in Eq. 19) to the first operand in the multiplication. Since in RMS the first operand of multiplication is always an input bit, $\varvec{c}_{1,i}$ is contained in $c$.) The witness encryption then just uses hash proof systems from [1]. More formally, to encrypt a bit message $\mathsf {m}\in {\{0,1\}}$, $\mathsf {CWEnc}(\mathsf {crs},c,G,y,\mathsf {m})$ picks a uniformly random row vector $\varvec{\alpha }\in \mathbb {Z}_p^{1\times \nu }$, where $\nu $ is the number of rows of $\varGamma _{\mathsf {crs},c,G,y}$, and outputs the ciphertext where:
Witness Decryption: Using the notation from witness encryption, $\mathsf {CWDec}(\mathsf {crs},\mathsf {ct},c,G,y,\pi )$ outputs $\mathsf {m}\in {\{0,1\}}$ satisfying

The algorithms $\mathsf {CSetup}_{\mathsf {bind}},\mathsf {CCom},\mathsf {CVer}$ (as well as the simulators $\mathsf {CSetup}_{\mathsf {sim}},\mathsf {CSimCom},\mathsf {CSimOpen}$) of the resulting WE for NIZK of commitments run in time polynomial in their inputs. The algorithms $\mathsf {CProve},\mathsf {CPVer},\mathsf {CWEnc},\mathsf {CWDec}$ run in time polynomial in their inputs and exponential in the depth of the circuit $G$. This exponential blow up is due to the representation by a RMS program and explains the restriction to $\mathrm {NC}^1$.

Theorem 8

Assuming SXDH over bilinear groups. The construction $\varPi $ described above is a WE for NIZK of commitments for $\mathrm {NC}^1$.

Proof

Perfect correctness of the commitment, setup indistinguishability, perfect binding, and perfect equivocality follow directly from the fact that $(\mathsf {QSetup}_{\mathsf {bind}},\mathsf {QSetup}_{\mathsf {sim}},\mathsf {QCom}_1,\mathsf {QVer}_1,\mathsf {QSimCom}_1,\mathsf {QSimOpen}_1)$ is a dual-mode commitment scheme. Perfect proof correctness follows from perfect correctness of linear and quadratic proofs. Perfect soundness follows from perfect binding of type-1 and type-2 commitments as well as perfect soundness of linear and quadratic proofs. Perfect encryption correctness and perfect semantic security follow immediately from correctness and smoothness of the hash proof systems in [1]. It remains to prove the perfect zero-knowledge property. This is where the uniqueness of linear proofs (Remark 2) and the perfect uniformity (Remark 4) of the quadratic proofs are used. We give a proof by games:

Game 0 corresponds to the zero-knowledge game where proofs are honestly generated.
Game 1 is similar to Game 0 except that all the commitments are simulated but still opened to the value a real prover would use. This game is perfectly indistinguishable from the previous one by perfect equivocality of type-1 and type-2 commitments.
Game 2 is similar to Game 1, except that the decommitments $\varvec{d}_{2,k}$ for $k \in (S_+ \cup S_\times ) \setminus [m]$ (i.e., the ones which are not published) and $\varvec{d}'_{\star ,\star }$ used to generate the linear and quadratic proofs (see Eqs. (18) to (20)) are generated as by $\mathsf {CPSim}$. By perfect equivocality of type-1 and type-2 commitments, these values $\varvec{d}_{2,k}$ and $\varvec{d}'_{\star ,\star }$ are valid decommitments. Hence by uniqueness of linear proofs and perfect uniformity of quadratic proofs, the resulting proofs $\varvec{\pi }_k$ are perfectly indistinguishable between Game 1 and Game 2.

As Game 2 corresponds to the zero-knowledge game where proofs are simulated, this conclude the proof of perfect zero-knowledge. $\square $

Mr NISC: Multiparty Reusable Non-Interactive Secure Computation | Springer Nature Link

3.1 Definition of Witness Encryption for NIZK of Commitments

Definition 4

Definition 5

Definition 6

3.2 Bilinear Commitments with Proofs of Quadratic Relations

Lemma 2

Remark 1

Lemma 3

Proof

Remark 2

Remark 3

Lemma 4

Proof

Remark 4

3.3 WE for NIZK of Commitments for \(\mathrm {NC}^1\)

Definition 7

Theorem 8

Proof