This post explains an inherent tension between threshold BLS signature and Elgamal encryption for onchain verification, 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 counter-parties.

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 aforementioned. In particular, when using pairing equipped curves, a threshold network can be used to create threshold BLS signatures but it can also be used as a decryption oracle. In the latter, users encrypts towards the threshold network and push the encryption on-chain.

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, translated to the threshold setting.

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}$.
  • $\{rG, H(rP) \oplus m, \pi_{\mathbb{G}}\}$

<aside> 💡 💡 The purpose of the DLEQ proof is twofold:

1. CCA security: and more informally, to prove the author of the ciphertext really created it, i.e. that he knows the secret random scalar $r$ used for encryption. 2. Replay protection: because we can embed a public identifier of the author inside the DLEQ transcript so it is not possible for anyone else to submit the same ciphertext.

</aside>

• Verification of the correctness of the ciphertext involves verifying the DLEQ proof using group operations on $\mathbb{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$