Threshold Encryption

Notes on a threshold encryption scheme: Simple and Efficient Threshold Cryptosystem from the Gap Diffie-Hellman Group from Baek and Zheng.

Lagrange interpolation

A polynomial $f$ of degree $t-1$ can be recovered with a set of $t$ of its evaluations at distinct points $S=(x_i{)}_i$ with the following linear combination (Lagrange interpolation polynomial),

using the Lagrange coefficient $L_{S,i}(x)={\prod }_{j\in S,j\ne i}\frac{x-x_j}{x_i-x_j}$:

$f(x)={\sum }_{i\in S}f(x_i)L_{S,i}(x).$

Here we’re taking $x_i=i$.

Notations

• $[n]P$ for scalar $n\in F_r$ and point $P$ in elliptic curve: scalar point multiplication
• $x\stackrel{﹩}{\leftarrow }R$: sample $x$ uniformly at random from set $R$

Setup

BLS curve with pairing $e(\cdot ,\cdot ):G_1\times G_2\to G_t$ where $G_1,G_2$ are subgroups (elliptic curves) of the same order $r$, generators $g_1,g_2,g_t\in G_1\times G_2\times G_t$. The scalar field $F_r$ from BLS. A hash function $\mathsf{G}:\{0,1{\}}^{\ast }\to \{0,1{\}}^l$, hash to curve function $\mathsf{G}:\{0,1{\}}^{\ast }\to G_2$, message space $\{0,1{\}}^l$.

A number of nodes $n>0$ indexed from 1 to $n$ (inclusive).

A threshold $0<t<n$.

A polynomial $f\in F_r[x]$ of degree $t-1$ whose coefficients $a_0,\dots ,a_{t-1}\in F_r$ are not known and sampled uniformly at random.

An (unknown) secret master key $sk=f(0)\in F_r$, and corresponding public master key $Y=[sk]g_2\in G_2$.

Each node possesses a share of the secret key (called secret key share) $(s{k}_i{)}_i=(f(i){)}_i\in F_r^n$, with corresponding public verification keys for each node $(Y_i{)}_i=([s{k}_i]g_2{)}_i$.

Deriving public key shares and public key in $G_1$

Each node $i$ can compute a verification key share in $G_1$ by computing $Y_i^{\prime }=[s{k}_i]g_1$. And after posting them on-chain, the master public key on $G_1$ can be recovered like so:

$Y^{\prime }={\sum }_{i\in S}[L_{S,i}(0)]Y_i={\sum }_{i\in S}[L_{S,i}(0)f(i)]g_1=[f(0)]g_1.$

One can check that the verification key share in $G_1$ matches the one in $G_2$ with the pairing check for $\alpha \stackrel{﹩}{\leftarrow }{F}_r^{\times }$:

$e(Y^{\prime }+{\sum }_i{\alpha }^i{Y}_i^{\prime },g_2)\stackrel{?}{=}e(g_1,Y+{\sum }_i{\alpha }^i{Y}_i).$

Encrypt

If $Y,(Y_i{)}_i\in G_2$

Input: $m\in \{0,1{\}}^l$, a valid setup (provided by a DKG in our case).

• Sample $r\stackrel{﹩}{\leftarrow }{F}_r^{\times }$
• $U\leftarrow [r]g_1\in G_1$
• Compute $V$:
  • if $Y,(Y_i{)}_i\in G_1$: $V\leftarrow \mathsf{G}(serialize([r]Y))\oplus m\in \{0,1{\}}^l$
  • if $Y,(Y_i{)}_i\in G_2$: $V\leftarrow \mathsf{G}(serialize(e(g_1,[r]Y)))\oplus m\in \{0,1{\}}^l$
• $W\leftarrow [r]\mathsf{H}(U,V)\in G_2$
• Ouput $C=(U,V,W)$

Verify ciphertext

Input: ciphertext $C=(U,V,W)$

• Compute $H=\mathsf{H}(U,V)\in G_2$
• Return $e(g_1,W)\stackrel{?}{=}e(U,H)$

Create decryption key share

• If ciphertext verification succeeds, $U_i\leftarrow [f(i)]U\in G_1$, output $D_i=(i,U_i)$

Verify decryption key share

if $Y,(Y_i{)}_i\in G_1$:

$e(Y_i,W)\stackrel{?}{=}e(U_i,H)$ and $e(g_1,W)\stackrel{?}{=}e(U,H)$

can be verified with two pairings:

$e(g_1+\alpha Y_i,W)\stackrel{?}{=}e(U+\alpha U_i,H)$

Scaling with the number of ciphertexts

This works with public key shares $Y_i$ in $G_2$, which is doable as the keyholder can easily map their key shares from $G_1$ to $G_2$ with the mapping $(s{k}_i,g_1^{s{k}_i})\mapsto g_2^{s{k}_i}$ which preserves the properties of the public keys, and the key shares in $G_2$ can be checked against the key shares in $G_1$ with a pairing after the DKG phase: $e(g_1,g_2^{s{k}_i})=e(g_1^{s{k}_i},g_2)$.

