Efficient threshold BLS & Encryption

This post explains an inherent tension between BLS signature and Hashed Elgamal in the context of a threshold network, and then presents a way to augment such threshold network such that a smart contract can efficiently verify a signature and decrypt/verify encryption onchain.

Introduction

For encryption/decryption and signing, we (usually) require a group, i.e. a single elliptic curve. However, using pairings, we have to choose between $\mathbb{G_1}$ and $\mathbb{G_2}$ (and even $\mathbb{G_t}$), each group have their pros and cons depending on the cryptographic protocol we want to use. In practice, $\mathbb{G_1}$ is usually preferred given it is much shorter and faster to compute in it, than its counterparties.

This choice of group comes up when designing threshold networks. Indeed, there is a distributed key lying in a group $\mathbb{G}$ which could be any of the three groups aforementionned. In particular, when using pairing equipped curves, a threshold network can be used to create threshold BLS signatures (which has lots of nice properties and is used more than even in the blockchain space) but it can also be used as a decryption oracle. In the latter, users encrypts towards the threshold network and push the encryption onchain.

This posts shows the pros and cons of using $\mathbb{G_1}$ and $\mathbb{G_2}$ for each and shows there is a tension between the two. This posts then shows a simple solution to get the best of both worlds. The technique is heavily inspired by a post by Kobi Gurkan on efficient multisignature verification onchain.

Reminder on the cryptographic schemes

BLS Signatures

There are many references on the web that will explain BLS signatures. This post by Remco Bloemen is one of them!

Workflow: user creates a signature and push it onchain. The smart contract will verify the validity of this signature.

Hashed El Gamal

For succinctness and simplicity, we present this CCA version of El Gamal encryption scheme. Note that are many versions and also IBE based encryption scheme (such as the one used for timelock encryption), that will expose the same problem laid in this post.

Workflow: a user encrypts a message, and push it onchain. The smart contract will verify the “validity” of this ciphertext.

Assume we have a generic group $\mathbb{G}$, then

• Encryption of msg m is happening on $\mathbb{G}$ bundled with a DLEQ proof $\pi_{\mathbb{G}}$ (such as the one used in Privacy Pass by Cloudflare) lying in group $\mathbb{G}$.
• Verification of the correctness of the ciphertext involves verifying the DLEQ proof using group operations on G. We do not show it here for succinctness.
• Verification of this proof is done on the smart contract !

Distributed Key Generation

Such protocol is used to generate a distributed private key, such that each node has a share of it, but no one individually can recover the private key. The public key is known. The set of all nodes can act as if it was a single entity.

Let’s assume we have $n$ participants, with a threshold of $t$, a distributed public key $P=xG \in \mathbb{G_1}$, with each node having a share $x_i\in\mathbb{F_r}$-The “public share” can also be computed publicly $X_i=x_iG_1\in\mathbb{G_1}$

To recover the private key $x$, the network would need to come together and compute

Pubkey in $\mathbb{G_1}$, Signature in $\mathbb{G_2}$

• Threshold network public key $P=xG_1$
• Encryption to threshold network: $\{rG, H(rP) \oplus  m, \pi_{\mathbb{G_1}}\}$
• BLS signature σ verification from network:
• $e(P,H_2(m)) == e(G_1,\sigma)$ where $\sigma = xH_2(m) \in \mathbb{G_2}$
• This is computed on the smart contract !

In this situation, the trade off is as follow:

• DLEQ proof verification is FAST because only group operations in $\mathbb{G_1}$ are involved.
• BLS signature verification is SLOW because of the the hash-to-curve $H_2(m)$ operations which requires to handle operations in $\mathbb{F_{q^2}}$. This is especially relevant in context of blockchain where smart contract operations are usually costly.

Pubkey in $\mathbb{G_2}$, Signature in $\mathbb{G_1}$

• Threshold network public key $P=xG_2$
• Encryption to threshold network: $\{rG_2, H(rP) \oplus m, \pi_{\mathbb{G_2}}\}$
• BLS signature σ verification from network:
• $e(H_1(m),P) == e(\sigma,G_2)$ where $\sigma = xH_1(m) \in \mathbb{G_1}$

In this situation, the trade off is as follow:

• DLEQ verification is SLOW because group operations in $\mathbb{G_2}$ are involved. It is especially relevant in the context of blockchain where we want to verify this DLEQ proof onchain.
• BLS signature verification is FAST because the hash-to-curve operation $H_1(m)$ is fast, as it only involves $\mathbb{F_q}$ operations.

Goal

We want the best of both worlds:

• “Encryption to public key” on $\mathbb{G_1}$ to get cheap decryption/verification
• “Signature public key” on $\mathbb{G_2}$ to get cheap signature verification
• Still having the same “secret key” behind

The end user now have to use the corresponding key depending on which protocol he needs.

Creating a $\mathbb{G_2}$ key from the $\mathbb{G_2}$ key

The goal is to have a second public key $P’=xG_2 \in \mathbb{G_2}$, using the same share, representing the same secret key !

The network must perform the following steps (off chain):

