CDS Composition of Multi-round Protocols

Abstract

We revisit the Cramer, Damgård, Schoenmakers (CDS) approach for composing sigma protocols, and adapt it to a setting in which the underlying protocols have multiple rounds of interaction. The goal of CDS composition is to prove compound NP-relations by combining multiple “atomic” proof systems. Its key feature is that it interacts with the atomic proofs in a generic fashion, enabling simpler and more efficient implementation.

Recent developments in multi-round protocols call for the adaptation of CDS composition beyond its original scope, which not only was restricted to three-move protocols but in fact fails in the multi-round case, as well as in the composition of so-called k-special sound proofs.

We propose a new method for multi-round composition in the plain model, in a soundness preserving way and with an “offline” zero-knowledge simulation property. The need for handling arbitrary monotone access structures in $\textsf{mNC}^1$, which is all Boolean function families represented by polynomial-size formulas over some fixed complete basis, leads us to identify a complexity theoretic problem of independent interest.

Prior to our work, multi-round composition was either restricted to the random oracle model, or worked only for argument systems, and moreover required heavy “online” zero-knowledge simulation.

A Dual-Mode Commitment Scheme from DDH

This section presents an instantiation of a dual-mode commitment scheme associated with a $\mathsf {\varSigma }$-protocol for proving correct generation of a binding key. We first describe the dual-mode commitment scheme taken from [38] with a modification that the prover generates the public parameters, $(\mathbb {G}, q, g)$, and chooses a random generator h by itself while they are given as a common reference string in [38]. This results in losing the original computational binding property in the hiding mode, which we do not need in our construction. It is noted that it does not spoil the computational hiding property in the binding mode as well as the mode indistinguishability where the adversary is the verifier. We instantiate $\textsf{dmCom}= \{\ensuremath {\textsf{CGen}_{\textsf{BIND}}}, \ensuremath {\textsf{CGen}_{\textsf{HIDE}}}, \ensuremath {\textsf{Com}}, \ensuremath {\textsf{Eqv}}\}$ as follows:

• $\ensuremath {\textsf{CGen}_{\textsf{BIND}}}(\ensuremath {1^\ensuremath {\lambda }})\rightarrow \ensuremath {\textsf{ck}}$: Run $(\mathbb {G}, q, g) \leftarrow \mathcal{G}(\ensuremath {1^\ensuremath {\lambda }})$. Choose , and . Compute $u = g^{\rho _1}$ and $v = g^{\rho _2}$, and output $\ensuremath {\textsf{ck}}:=(\mathbb {G}, q, g, h, u, v)$.

• $\ensuremath {\textsf{CGen}_{\textsf{HIDE}}}(\ensuremath {1^\ensuremath {\lambda }})\rightarrow (\ensuremath {\textsf{ck}},\ensuremath {\textsf{td}})$: As above, except for choosing , and computing $u = g^{\rho }$, and $v = h^{\rho }$. Output $\ensuremath {\textsf{ck}}: = (\mathbb {G}, q, g, h, u, v)$, and $\ensuremath {\textsf{td}}:= \rho$.

• $\ensuremath {\textsf{Com}}_\ensuremath {\textsf{ck}}(m;r) \rightarrow \ensuremath {\textsf{com}}$: Choose and compute $a = g^r / u^m$ and $b = h^r / v^m$. Output $\ensuremath {\textsf{com}}:= (a, b)$.

• $\ensuremath {\textsf{Eqv}}_\ensuremath {\textsf{td}}(\ensuremath {\textsf{com}},\ensuremath {\textsf{ck}}, m', r', m)\rightarrow r$: Take $\rho$ from $\ensuremath {\textsf{td}}$ and output $r := (r' - \rho m') + \rho m$.

Theorem 10

The above $\textsf{dmCom}$ is a dual-mode commitment scheme. It is perfectly binding in the binding mode, and equivocal in the hiding mode. It is mode indistinguishable and computationally hiding in the binding mode under the decision Diffie-Hellman assumption relative to $\mathcal G$.

Proof

