# BZTE + JF-DKG

A summary of a threshold encryption scheme using a variant of BZTE and JF-DKG for the initial setup.

Reading:
- Intro https://anoma.net/blog/demystifying-aggregatable-distributed-key-generation
- Pedersen DKG https://link.springer.com/content/pdf/10.1007/3-540-46416-6_47.pdf
- JF-DKG https://link.springer.com/content/pdf/10.1007/s00145-006-0347-3.pdf
- BZTE https://cpb-us-w2.wpmucdn.com/sites.uab.edu/dist/a/68/files/2020/01/globecom03-p1491.pdf

## BZTE protocol

### Setup

Scheme:
- $n$ key holders
- $k$ threshold
- BLS12-381 curve
- Generators $G\in G1$, $H\in G2$
- Decryption shares and public keys in $G1$

SSS instantiation (for every key holder):

$f_j(x)=\sum_{i=0}^{k-1}a_{ji}x^i$ random polynomial
$ss_{ji}=f_j(i)$ secret share is an evaluation of that polynomial

$sk_j=\sum_{j=1}^n ss_{ji}$
$msk=\sum_{j=1}^{n} a_{j0}$
$MPK=msk\cdot G$

The free term can be recovered using Lagrange interpolation:
$a_{j0}=f_j(0)=\sum_{i=1}^k ss_{ji}\prod_{m=1,m\ne i}^k \dfrac{0-x^m}{x^j-x^m}$ here the sum can be actually over any subset of key holders (as long as it is of size $k$).

Note that since the Lagrange coefficients are the same for all $f_j(x)$ (the same $k$ subset of key holders) we can do:
$msk=\sum_{j=1}^{n} \sum_{i=1}^k ss_{ji}\cdot l_i=\sum_{i=1}^k l_i \sum_{j=1}^{n} ss_{ji}=\sum_{i=1}^k l_i\cdot sk_i$

### Encryption

Inputs:
- Master public key $MPK\in G1$
- Message $m\in \{0, 1\}^{32}$

Output:
- Ciphertext $(U,V,W)\ where\ U\in G1,V\in \{0, 1\}^{32},W\in G2$

Do:

$r=random(F_p)$
$U=r\cdot G$ `ElGamal c1`
$y=r\cdot MPK$ `ElGamal shared key`
$V=hash(serialize(y))\oplus m$ `ElGamal c2`
$h=hash\_to\_g2(concat(serialize(U),V, AAD^*))$
$W=r\cdot h$ `BLS signature`

$AAD^*$ is used to bind together a shared key encrypted with TE and larger data encrypted with that key using symmetric cipher.

### Verifying ciphertext

Inputs:
- Ciphertext $(U,V,W)\ where\ U\in G1,V\in \{0, 1\}^{32},W\in G2$

Do:

$h=hash\_to\_g2(concat(serialize(U),V,AAD))$
$p1=e(U, h)$
$p2=e(G, W)$
$p1=p2$

Check:

$e(r\cdot G,h)=e(G,r\cdot h)$
$e(G,h)^r=e(G,h)^r$

#### Optimizations

1. We can do batch ciphertext verification on the sequencer side, but for a specific account only;
2. We cannot do batch verification on the key holder side, because key holder needs to only provide decryption shares for valid ciphertexts, so it needs to know which ones are valid exactly;
3. We can optimize individual pairing checks though, using the pairing product that shares final exponentiation.

Product of pairings:

$p1=e(U, h)$
$p2=e(-G, W)$
$p1\cdot p2=1$

Batch verification:
- $C$ ciphertexts
- Ciphertext $(U_c,V_c,W_c)$
- Generator $G$ (and its pre-calculated inversion)

$\alpha_{c}=random(F_p)$
$W=\sum_c \alpha_c\cdot W_c$
$h_c=hash\_to\_g2(concat(serialize(U_c),V_c,AAD_c))$

$e(G, W)=\prod_c [e(G,W_c)^{\alpha_c}]=\prod_c [e(U_c,h_c)^{\alpha_c}]$
$e(G, W)=\prod_c [e(\alpha_c\cdot U_c,h_c)]$
$e(-G, \sum_c \alpha_c\cdot W_c)\cdot\prod_c [e(\alpha_c\cdot U_c,h_c)^{}]=1$

### Decrypting shares

Inputs:
- Ciphertext $(U,V,W)\ where\ U\in G1,V\in \{0, 1\}^{32},W\in G2$

Do:

$DSH_j=sk_j\cdot U$

#### Optimizations

Key holder can use optimized multi scalar multiplication (MSM) algorithms to generate decryption shares for multiple ciphertexts.

Keywords: Pippenger, GLV decomposition, Wnoaf
- https://hackmd.io/@drouyang/SyYwhWIso
- https://hackmd.io/@drouyang/glv

### Verifying shares

Inputs:
- Ciphertext $(U,V,W)\ where\ U\in G1,V\in \{0, 1\}^{32},W\in G2$
- Decryption share $DSH_j\in G1$
- Key holder public key share $PK_j\in G2$

Do:

$h=hash\_to\_g2(concat(serialize(U),V,AAD))$
$p1=e(DSH_j,h)$
$p2=e(PK_j,W)$
$p1=p2$

Check:

