Distributed Key Generation (DKG)

We give an overview of Distributed Key Generation (DKG) and describe the DKG protocol used in the paper GJKR99. This, along with the ECVRF, will be two main components for the Distributed Verifiable Random Function (DVRF) protocol used for generating pseudorandom values. First, we give an overview of DKG. Then, we mention Verifiable Secret Sharing (VSS), the main building block for a DKG protocol. Finally, we describe the DKG protocol of GJKR99.

Author(s): phamnhatminh1292001

Overview of DKG

Distributed key generation is a main component of threshold cryptosystems. It allows $n$ participants to take part and generate a pair of public key and secret key required for the threshold cryptosystem without having to rely on a trusted party (dealer). Each participant in additional receive a partial secret key and a partial public key. While the public key and partial public keys is seen by everyone, the private key is maintained as a (virtual) secret of a $t,n$ secret sharing scheme, where each share is the partial secret key of a participant GJKR99. No adversary with limited computational power can learn any information of the secret key unless it control the required amount of participants.

DKG Security Properties

As in GJKR99, we wish a $(t,n)$ DKG protocol to have the following properties:

Correctness:

1. There is an efficient algorithm that, given any $t+1$ shares provided by honest parties, output the same unique secret key $sk$.
2. All honest parties agree on the same value of the public key $pk=g^{sk}$.
3. $sk$ is uniformly distributed in $\mathbb{Z}_p$.

Secrecy:: For any adversary who controls at most $t$ participants, he cannot learn any additional information except the value $pk=g^{sk}$.

Applications

DKG has been used in numerous aspects:

1. Threshold Encryption and Signatures: In threshold cryptosytems, one problem arises: single point of failure. If a single participant fails to follow the protocol, then the entire system will abort. When applied as a component of a threshold cryptosystem, $(n,t)$DKG solves this problem by ensuring that any $t+1$ participants who behave honestly will allow the protocol to execute successfully.

2. Identity based Cryptography (IBC): In IBC, a private-key generator (PKG) is required to generate a secret, called the master key and provide private keys to clients using it. Since he know the private key of the client, he can decrypt the messages of the client. A $(n,t)$ DKG solve this by distributing the PKG into many participants where any adversary who control at most $t$ parties cannot compute the master key, and the client receive his secret key by collecting $t+1$ partial private keys from the participants.

3. Distriuted Pseudo-random Functions: Pseudo-random Functions (PRF) and Verifiable Random Functions (VRF) is used to produce values that looks indistinguishable from random. Both require a secret key to compute the output. However, the secret key holder can select the value of the secret key to manipulate the output, or share the secret key with others to benefit himself. This can be prevented by applying a $(n,t)$ distributed version of PRF or VRF, thus no adversary can learn or affect the value of the secret key.

Verifiable Secret Sharing (VSS)

In this chapter, we discuss about Verifiable Secret Sharing (VSS), the main building block for a DKG protocol. We state the syntax and security properties of a VSS, then describe the VSS construction due to Pedersen.

Introduction

Secret Sharing was first introducted by Shamir in 1979 Shamir79. It allows a person to share a secret $s$ among $n$ parties such that any $\textit{authorized}$ subset of parties can use all their shares to reconstruct the secret, while any other (non-authorized) subset learns nothing about the secret from their shares. Shamir proposed a secret sharing scheme in his paper Shamir79. However, in Shamir's scheme, parties can commit wrong shares, leading the protocol to reconstruct the wrong secret, thus a verification process of the shares is required. To solve this problem, Chor et al. CGMA85 introduced Verifiable Secret Sharing.

Syntax and Properties

Syntax

A $(t,n)$ Verifiable Secret Sharing consists of two phases: Share and Reconstruct as follow:

Share: The dealer $D$ has a secret value $s$. Initially, there are $n$ parties $P_1, P_2, ..., P_n$. The sharing phase may consist of several rounds of interaction between parties. At the end of the phase, each party $P_i$ holds a share $s_i$ that will be required to reconstruct the secret of the dealer later.

Reconstruct: In this phase, each party $P_i$ publishes its share $s_i$ from the sharing phase. Then, from these shares, a reconstruction function will be applied to output the original secret.

Properties

As in BKP11, a VSS need to have the following properties:

Correctness: If $D$ is honest, then the reconstruction function outputs $s$ at the end of the Reconstruct phase and all honest parties agree on the value $s$.

Secrecy: If $D$ is honest, then any adversary that control at most $t$ parties does not learn any information about $s$ during the Share phase.

Commitment: If $D$ is dishonest, then at the end of the sharing phase there exists a value $s^* \in \mathbb{F}_p$ such that at the end of the Reconstruct phase all honest parties agree on $s^*$.

Pedersen's Construction

We describe a VSS protocol from Pedersen Ped91. This scheme provides perfect information theoretic security against any adversary with unbounded computational power.

Share The dealer chooses two polynomials $p(x)=a_0+a_1x+a_2x^2+...+a_tx^t$ and $p'(x)=b_0+b_1x+b_2x^2+...+b_tx^t$ such that $a_0=s$. Then he compute $s_i=p(i)$ and $s_i'=p'(i)$. The dealer then broadcasts $C_i=g^{s_i}h^{s_i'}$. Then he gives the party $P_i$ the tuple $(s_i,s_i')$. This allows $P_i$ to check if $(s_i,s_i')$ is a valid share by checking that