1. Each node creates its symmetrical version of its share on $\mathbb{G_2}$ and broadcasts it:
1. $X_{i}' = x_iG_2\in\mathbb{G_2}$
2. everyone (including third parties) can verify the validity of the new share using the following equations:

1. The “public key in $\mathbb{G_2}$ can be recovered via regular lagrange interpolation

This key $P’$ can now be used for BLS signature on $\mathbb{G_2}$ !

Verification on chain of the equivalence

How does the contract know what is the new $P’$ ? How can he verify it is correct ?

We assume the contract already knows the original distributed key P.

An aggregator that performs (a) and (b) can submit $P’$ on chain. Contract then only need to perform a simple pairing check

This works because both have the same dlog / secret key !

Eviction of malicious node

A node might not generate its second version of its share or give an invalid one. How do you attest of that fact to the smart contract so he can be slashed / excluded ?

Given we now have “cheap” BLS signature, the threshold network (who have a majority of honest nodes) can “BLS sign” on the eviction of this node !

Another solution would for the contract to check (a) using the malicious node values but that might be more expensive to perform because the smart contract may not know $X_i$ in advance. This value requires evaluating the distributed public polynomial and this is linear in the threshold.

Acknowledgements

Thanks to Rosario Gennaro for help on the proof sketch, and Kobi for his post on the idea of translating between $\mathbb{G_1}$ and $\mathbb{G_2}$.

Appendix: Proof Sketch

Publishing keys in both group is safe

Assume we have groups $\mathbb{G}_1, \mathbb{G}_2,\mathbb{G}_T$ and a pairing function $e: \mathbb{G}_1 \times \mathbb{G}_2 \longrightarrow \mathbb{G}_T$

Let $P_1=xG_1 \in \mathbb{G}_1 \textrm{ and } P_2=xG_2 \in \mathbb{G}_2$

$P_2$ is the public key of a BLS signature scheme where a message $m$ is signed by first hashing it into $\mathbb{G_1}$ as $M = H(m)\in\mathbb{G_1}$ and the signature is computed as $S=xM\in\mathbb{G}_1$

The verification is $e(S,G_2)=e(M,P_2)$

$P_1$ is the public key of a Hashed ElGamal encryption scheme where the encryption of a message $m$ is computed as $(\alpha,\beta)$ with $\alpha=rG_1$ and $\beta=\hat{H}(rP_1) \oplus m$ together with a DLEQ proof $\pi$. Decryption is performed only if the proof holds and $m=\beta \oplus \hat{H}(x\alpha)$. The DLEQ proof provides another group element $\gamma=r\hat{G}_1$ and proves that $\log_{G_1}\alpha = \log_{\hat{G}_1}\gamma$.

Let’s assume the following problem is hard in $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T$

Given $P_1=xG_1,A=aG_1,P_2=xG_2 \textrm{ compute } B=(ax)G_1$

This is the Augmented Computational Diffie-Hellman problem in $\mathbb{G_1}$ where we account for the fact that $P_2$ is also known to the adversary.

The aCDH problem is what is needed to prove BLS in Asymmetric Pairings setting (see page 15 of Boneh et al).

Using same secret key for both BLS and El Gamal is safe

We need to show that the simultaneous security of BLS (unforgeable under chosen message attack) and Hashed ElGamal (under chosen ciphertext attack).

Our simulator is given $P_1$, $A$, $P_2$ from the aCDH problem. It sets $P_2$ as the BLS public key, $P_1$ as the Hashed ElGamal public key and sets $\hat{G}_1=\lambda P_1$ for a random $\lambda$

When the adversary is given $P_1,P_2$ and asks for a signature on a message $m$ the simulator sets $M=H(m)=rG_1$ for a random $r$ and then the signature is $S=rP_1$.

If the adversary queries a ciphertext $(\alpha=rG_1,\beta,\gamma,\pi)$ to the decryptor, the simulator answers $\bot$if the proof is not valid. Otherwise we know that $\gamma=r\hat{G}_1=r \lambda P_1$ and therefore $rP_1=\lambda^{-1} \gamma$ and $m=\beta \oplus \hat{H}(\lambda^{-1} \gamma)$

On the message $\hat{m}$ that the adversary wants to forge (which is guessed at random by the simulator), the simulator sets $\hat{M}=H(\hat{m})=A$ then the signature output by the forger must be $\hat{S}=xA=B$ as desired.

If the adversary issues a “distinguishing query” on Hashed ElGamal by presenting two messages $m_0,m_1$, the simulator chooses $b \in \{0,1\}$ at random and encrypts $m_b$ as $(\alpha=A,\beta = \hat{r} \oplus m_b, \gamma, \pi)$ where $\hat{r}$ is a random string, $\gamma$ is a random group element and $\pi$ is a simulated proof that $\log_{G_1} \alpha = \log_{\hat{G}_1} \gamma$. Note that the simulator is implicitly defining $H(B)=\hat{r}$ in the above simulation (implicitly since it does not know $B$). If the adversary guesses $b$ with probability better than 1/2 it must have queried B to the random oracle. Note that the simulator can detect when B is queried since $e(A,P_2)=e(B,G_2)$ so when that queries happens it answers with $H(B)=\hat{r}$ and outputs B as the desired solution.