One can check for a threshold of keyholders indexed by $i\in V$ ($V$ is keyholder set):

$\{e(D_{i,c},g_2)\stackrel{?}{=}e(U_c,Y_i){\}}_{i,c}\}=\{{\text{true}}_{i,c}{\}}_{i,c}$

the above predicate is equivalent to with high probability (for nonzero random scalar $\alpha$):

$\{e({\sum }_{c=0}^n[{\alpha }^c]D_{c,i},g_2)\stackrel{?}{=}e({\sum }_{c=0}^n[{\alpha }^c]U_c,Y_i){\}}_i=\{{\text{true}}_i{\}}_i$

Alpha can be sampled solely from ALL the arguments to the pairings (Fiat-Shamir transformation).

For kernel execution, the random scalar $\alpha$ can be chosen as the hash of all the arguments to the pairings

So that we go (for $B$ ciphertexts) from $2\times V\times B$ pairings down to $2\times V$ ($V$ pairing checks instead of $V\times B$ pairing checks).

Why is the above batching secure?

Let’s consider the simpler problem:

Let A be an adversary who outputs pairs of group
elements ${(C_i,D_i)}_i$ and wins iff $({\sum }_i{r}^i{C}_i)=({\sum }_i{r}^i{D}_i)$ where $r:=Hash({(C_i,D_i)}_i)$. Prove that either $C_i=D_i$ forall $i=0,...,n$ or A cannot win except with negligible probability.

We obtain $({\sum }_i{r}^i{C}_i)-({\sum }_i{r}^i{D}_i)=0$ thus $({\sum }_i{x}^i(C_i-D_i))(r)=0$ which is a polynomial of degree $n$ (so has at most $n$ roots in the base finite field $F$) that vanishes at $r$. Assuming $C_i\ne D_i$ forall $i=0,...,n$ (otherwise the equality holds for any choice of $r$), by the Schwartz-Zippel lemma, the probability that a uniformly random $r$ vanishes the polynomial is $\le n/|F|$ which is negligible when working in a big finite field $F$. We can take $r=Hash({(C_i,D_i)}_i)$ by the Fiat-Shamir transform as the hash function uniformly distributes outputs, regardless of the inputs, so that the probability of success of the adversary would remain $\le n/|F|$.

One can reduce the above predicate to this simpler problem with the following chain of equivalences:

$\{e({\sum }_c[{\alpha }^c]D_{c,i},g_2)=e({\sum }_c[{\alpha }^c]U_c,Y_i){\}}_i$

$\{e({\sum }_c[{\alpha }^c{d}_{c,i}]g_1,g_2)=e({\sum }_c[{\alpha }^c{u}_c]g_1,Y_i){\}}_i$

$\{e({\sum }_c[{\alpha }^c{d}_{c,i}]g_1,g_2)=e({\sum }_c[{\alpha }^c{u}_c]g_1,y_i{g}_2){\}}_i$

$\{{\sum }_c[{\alpha }^c{d}_{c,i}]e(g_1,g_2)={\sum }_c({\alpha }^c{u}_c)y_{i}e(g_1,g_2){\}}_i$

$\{{\sum }_c{\alpha }^c{d}_{c,i}={\sum }_c({\alpha }^c{u}_c)y_i{\}}_i$

$\{({\sum }_c(d_{c,i}-u_c{y}_i)x^c)(\alpha )=0{\}}_i$

Combine decryption key shares

Input: $t$ decryption key shares $(D_i{)}_{i\in S}$ from a set $S$ of $t$ distinct nodes

• Verify ciphertext
• Verify decryption key shares $(D_i{)}_i$
• Recover plaintext $m$:
  • if $Y,(Y_i{)}_i\in G_1$: $m\leftarrow \mathsf{G}(serialize({\sum }_{i\in S}[L_{S,i}(0)]U_i))\oplus V$
  • if $Y,(Y_i{)}_i\in G_2$: $m\leftarrow \mathsf{G}(serialize(e({\sum }_{i\in S}[L_{S,i}(0)]U_i,g_2)))\oplus V$

Correctness:

$$\begin{array}{rl}\sum _{i\in S}[L_{S,i}(0)]U_i& =\sum _{i\in S}[L_{S,i}(0)f(i)r]g_1\\ & =[r\sum _{i\in S}{L}_{S,i}(0)f(i)]g_1\\ & =[rf(0)]g_1\\ & =[r]([f(0)]g_1)\\ & =[r]([sk]g_1)\end{array}$$

For $Y,(Y_i{)}_i\in G_2$: by bilinearity of the pairing (and $e(g_1,g_2)=g_t$):

$e(g_1,[r]Y)=e(g_1,[r][sk]g_2)=e(g_1,g_2{)}^{r\times sk}=g_t^{r\times sk}=e([r\times sk]g_1,g_2).$