For a commitment, (a, b), let $\tilde{a} := \log _g a$, $\tilde{b} := \log _h b$ and $x := \log _g h$. We first show that $\textsf{dmCom}$ is perfectly binding in the binding mode. From $a = g^r / u^m$ and $b = h^r / v^m$, we have $\tilde{a} = r + \rho _1 m$ and $\tilde{b} = r + \rho _2 m$. Since $\rho _1 \ne \rho _2$, they determine $m \in \ensuremath {\mathbb {Z}}_q$ uniquely by $m = (\tilde{a} - \tilde{b}) / (\rho _1 - \rho _2)$. To show that commitments are computationally hiding in the binding mode under the DDH assumption, consider two distributions, C(m) and R, over variables (g, h, u, v, a, b) that (g, h, u, v) is generated by $\ensuremath {\textsf{CGen}_{\textsf{BIND}}}(\ensuremath {1^\ensuremath {\lambda }})$, and (a, b) for C(m) is generated by $\ensuremath {\textsf{Com}}_\ensuremath {\textsf{ck}}(m)$ with $\ensuremath {\textsf{ck}}: = (\mathbb {G}, q, g, h, u, v)$, and (a, b) for R is uniform over $\mathbb {G}^2$. We then set up the following hybrid. For a given DDH question $Q:=(g, g^r, h, h^{r'})$ and message m, let and $(a,b) := ((g^r) / u^m, (h^{r'}) / v^m)$. If Q is taken from the DDH distribution where $r=r'$, (g, h, u, v, a, b) is in C(m). On the other hand, if Q is taken from the random distribution where $r \ne r'$, (g, h, u, v, a, b) is in R. Thus, distinguishing C(m) and R is hard under the DDH assumption. For $m' (\ne m)$, $C(m')$ and R are indistinguishable for the same reason. Thus, for any m and $m'$, two distributions C(m) and $C(m')$ are indistinguishable under the DDH assumption.

We next show that $\textsf{dmCom}$ is perfectly hiding in the hiding mode. Since $u = g^{\rho }$ and $v = h^{\rho }$, we have $\tilde{a} = \tilde{b} = r - \rho m$. Thus, for any $m'$, there exists $r'$ that satisfies $\tilde{a} = \tilde{b} = r' - \rho m'$. Therefore, (r, m) is perfectly hiding.

Mode indistinguishability is directly from the DDH assumption. The quadruple (g, h, u, v) in a hiding key is in the DDH distribution, and the one in a binding key is in the uniform distribution. Thus, they are indistinguishable under the DDH assumption.

Finally, equivocality is verified by inspecting that $r' = (r - \rho m) + \rho m'$ satisfies $a = g^r / u^m = g^{r'} / u^{m'}$ and $b = h^r / v^m = h^{r'} / v^{m'}$.

   $\square$

We present a $\mathsf {\varSigma }$-protocol $\varPi ^{\textsf{bind}}$ for proving that $\ensuremath {\textsf{ck}}:=(\mathbb {G}, q, g, h, u, v)$ is a binding key. We assume that group generator $\mathcal{G}$ is transparent, i.e., $(\mathbb {G}, q, g) \in \mathcal{G}(\ensuremath {1^\ensuremath {\lambda }})$ can be verified publicly, and focus on the relation among (g, h, u, v). Concretely, the proof is for the following relation:

$$\begin{aligned} R^{\textsf{bind}} := \left\{ (\rho _1, \rho _2) \,|\, u = g^{\rho _1}\, \wedge \,v = h^{\rho _2} \, \wedge \, \rho _1 \ne \rho _2 \right\} . \end{aligned}$$

Inequality $\rho _1 \ne \rho _2$ is shown by checking $d_1^{(\rho _1 - \rho _2)} \ne 1_{\mathbb {G}}$ for a random generator $d_1$.

[ $\varPi ^{\textsf{bind}}$ : Proof of Binding Key]

• Prover’s private input is $(\rho _1, \rho _2)$, and the common input to the prover and verifier is $\ensuremath {\textsf{ck}}:=(\mathbb {G}, q, g, h, u, v)$.

• Prover computes , $d_2 := d_1^{(\rho _1 - \rho _2)}$, , $a_1 := g^{r_1}$, $a_2 := h^{r_2}$, $a_3 := d_1^{r_1 - r_2}$, and sends $(a_1, a_2, a_3, d_1, d_2)$ to the verifier.

• Verifier selects and send it to Prover.

• Prover computes $z_1 = r_1 - c\, \rho _1$, $z_2 = r_2 - c\, \rho _2$, and send $(z_1, z_2)$ to Verifier

• Verifier accepts if $a_1 = g^{z_1} u^{c}$, $a_2 = h^{z_2} v^{c}$, $a_3 = d_1^{z_1 - z_2} d_2^{c}$, $d_1 \ne 1_{\mathbb {G}}$, and $d_2 \ne 1_{\mathbb {G}}$. Reject, otherwise.

Theorem 11

