CSI-RAShi: Distributed Key Generation for CSIDH

Abstract

We present an honest-majority Distributed Key Generation protocol (DKG) based on Shamir’s (k, n)-threshold secret sharing in the setting of Very Hard Homogenous Spaces (VHHS). DKGs in the discrete logarithm setting use Pedersen commitments, for which there is no known analogue in the VHHS setting. As a replacement, we introduce a new primitive called piecewise verifiable proofs, which allow a prover to prove that a list of NP-statements is valid with respect to a common witness, and such that the different statements can be verified individually. Our protocol is robust and actively secure in the Quantum Random Oracle Model. For n participants, the total runtime of our protocol is $2+\lambda +n(1+4\lambda )$ group action evaluations, where $\lambda$ is the underlying security parameter, and is thus independent of the threshold k. When instantiated with CSIDH-512, this amounts to approximately $4.5+18n$ seconds.

This work was supported in part by the Research Council KU Leuven grants C14/18/067 and STG/17/019, and by CyberSecurity Research Flanders with reference number VR20192203. Ward Beullens is funded by FWO fellowship 1S95620N. Date of this document: July 2, 2021

A Security Proof of NIPVP

1.1 A.1 Completeness

Lemma 1

Algorithms 3 and 4 constitute a complete NIPVP in the QROM for the list of relations of (1) if the used commitment scheme is collapsing and quantum computationally hiding.

Proof

If the protocol is followed correctly and if the input was a valid statement-witness pair $(x,w) \in R$, then the verifier will accept the proof piece with probability 1.

• In the case $i= 0$ the verifier will accept the proofs because the curves $\widetilde{E}_j$ recomputed by the verifier match the curves $\hat{E}_j$ computed by the prover: for each $j \in \{1,\dots ,\lambda \}$, if $c_j = 0$, then $r_j = b_j$ and hence $\widetilde{E}_j = [r_j(0)]E_0 = [b_j(0)]E_0 = \hat{E}_j$. If $c_j = 1$, then $r_j(0) = b_j(0)-f(0)$, so again we have $\widetilde{E}_j = [r_j(0)]E_1 = [b_j(0)-f(0)][f(0)]E_0 = [b_j(0)]E_0 = \hat{E}_j$. Thus both $\mathsf {C}_0$ are equal and the verifier will accept.

• In the case $i>0$ for each $j \in \{1,\dots ,\lambda \}$, the prover computes $b_j(i)$, and the verifier computes $r_j(i) + c_j x_j = b_j(i) - c_jf(i) + c_j x_j=b_j(i)$, if $x_i=f(i)$. So if the witness is valid, then the $\mathsf {C}_i$ match and the verifier will accept.    $\square$

1.2 A.2 Soundness

Our protocol can be seen as a “weak” Fiat-Shamir transformed version of a sigma protocol, where by “weak” we mean that, to obtain a challenge we only hash the commitment (instead of hashing both the commitment and the statement). The known results on the security of the FS transform in the QROM are about the strong FS transform. Therefore, before we can prove the soundness of our protocol we first prove the following lemma, which allows us to prove the security of the weak FS transform. This lemma bootstraps the known results for the strong FS transform to prove the soundness of the weak FS transform of a sigma protocol where the first message of the prover commits to the statement.

Lemma 2

Suppose $\varSigma = (P_1,V_1,P_2,V_2)$ is a sigma protocol for the relation R with superpolynomially sized challenge space $\mathcal {C}h$, special soundness and quantum computationally unique responses. Let $\varSigma ' = (P',V')$ be the following sigma protocol:

Then the weak Fiat-Shamir transformed version of $\varSigma '$ is a quantum proof of knowledge for the same relation R, assuming that $\mathcal {C}$ is collapsing.

Proof

The strategy of the proof is to interpret the weak FS transform for the relation R as the strong FS transformed protocol for a different relation $R'$. We can then use the techniques of Don et al. [16] on the security of the strong FS transform in the QROM. We define the following relation

$$\begin{aligned} R' = \{ (\mathsf {C}_x , (x,y,w) ) \, | \, \mathsf {C}_x = \mathcal {C}( x , y ) \text{ and } (x,w) \in R \}\, , \end{aligned}$$