$g^{s_{i}}h^{s_{i}'} \stackrel{?}{=} \prod_{k=0}^{t}(C_{k})^{i^k} (*).$

If a party $P_i$ receives a share that does not satisfy $(*)$, he will complains against the dealer. The dealer must reveal the share $(s_i,s_i')$ that satisfies for each complaining party $P_i$. If any of the revealed shares does not satisfy $(1)$ the equation, the dealer is marked invalid.

Reconstruct Each participant submits $(s_i,s_i')$. Everyone can verify if $P_i$ submitted the correct shares by checking if $1$ is satisfied. If $P_i$ receives more than $t$ complaints, then he is disqualified. Given $t+1$ valid shares, $s_1,s_2,...,s_{t+1}$ from parties $P_{x_1},P_{x_2},...,P_{x_{t+1}}$, the secret $s$ can be computed as: $s= \sum_{i=0}^{t}s_i \left(\prod_{\substack{j=0 \\ j\neq i}}^{t}\dfrac{x_j}{x_j-x_i}\right).$

The security proof of the protocol can be found in Ped91.

DKG Construction

In this chapter, we describe the DKG protocol in the paper Gennaro et al GJKR99. The protocol can withstand up to $\dfrac{n}{2}$ dishonest participants, where $n$ is the number of participants. Despite the high communication cost, the protocol only need to be executed once in the first round of many threshold cryptosystems, making the DKG communication cost is not a serious matter in these cryptosystems.

Why Gennaro et al's Construction?

Despite there are numerous constructions for DKG, namely GJKR99, there is a reason we choose the DKG protocol of Gennaro et al.

Previously, Pedersen was the first to propose a DKG construction Ped91a. However, Gennaro et al. proved that in Pedersen's DKG, an attacker can manipulate the result of the secret key, making it not uniformly distributed GJKR99.

Canetti et al. CGJKR99 give a construction of a DKG that is secure against an adaptive adversary. However, his construction has worse performance than Gennaro's, since each participant has to use Pedersen's VSS two times. In addition, no adaptive adversary has been able to successfully attack the construction of Gennato et al.

Numerous attempts have been made to reduce the communication cost for a DKG KG09,CS04,CZAPGD20. However, all these schemes require a trusted party. This quite contradict the goal of a DKG.

This make the DKG construction of Gennaro et al. remains a simple, efficient and secure DKG protocol.

Gennaro et al's Construction

The DKG protocol consists of two phases, namely, generating and extracting, working as follows:

Public Parameters: Let $p$ be a prime number. Let $G$ be a cyclic group of order $p$ with generators $g$ and $h$. The public parameters of the system are $p,G,g,h$.

Generating: This process works as follows:

1. Each participant $P_i$ chooses two random polynomials $f_i(z)=a_{i0}+a_{i1}z+...+a_{it}z^t$ and $f_i'(z)=b_{i0}+b_{i1}z+...+b_{it}z^t$ and broadcasts $C_{ij}=g^{a_{ij}}h^{b_{ij}}$ for $j=0,1,...,t$.
2. The participant $P_i$ then sends $s_{ij}=f_i(j)$ and $s'_{ij}=f_i'(j)$ to $P_j$.
3. Each participant $P_j$ verifies the shares he received from each $P_i$ by checking whether

$g^{s_{ij}}h^{s_{ij}'}\stackrel{?}{=} \prod_{k=0}^{t}C_{ik}^{j^k}. (*)$

If the check fails for some $i$, $P_j$ complains against $P_i$.

1. Each $P_i$ who receives a complaint from $P_j$ broadcasts $s_{ij}$ and $s_{ij}'$ that satisfy Equation $(*)$.
2. A participant $P_i$ is disqualified if he receives at least $t+1$ complaints or answers a complaint with value that does not satisfy Equation. Then a set $\mathsf{QUAL}$ of qualified participants is determined.
3. For each $i$, the secret key $sk_i$ of $P_i$ is equal to $\sum_{j\in \mathsf{QUAL}} s_{ji}$. For any set $\mathcal{V}$ of at least $t+1$ participants, the secret key $sk$ is equal to $\sum_{i \in \mathcal{V}} sk_i\cdot\lambda_{i,\mathcal{V}}$.

Extracting: The process works as follows:

1. Each participant $P_i$ in the set $\mathsf{QUAL}$ publishes $A_{ij}=g^{a_{ij}}$ for $j=0,1,2,\dots,t$.
2. Each participant $P_j$ verifies $A_{ij}$ for each $i$. Specifically, $P_j$ checks whether $g^{s_{ij}}\stackrel{?}{=} \prod_{k=0}^{t}A_{ik}^{j^k}.$ If the check fails for some $i$, $P_j$ complains against $P_i$.
3. For each $i$ that $P_i$ receives at least one valid complaint, all other parties run Pedersen VSS to reconstruct $f_i(z)$, and restore $s_{i0}$ and $A_{ij}$ for $j=0,1,...,t$. The public key is equal to $pk= \prod_{i \in \mathsf{QUAL}}A_{i0}$.
4. The public key $pk_i$ of $P_i$ is calculated as $pk_i=g^{sk_i}=\prod_{j \in \mathsf{QUAL}}g^{s_{ji}}= \prod_{j \in \mathsf{QUAL}}\prod_{k=0}^{t}A_{jk}^{i^k}$.

The security proof of the DKG protocol can be found in GJKR99.