$e(sk_j\cdot U, h)=e(sk_j\cdot G,r\cdot h)$
$e(sk_j\cdot (r\cdot G), h)=e(sk_j\cdot G,r\cdot h)$
$e(sk_j\cdot G, h)^r=e(sk_j\cdot G,h)^r$

#### Optimizations

Sequencer can verify decryption shares in **batches**, but only for a given key holder. Batch verification cannot tell which shares are invalid exactly, and the job of the sequencer is to only include valid decryption shares in the blueprint.

Related:
- Vitalik's post https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407
- Ferveo's implementation (NOTE that they have different TE scheme) https://github.com/anoma/ferveo/blob/1022ab2c7ccc689abcc05e5a08df6fb0c2a3fc65/tpke/src/decryption.rs#L24
- Taiko notes https://github.com/axiom-crypto/halo2-lib/issues/101

Inputs:
- $C$ ciphertexts
- $DSH_c$ decryption share for particular ciphertext
- Ciphertext $(U_c,V_c,W_c)$
- Public key share $PK$ (and its pre-calculated inversion)

$\alpha_{c}=random(F_p)$
$W=\sum_c \alpha_c\cdot W_c$
$h_c=hash\_to\_g2(concat(serialize(U_c),V_c,AAD_c))$

$e(PK, W)=\prod_c [e(PK,W_c)^{\alpha_c}]=\prod_c [e(DSH_c,h_c)^{\alpha_c}]$
$e(PK, W)=\prod_c [e(\alpha_c\cdot DSH_c,h_c)]$
$e(-PK, \sum_c \alpha_c\cdot W_c)\cdot\prod_c [e(\alpha_c\cdot DSH_c,h_c)^{}]=1$

NOTE that product of pairings can be calculated with shared exponentiation step.

### Combining shares

$p=\sum_{j=1}^k l_{j}\cdot DSH_{j}$ where $l_{j}$ are respective Lagrange interpolation coefficients
$ret=hash(serialize(p)) \oplus V$

Check:

$p=y$
$\sum_{j=1}^k l_{j}\cdot (sk_{j}\cdot (r\cdot G)) = r\cdot (msk \cdot G)$
$msk\cdot (r\cdot G) = r\cdot (msk \cdot G)$

#### Optimizations

We can use MSM although it probably won't give significant gain for a small number of shares (4 in our case).

Although it's not necessary to verify decryption shares (i.e. verify BLS signatures `W` in ciphertexts) we still have to do subgroup checks, i.e. ensure decryption shares belong to G1.

These checks can be implemented more efficiently:
- https://eprint.iacr.org/2019/814.pdf
- https://hackmd.io/@yelhousni/bls12_subgroup_check
- https://github.com/anoma/ferveo/issues/80

## DKG protocol

Reading:
- https://link.springer.com/content/pdf/10.1007/s00145-006-0347-3.pdf
- https://github.com/celo-org/celo-threshold-bls-rs/tree/master/crates/dkg-core

### Verifiable secret sharing (Feldman VSS)

Goal: ensure that all the shares are produced using the same polynomial.

Starting with the SSS instance:
$f(x)=\sum_{i=0}^{k-1}a_{i}x^i$

Dealer produces a commitment to the polynomial:
$F(x)=\sum_{i=0}^{k-1}a_{i}x^i\cdot G$

Public key share can be obtained by evaluating the commitment to the polynomial:
$PK_j=F(j)$

All receiving parties (and generally everyone) can now check that their shares belong to the original polynomial. Applying that to a TE scheme, the commitment polynomial is used to verify the authenticity of the decryption shares produced by the parties.

#### Complaints

If some party holds a share that does not belong to the published polynomial, it broadcasts a complaint against the dealer.

Dealer has to open the commitment (basically reveal the respective secret share) and if he fails to do so then he becomes disqualified (so do all the secret shares he distributed).

### JF-DKG scheme (Joint-Feldman)

Simplified [Pedersen DKG](https://eprint.iacr.org/2023/740.pdf)

1. All parties instantiate Feldman VSS
2. Honest parties form the $QUAL$ set
3. Every party computes its secret share as a sum of individual secret shares received from the $QUAL$
4. Public key shares are computed by multiplying commitment evaluations

#### On complaints and disqualified parties

Since the initial set of parties (keyholders) is determined by the L1 governance, the disqualification is also something that L1 governance has to resolve. What it means is that we do not proceed if one or multiple parties broadcasted incorrect shares but aim to rerun the protocol again with an adjusted set of parties.

#### On non-uniformly distributed secret

The JF-DKG protocol enables an adversary to influence the distribution of the result to a non-uniform distribution. But this attack relies on the fact an adversary can disqualify corrupted parties. In our modification disqualifications are not allowed, the protocol just falls back to L1 to replace the faulty keyholder.

## Implementations

**Celo**
JF-DKG / BZTE — BLS12-381
https://github.com/celo-org/celo-threshold-bls-rs

**EthDKG**
https://github.com/PhilippSchindler/EthDKG/

**SKALE**
JF-DKG / BZTE — BN254 (aka BN128)
https://github.com/skalenetwork/libBLS
Note: decryption shares in G2

**MaidSafe / PoA network / Dashpay**
JF-DKG / BZTE — BLS12-381
NOTE: decryption shares & public keys in G1
https://github.com/maidsafe/blsttc