and the following sigma protocol $\varSigma '' = (P'',V'')$:

Observe that the adaptive proof of knowledge game against the weak FS transform of $\varSigma '$ is identical to the adaptive proof of knowledge game against the strong FS transform of $\varSigma ''$, so it suffices to prove that $FS(\varSigma '')$ is a quantum proof of knowledge to finish the proof. We do this by invoking the theorems of Don et al. [16, Th. 25 and Cor. 16], which say that if $\varSigma ''$ has special soundness, quantum computationally unique responses and a superpolynomial challenge space, then $FS(\varSigma '')$ is a quantum proof of knowledge. Note that the challenge space $\mathcal {C}h$ is superpolynomial by assumption.

Special Soundness.² Suppose we are given two accepting transcripts $\mathsf {C}_x,com,ch,(x,y,rsp)$ and $\mathsf {C}_x,com,ch',(x',y',rsp')$ with $ch \not = ch'$, which means

$$\begin{aligned} \mathsf {C}_x&= \mathcal {C}(x,y) = \mathcal {C}(x',y') \, \text {, and} \\ V_2(x,com,ch,rsp)&= V_2(x',com,ch',rsp') = \text {accept} \, . \end{aligned}$$

Then, we can either extract a collision $\mathcal {C}(x,y) = \mathcal {C}(x',y')$ for $\mathcal {C}$ in the case $x \not = x'$, or we can invoke the special soundness of $\varSigma$ to obtain a witness w such that $(x,w) \in R$, which means we can construct a witness $w' = (x,y,w)$ such that $(\mathsf {C}_x,w') \in R'$.

Quantum Computationally Unique Responses ([16, Def. 24]). We define 3 games $\mathsf {Game}_i$ for $i \in \{1,2,3\}$, played by a two-stage poly-time adversary $\mathcal {A}= (\mathcal {A}_1,\mathcal {A}_2)$:

$$\begin{aligned} \mathsf {Game}_i^{\mathcal {A}}(): \quad&(x,y,rsp),com,ch \leftarrow \mathcal {A}_1() \\&z \leftarrow V_2(x,com,ch,rsp) \text { and } \mathsf {C}_x = \mathcal {C}(x,y)\\ \text { if } i \in \{1,2\} \quad&rsp \leftarrow \mathcal {M}(rsp) \\ \text { if } i \in \{1\} \quad&(x,y) \leftarrow \mathcal {M}(x,y) \\&(com,ch) \leftarrow \mathcal {M}(com,ch) \\&b \leftarrow \mathcal {A}_2(x,y,rsp,com,ch) \end{aligned}$$

Then the sigma protocol has quantum computationally unique responses if for any adversary $\mathcal {A}$, the following advantage is a negligible function of the security parameter:

$$\begin{aligned} Adv = \left| \Pr _{\mathsf {Game}_1^\mathcal {A}} [z = b = 1] - \Pr _{\mathsf {Game}_3^\mathcal {A}} [z = b = 1] \right| \, . \end{aligned}$$

(2)

This follows immediately from the assumptions, because the assumption that $\mathcal {C}$ is collapsing implies that $\left| \Pr _{\mathsf {Game}_1^\mathcal {A}} [z = b = 1] - \Pr _{\mathsf {Game}_2^\mathcal {A}} [z = b = 1] \right|$ is negligible, and the assumption that $\varSigma$ has quantum computationally unique responses implies that $\left| \Pr _{\mathsf {Game}_2^\mathcal {A}} [z = b = 1] - \Pr _{\mathsf {Game}_3^\mathcal {A}} [z = b = 1] \right|$ is negligible.    $\square$

Lemma 3

Algorithms 3 and 4 constitute a sound NIPVP in the QROM for the list of relations of (1) if the used commitment scheme is collapsing.

Proof

We need to prove that for any $I \subseteq \{0,\dots ,n\}$ and any QPT adversary $\mathcal {A}^\mathcal {O}$, the following advantage is negligible:

If $|I|<k$, then $\mathsf {Adv}^{\mathsf {sound}}_{\mathcal {A},I} = 0$ for any $\mathcal {A}$, simply because for every $x_I$, there exists a $w \in \mathbb {Z}_N[x]_{\le k-1}$ such that $(x_I,w) \in R_I$. Therefore, we can focus on the case $|I|\ge k$ for the remainder of the proof. We fix $I \subset \{0,\dots ,n\}$ with $|I|\ge k$. We define the function F as follows

$$\begin{aligned} F : \, \{0,1\}^\lambda \times \mathcal {X}_I \times (\{0,1\}^\lambda )^I \times (\mathbb {Z}_N[x]_{\le k-1})^\lambda&\rightarrow (\{0,1\}^{2\lambda })^I \\ \, (\mathbf {c}, x_I, y_I, \mathbf {r})&\mapsto \{\mathsf {C}_i'\}_{i \in I} \, , \end{aligned}$$

where $\mathsf {C}_0' = \mathcal {C}( [r_1(0)] E_{c_1} || \cdots || [r_\lambda (0)] E_{c_\lambda } || x_0 , y_0)$ (if $0 \in I$), and where $\mathsf {C}_i' = \mathcal {C}( r_1(i) + c_1 x_i || \cdots || r_\lambda (i) + c_\lambda x_i || x_i , y_i)$. With this notation we have$V^\mathcal {O}(i,x_i,\widetilde{\pi },\pi _i) = 1$ for all $i \in I$ if and only if $F( \mathcal {O}(\mathsf {C}) , x_I , y_I, \mathbf {r}) = \mathsf {C}_I$ and $\mathsf {C}'_i = \mathcal {C}(x_i,y_i)$ for all $i \in I$. So the claim that the advantage $\mathsf {Adv}^{\mathsf {sound}}_{\mathcal {A},I}(\lambda )$ is negligible for every efficient adversary $\mathcal {A}$ is equivalent to the claim that the “weak” FS transform of the following sigma protocol $\varSigma ' = (P_1',V_1',P_2',V_2')$ is a quantum computationally sound proof for $R_I$ ([16, Def. 9]):

$$\begin{aligned} P_1'(x_I,w) :&\, y_I,y'_I \leftarrow (\{0,1\}^\lambda )^I, \mathsf {C}'_i \leftarrow \mathcal {C}(x_i,y'_i) \text { for all } i \in I, \\&\, \mathbf {b} \leftarrow (\mathbb {Z}_N[x]_{\le k-1})^\lambda , \mathsf {C}_I = F( 0 , x_I , y_I, \mathbf {b} ) \\ V_1'(\mathsf {C}_I,\mathsf {C}'_I) :&\, \mathbf {c} \leftarrow \{0,1\}^\lambda \\ P_2'(\mathbf {c}) :&\, \mathbf {r} \leftarrow \mathbf {b} - \mathbf {c} \cdot w , rsp \leftarrow ( y_I , y'_I, \mathbf {r} ) \\ V_2'(rsp) :&\, \text { accept if } \mathsf {C}_I = F(\mathbf {c},x_I,y_I,\mathbf {r}) \text { and } \mathsf {C}'_i = \mathcal {C}(x_i,y_i) \text { for all } i \in I \end{aligned}$$