$\varPi ^{\textsf{bind}}$ is a three-round public-coin proof protocol for relation $R^{\textsf{bind}}$. It is complete, 2-special sound, and honest verifier zero-knowledge.

Proof

We focus on soundness and zero-knowledge properties since others are direct from the construction. To prove 2-special soundness, we construct an extractor, $\mathcal E$, as follows. Given a colliding transcript $(\ensuremath {\textsf{ck}}, a_1, a_2, a_3, d_1, d_2, c, z_1, z_2, c', z'_1, z'_2)$ that satisfies

$$\begin{aligned} a_1 &= g^{z_1} u^c = g^{z'_1} u^{c'},\end{aligned}$$

(2)

$$\begin{aligned} a_2 &= h^{z_2} v^c = h^{z'_2} v^{c'},\end{aligned}$$

(3)

$$\begin{aligned} a_3 &= d_1^{z_1 - z_2} d_2^c = d_1^{z'_1 - z'_2} d_2^{c'}, \end{aligned}$$

(4)

$c \ne c'$, $d_1 \ne 1$, and $d_2 \ne 1$, extractor $\mathcal E$ computes

$$\begin{aligned} \rho _1 := \frac{z'_1 - z_1}{c - c'},\quad \rho _2 := \frac{z'_2 - z_2}{c - c'}, \end{aligned}$$

and outputs $(\rho _1,\rho _2)$.

To verify that $\mathcal E$ is correct, observe that, from (2) and (3):

$$\begin{aligned} &z_1 + \log _g u \cdot c = z'_1 + \log _g u \cdot c' \Rightarrow \log _g u = \frac{z'_1 - z_1}{c - c'} = \rho _1, \text { and}\\ &z_2 + \log _h v \cdot c = z'_2 + \log _h v \cdot c' \Rightarrow \log _h v = \frac{z'_2 - z_2}{c - c'} = \rho _2. \end{aligned}$$

Also, from (4),

$$\begin{aligned} &(z_1 - z_2) + c \log _{d_1} d_2 =(z'_1 - z'_2) + c' \log _{d_1} d_2 \Rightarrow \log _{d_1} d_2 = \frac{z'_1 - z_1}{c - c'}- \frac{z'_2 - z_2}{c - c'}\\ &\Rightarrow \log _{d_1} d_2 = \log _g u - \log _h v = \rho _1 - \rho _2. \end{aligned}$$

Since $d_1 \ne 1$ and $d_2 \ne 1$, $\log _{d_1} d_2 \ne 0$. Thus, we have $\rho _1 - \rho _2 \ne 0$, proving $\rho _1 \ne \rho _2$.

To prove honest verifier zero-knowledge, we construct a simulator, $\ensuremath {{\mathcal {S}}}$, as follows. Given instance $\ensuremath {\textsf{ck}}= (\mathbb {G}, g, h, u, v)$, $\ensuremath {{\mathcal {S}}}$ picks $c, z_1, z_2$ uniformly and independently of $\ensuremath {\mathbb {Z}}_q$. It also chooses $d_1$ and $d_2$ uniformly and independently of $\mathbb {G}$. It then computes $\tilde{a}_1 := g^{\tilde{z}_1} u^{c}$, $\tilde{a}_2 := h^{\tilde{z}_2} v^{c}$, and $\tilde{a}_3 := d_1^{\tilde{z}_1 - \tilde{z}_2} d_2^{c}$. Finally, it outputs $(a_1, a_2, a_3, d_1, d_2, c, z_1, z_2)$.

We show that the above output from the simulator is computationally indistinguishable from that observed in a real protocol run. We construct a hybrid as follows. Given DDH question $Q:=(g, A, B, C)$ relative to $\mathcal{G}(1^n)$, we set $u=A$, $v = h^{\rho _2}$, $d_1=B$ and $d_2 = C B^{-\rho _2}$, and create other variables as prescribed by the simulator. This implies $\rho _1 = \log _g A$. If Q is in the DDH distribution, $C=B^{\rho _1}$. We then have $d_2 = B^{\rho _1 - \rho _2}$. Thus, the transcript is in the same distribution as the real prover outputs. On the other hand, if Q is in a random distribution, $d_2$ distributes uniformly as in the simulated transcript due to the randomness of C. Accordingly, the simulated and real transcripts are indistinguishable if the DDH assumption holds for $\mathcal{G}(1^n)$. This concludes the proof of honest verifier computational zero-knowledge of $\varPi ^{\textsf{bind}}$.

   $\square$