Since quantum computational soundness is implied by the quantum proof of knowledge property, it suffices to prove that the weak FS transform of $\varSigma '$ is a quantum proof of knowledge. This sigma protocol takes the form of $\varSigma '$ in the statement of Lemma 2, so we can conclude that our NIPVP is sound if the sigma protocol $\varSigma = (P_1,V_1,P_2,V_2)$ with

$$\begin{aligned} P_1(x_I,w) :&\, y_I \leftarrow (\{0,1\}^\lambda )^I, \mathbf {b} \leftarrow (\mathbb {Z}_N[x]_{\le k-1})^\lambda , \mathsf {C}_I = F( 0 , x_I , y_I, \mathbf {b} ) \\ V_1(\mathsf {C}_I) :&\, \mathbf {c} \leftarrow \{0,1\}^\lambda \\ P_2(\mathbf {c}) :&\, \mathbf {r} \leftarrow \mathbf {b} - \mathbf {c} \cdot w, rsp \leftarrow (\mathbf {r},y_I) \\ V_2(rsp) :&\, \text { accept if } \mathsf {C}_I = F(\mathbf {c},x_I,y_I,\mathbf {r}) \end{aligned}$$

has a superpolynomial challenge space, special soundness and quantum computationally unique responses.

Superpolynomial Challenge Space. The size of the challenge space is $2^\lambda$, which is superpolynomial in $\lambda$.

Special Soundness.³ Let $x_I, \mathsf {C}_I, \mathbf {c} , \mathbf {r}$ and $x_I, \mathsf {C}_I, \mathbf {c}'' , \mathbf {r}'$ be two accepting transcripts with $\mathbf {c} \not = \mathbf {c}'$. Take $j \in \{1,\dots ,\lambda \}$ such that $c_j \not = c'_j$, without loss of generality we can assume $c_j = 0$ and $c'_j = 1$. Then, if $0 \in I$ and $[r_j(0)] E_0 \ne [r'(0)] E_1$, we found a collision in $\mathcal {C}$. Similarly, if for some non-zero $i \in I$ we have $r_j(i) \not = r'_j(i) + x_i$, we also have a collision for $\mathcal {C}$. If there is no collision, we have

$$\begin{aligned} r_j(i)&= r_j'(i) + x_i \text { for all } i \in I , i>0 \, \text {, and } \\ [r_j(0)] E_0&= [r'(0)] E_1 \quad (\text {if } 0 \in I) \, , \end{aligned}$$

so $r_j(x) - r'_j(x)$ is a witness for $x_I$.

Quantum Computationally Unique Responses. Notice that F factors as $F = G \circ H$, where H is the function that given $\mathbf {c},x_I$ and $\mathbf {r}$ computes the input to the commitment function $\mathcal {C}$, and where G takes the output of H and the commitment randomness $y_I$ and outputs $\mathsf {C}_I$. We define 3 games $\mathsf {Game}_i$ for $i \in \{1,2,3\}$, played by a two-stage poly-time adversary $\mathcal {A}= (\mathcal {A}_1,\mathcal {A}_2)$:

$$\begin{aligned} \mathsf {Game}_i^{\mathcal {A}}(): \quad&(y_I,\mathbf {r}),(\mathsf {C}_i,\mathbf {c}) \leftarrow \mathcal {A}_1() \\&z \leftarrow 1 \text { if } \mathsf {C}_I = F(\mathbf {c},x_I,y_I,\mathbf {r}) \text { and 0 otherwise. }\\ \text { if } i = 3 \quad&\mathbf {r} \leftarrow \mathcal {M}(\mathbf {r}) \\ \text { if } i \in \{2,3\} \quad&(h,y_I) \leftarrow \mathcal {M}(H(\mathbf {c},x_I,\mathbf {r}),y_I) \\&(\mathsf {C}_I,\mathbf {c}) \leftarrow \mathcal {M}(\mathsf {C}_I,\mathbf {c}) \\&b \leftarrow \mathcal {A}_2(x,y,rsp,com,ch) \end{aligned}$$

We need to prove that for any efficient $\mathcal {A}$ the following is a negligible function:

$$ \left| \Pr _{\mathsf {Game}_1^{\mathcal {A}}}[z=b=1] - \Pr _{\mathsf {Game}_3^{\mathcal {A}}}[z=b=1] \right| \, . $$

Since G is just the parallel composition of |I| instances of $\mathcal {C}$, and since we assumed that $\mathcal {C}$ is collapsing it follows that G is collapsing. Therefore we have that $\left| \Pr _{\mathsf {Game}_1^{\mathcal {A}}}[z=b=1] - \Pr _{\mathsf {Game}_2^{\mathcal {A}}}[z=b=1] \right|$ is negligible. Since for a fixed value of $x_I$ and $\mathbf {c}$, the function $H(\mathbf {c},x_I,\cdot )$ is injective (here we use that $|I| \ge k$), we get that after measuring h and $\mathbf {c}$, the register $\mathbf {r}$ is not in a superposition of basis vectors. Therefore, the measurement $\mathbf {r} \leftarrow \mathcal {M}(\mathbf {r})$ does not affect the state of the system and we have $\Pr _{\mathsf {Game}_2^{\mathcal {A}}}[z=b=1] = \Pr _{\mathsf {Game}_3^{\mathcal {A}}}[z=b=1]$.    $\square$

1.3 A.3 Zero-Knowledge

For a fixed $I \subseteq \{0,\dots ,n\}$, our security definition of zero-knowledge for NIPVP is similar to the standard definition of non-interactive zero-knowledge in the QROM (e.g. [31, Def. 6]), except that the simulator is only given a partial statement $x_I$, instead of the full statement $\mathbf {x}$. Our proof strategy is to first reduce the NIPVP soundness to the standard zero-knowledge property of a standard sigma protocol. Then, we can use the results of Unruh [31] to finish the proof.

Lemma 4

Fix $I \subset \{0,\dots ,n\}$ and suppose $\mathsf {Sim}= (\mathsf {Sim}_1,\mathsf {Sim}_2)$ is a zero-knowledge simulator for the “weak” FS transform of the sigma protocol $\varSigma = (P_1,V_1,P_2,V_2)$ for the relation $R_I$.

$$\begin{aligned} P_1(x_I,w) :&\, y_I,y'_I \leftarrow (\{0,1\}^\lambda )^I, \mathsf {C}'_i \leftarrow \mathcal {C}(x_i,y'_i) \text { for all } i \in I, \\&\, \mathbf {b} \leftarrow (\mathbb {Z}_N[x]_{\le k-1})^\lambda , \mathsf {C}_I = F( 0 , x_I , y_I, \mathbf {b} ) \\ V_1(\mathsf {C}_I,\mathsf {C}'_I) :&\, \mathbf {c} \leftarrow \{0,1\}^\lambda \\ P_2(\mathbf {c}) :&\, \mathbf {r} \leftarrow \mathbf {b} - \mathbf {c} \cdot w , rsp \leftarrow ( y_I , y'_I, \mathbf {r} ) \\ V_2(rsp) :&\, \text { accept if } \mathsf {C}_I = F(\mathbf {c},x_I,y_I,\mathbf {r}) \text { and } \mathsf {C}'_i = \mathcal {C}(x_i,y_i) \text { for all } i \in I \, . \end{aligned}$$

Then there exists a simulator $\mathsf {Sim}' = (\mathsf {Sim}_1',\mathsf {Sim}_2')$ such that for any QPT distinguisher $\mathcal {A}$, the distinguishing advantage

$$ \mathsf {Adv}^{\mathsf {zk}}_{\mathsf {Sim},\mathcal {A}} = \Big | \Pr \left[ \mathcal {A}^{P',\mathcal {O}} (1^\lambda ) = 1 \right] - \Pr \left[ \mathcal {A}^{S', \mathsf {Sim}'_2} ( 1^\lambda ) = 1 \right] \Big | \, , $$

is a negligible function of the security parameter, where $P'$ is an oracle that on input $(\mathbf {x},w) \in R$ runs $\pi := P^\mathcal {O}(\mathbf {x},w)$ and outputs $\pi _I = (\tilde{\pi }, \{ \pi _i \}_{i \in I})$ and $S'$ is an oracle that on input $(\mathbf {x},w) \in R$ returns $\mathsf {Sim}'_1( \{x_i\}_{i \in I} )$.

Proof

The simulator $\mathsf {Sim}_2'$ simply forwards all its queries to $\mathsf {Sim}_2$, and $\mathsf {Sim}_1'$ forwards his queries to $\mathsf {Sim}_1$ to obtain $\mathsf {C}_I,y_I,y'_I,\mathbf {r}$. Then, for all $i \not \in I$ the simulator $\mathsf {Sim}_1'$ commits to dummy values to produce $\mathsf {C}_i$ and $\mathsf {C}'_i$. Then $\mathsf {Sim}_1'$ outputs $\tilde{\pi } = (\mathsf {C},\mathsf {C}',\mathbf {r}), \{ \pi _i = (y_i,y'_i) \}_{i \in I}$.

We prove the lemma with a simple hybrid argument: Let $\mathsf {Sim}''$ be identical to $\mathsf {Sim}'$ except that it interacts with a real prover for $\varSigma$, instead of with $\mathsf {Sim}$. Then, because $\mathsf {Sim}$ is supposed to be computationally indistinguishable from a real prover, we have that $\left| \Pr \left[ \mathcal {A}^{S', \mathsf {Sim}_2'} ( 1^\lambda ) = 1 \right] - \Pr \left[ \mathcal {A}^{S'', \mathsf {Sim}_2''} ( 1^\lambda ) = 1 \right] \right|$ is negligible. Secondly, since the only difference between an honest prover for the NIPVP protocol and $\mathsf {Sim}''$ is that $\mathsf {Sim}''$ commits to dummy values instead of real values for $i \not \in I$, it follows from the quantum computationally hiding property of the commitment scheme that $\left| \Pr \left[ \mathcal {A}^{P',\mathcal {O}} (1^\lambda ) = 1 \right] - \Pr \left[ \mathcal {A}^{S'', \mathsf {Sim}_2''} ( 1^\lambda ) = 1 \right] \right|$ is negligible.    $\square$

Lemma 5

Algorithms 3 and 4 form a zero-knowledge NIPVP in the QROM for the list of relations of (1) if the used commitment scheme is quantum computationally hiding and collapsing.

Proof

In light of Lemma 4, if suffices to prove that for every $I \subseteq \{0,\dots ,n\}$, the “weak” FS transform of the sigma protocol $\varSigma _I$ is zero-knowledge. Unruh proved (Theorem 20 of [31]) that if a sigma protocol has HVZK, completeness and unpredictable commitments, then the “strong” FS transform of that sigma protocol is zero-knowledge, but the proof goes through without problems in case of a “weak” FS transform also. Therefore, it suffices to prove for each $I \subset \{0,\dots ,n\}$, that $\varSigma _I$ has HVZK, completeness and unpredictable commitments.

Completeness. The protocol has perfect completeness. The proof is similar to the proof of Lemma 1.

Unpredictable Commitments. We say the sigma protocol has unpredictable commitments if the commitments have superlogarithmic collision entropy. More concretely, if there exists a negligible function $\mu (\lambda )$, such that for every $(x_I,w) \in R_I$ we have

$$ \Pr [(\mathsf {C}_I,\mathsf {C}'_I) = (\mathsf {C}''_I,\mathsf {C}'''_I) | (\mathsf {C}_I,\mathsf {C}'_I) \leftarrow P_1(x_I,w) , (\mathsf {C}''_I,\mathsf {C}'''_I) \leftarrow P_1(x_I,w) ] \le \mu (\lambda ) \, . $$

Let $i \in I$, then since $\mathsf {C}_i$ and $\mathsf {C}''_i$ are commitments, there are two possible ways to get a collision:

• The first possibility is that both commit to the same value. But since $\mathsf {C}_i$ commits to $\lambda$ uniformly random elements of $\mathcal {G}$ (or $\mathcal {E}$ in case $i = 0$), the probability that this happens is negligible.

• The second possibility is that both commitments commit to different values. Since we assume that $\mathcal {C}$ is collapsing (which implies collision resistance), this can also only happen with negligible probability.

Honest Verifier Zero Knowledge. The protocol has perfect HVZK. Consider the simulator that picks $y_I, y'_I, \mathbf {r}$ and $\mathbf {c}$ uniformly at random and sets $\mathsf {C}_I = F(\mathbf {c},x_I,y_I,\mathbf {r})$ and $\mathsf {C}'_i = \mathcal {C}(x_i,y'_i)$ for all $i \in I$.

This produces the same distribution of transcripts as honest executions of the protocol, because in both cases $y_I. y'_I, \mathbf {r}$ and $\mathbf {c}$ are uniformly random, and the rest of the transcript is a function of $y_I, y'_I, \mathbf {r}$ and $\mathbf {c}$.