This document is meant to be the central place of everything related to the cryptographic scheme the threshold network will employ.

It describes the cryptographic goals the threshold network wants to achieve & the different protocols one can use to get there with some implementation links.

• Notation
• Distributed Key Generation
• Pedersen DKG
• Security:
• Plan
• Specs
• Deal Phase
• Complaint Phase
• Final Phase
• Random Beacon
• Signature Generation:
• Verification:
• Implementation:
• Future
• Encryption
• Public Decryption (IBE)
• Intuition in blockchain context
• Protocol details
• Optimization: precomputation
• Private Decryption
• Overview:
• Protocols Description
• Encryption to the DKG network:
• Local Decryption
• Public Aggregation
• Research/Protocol Questions
• FAQ
• References

Notation

We note $n$ the number of nodes that have a secret share, and $t < n$ the threshold of the network. Each node $i$ is identified by their long term public key $P_i$ and have a secret key $sk_i$.

We call $Q$ the set of qualified node that have successfully ran the DKG, i.e. each node in $Q$ have a partial share $s_i$ corresponding to the distributed secret key $s$ and public key $P = sG$ where $G$ is the generator of the group (without indices means we refer to the "keys of the DKG").

We call the threshold network $GT$ as Generalized Threshold.

We call the Lagrange basis polynomials the following:

such that $\delta_j(x_j) = 1$ and $\delta_j(x_i) = 0$ with $i ≠ j$

When not specified otherwise, we will use a pairing equipped elliptic curve of type III. Namely:

• There are three groups $\mathbb{G_1},\mathbb{G_2},\mathbb{G_T}$ of order $q$, with associated generators $G_1,G_2,G_t$.
• There exists an efficiently computable bilinear map $e: \mathbb{G_1} \times \mathbb{G_2} \rightarrow \mathbb{G_T}$.
• We will place the key on the $\mathbb{G_2}$ group: $P = sG_1$ but that is not fixed.

Distributed Key Generation

Given the choice is not exactly settled, here are some potential solutions:

Pedersen DKG

The Pedersen based DKG works in synchronous rounds and is described succinctly here.

The main goal here is we want to have a shared scalar field at the end (and not a group element as for some other schemes such as PVSS)

Security:

Even though this DKG allows for some biasability in the final private key, because participants don't commit to the polynomial beforehand as in the Gennaro et al. one, it has been proven that the resulting key can be used for any re-keyable scheme such as BLS signature or El Gamal encryption, in this Mary et al. paper. This is sufficient for our purposes.

Plan

• Doing Pedersen DKG with trick from Neji (https://onlinelibrary.wiley.com/doi/abs/10.1002/sec.1651) as described in EthDKG

Specs

Each participant registered with a temporary private/public keypair $K_i = k_i * G_1 \in \mathbb{G_1}$ at the beginning of the protocol. How and where is out of scope for this crypto spec but you can think of it as if every participant save their public keys on a common smart contract.

We assume there is $n$ participants and we set the threshold $T > n/2$ as being the number of parties necessary to perform an operation with the distributed secret key.

Deal Phase

Proving:

Each participant does the following:

1. Generate T random coefficients $a_1, … , a_T \in \mathbb{F}$ for a polynomial $f(x)$ of degree T-1
2. Compute $n$ shares $f(1), f(2), … , f(n)$
1. Note in the future we might replace the indices with roots of unity $\omega^1, \omega^2…$
3. Compute commitment to the polynomial: $F(x) = f(x) G_1$ by multiplying all coefficients by the base generator $G_1$
4. Generate a random scalar $r \in \mathbb{F}$ and $R = rG_1$
5. Compute encryption of the share for each recipient:
1. For recipient i, compute $C_i = H(rK_i) \oplus b(f(i))$ where $b(.)$ transforms the scalar into bytes in little endian format.
6. Output the deal consisting of:
1. Coefficients of $F(x)$
2. Randomizer $R$
3. Encryption vector: $C_i$

Verifying:

Each recipient i perform the following verification:

1. Compute shared key $S_i = k_iR$
2. Decrypts share $f(i) = H(S_i) \oplus C_i$ (interprets results as a scalar)
3. Verify consistency: $F(i) == f(i)G_1$
4. If consistency check is not passing, then go to complaint phase.

Complaint Phase

Proving:

The recipient whose share is invalid will prove it to the smart contract by giving the shared key to the smart contract and proving it is the correct one without revealing its private key.

1. Generate a random $t \in \mathbb{F}$
2. Compute $w = tR$ and $w’ = tG_1^{’}$
3. Compute $u’ = k_iG_1^{’}$
4. Compute $e = H(C_i, S_i, u’, w, w’)$
5. Compute $f = t - e * k_i$
6. Output proof $[S_i, e, f, u’]$

Verifying:

The smart contract will use the information from the deals and from the proof:

1. Compute $w = fG_1 + eS_i = (t - e*k_i)R + (e*k_i)R = tR$
2. Compute $w’ = fG_1^{’} + eu’ = (t - e*k_i)G_1^{’} + (e*k_i)G_1^{’} = tG_1^{’}$
3. Check if $e == H(C_i, S_i, u’, w, w’)$
1. If not, the complaint is not valid (the smart contract can decide to slash etc, out of scope of this document)
2. Note the verifier must have the ciphertext not from the complainer but from the first phase. Using smart contract it is either registered onchain or the hash of it.
4. If check is valid, then decrypt the share $sh_i = H(S_i) \oplus C_i$
5. Verify the consistency: $F(i) == sh_i G_1$
1. If consistency is verified, complaint is not valid (the deal was correctly created)
2. If consistency check fails, the complaint is valid and the dealer must be excluded from the list of valid participants.

Final Phase

This phase happens after the first two and is simply the phase where the distributed keypair can be computed.

Secret Share for participant i:

$s_i = \sum_j f_j(i)$ for all dealers $j$ that were not excluded during the complaint phase.

Public Key

$S = \sum_j F_j(0)$ for all dealers $j$ that were not excluded during the complaint phase.

Random Beacon

$GT$ must be able to issue period random values, as a random beacon.

In the setting of threshold cryptography, the obvious and simple approach is to use a threshold BLS signature scheme, as in specified in drand specs.

TLDR

Signature Generation:

• Messages $m_r$ are consecutive rounds $r= 1, r=2, \dots$
• Each node partial sign $\sigma_{i,r} = [s_i]H(m_r)\in G_1$
• There is an aggregation for the final signature (either by a liveness-trusted aggregator or by all nodes)
• $\sigma = \sum_{i \in S} \delta_i(0)\sigma_{i,r}$
• where $S$ is a $t$-sized set of valid partial signatures

Verification:

• Check if $e(\sigma, g_2) == e(H(m_r), P)$

Implementation:

• Same code as in DKG (code), also works with blinded BLS signatures

Future

• Same thing for the roots of unity: at scale it makes the difference to be practical. Need implementation of BLS sig using roots of unity

Encryption

Using pairings and BLS signatures the way we do above, it allows us to have two kinds of encryption system:

• Public Decryption is where the threshold network will reveal a key that allows anybody to decrypt a ciphertext, using the identity based paradigm. Think of it as if a trusted third party were decrypting messages that were encrypted to it. If this third party obeys to a smart contract, it's equivalent to say that it gives the smart contract the functionality to decrypt messages encrypted to it.
• Private Decryption is where the threshold network's output is only decryptable by a given party with a specified private/public key pair

Public Decryption (IBE)

Intuition in blockchain context

Think of it as if a trusted third party were decrypting messages that were encrypted to it. If this third party obeys to a smart contract, it's equivalent to say that it gives the smart contract the functionality to decrypt messages encrypted to it. Note however in practice, everybody can decrypt the ciphertexts thanks to released material from the threshold network. The plaintext is not hidden in the smart contract (as currently, nothing is hidden).

The network will only decrypt the message upon a certain condition. For example, "timed encryption" means the network will release the private key material only after a certain time. If the condition is based on the exchange of tokens, the network will only release the material after the exhange has taken place. Etc.

Usages: Sealed bid auctions, timed encryptions, complex reward system (a complex condition will trigger the public decryption of the reward) etc

Performance:

• For the network, it is similar to threshold BLS
• For the decrypting an encrypted message client performs 1-2 pairings + XOR
• Some pre-computation can be done

Future:

Look into using IBE for everything (public/private encryption). See FAQ.

Protocol details

This scheme is a direct application of the Identity Based Encryption scheme from Boneh et al. (section 4.2) to the threshold and BLS setting.

For each instance of the protocol, we designate an $id$ and the corresponding public key. For example, for "timed encryption", the ID would be the round number $r$:

Encryption: A client that wishes to encrypt a message $m \in \{0,1\}^l$ "towards" the ID will perform the following:

1. Compute $G_{id} = e(P,Q_{id}) = e(P,H_1(id))$
• This can be pre-computed
2. Choose a random $\sigma \in \{0,1\}^l$
3. Set $r = H_3 (\sigma, m)$ where $H_3: \{0,1\}^* \rightarrow F_q$ is a secure hash function
4. Output the ciphertext:

where $H_2: \mathbb{G_t} \rightarrow \{0,1\}^l$ and $H_4: \{0,1\}^l \rightarrow \{0,1\}^l$ are both secure hash functions.

Decryption:

1. Once the threshold network decides it can decrypt the ciphertext, i.e. that the condition is validated, then it computes the BLS signature over the $id$ in a threshold way:
1. $\pi_{id} = sH(id) \in G_1$
2. It publishes $\pi_{id}$
2. At this point, anybody can decrypt the ciphertext in the following way
1. Compute $\sigma = V \oplus H_2(e(U, \pi_{id}))$
2. Compute $M = W \oplus H_4(\sigma)$
3. Set $r = H_3(\sigma, m)$
4. Test that $U = rG_1$ - if not, reject.
5. M is the decrypted ciphertext

Completeness:

1. Computation of $\sigma$

2. Computation of $M$:

Optimization: precomputation

The decryption still requires one pre-computed pairing and one individual pairing per decryption. A pairing can be costly and thus, having a way to batch decrypt would be very beneficial to using this method at scale and on-chain.

We introduce here roles to differentiate the computations:

• The encrypter (the persons encrypting the message,
• The helper (the party precomputing expensive operations to help decryption),
• The decrypter (the party actually doing the decryption, can be onchain).

Signature Embedding:

The encrypter will prefix/suffix its message $m$ with a signature $\pi_M$ over $m$ and it encrypts the results:

Once the helper has access to the signature related to the $id$, then it precomputes the following for all encrypted transactions for this epoch:

and submits this to the decrypter.

The decrypter actually decrypts all the messages with a simple XOR:

and verifies if the embedded signature is correct for each $m'$. If it is correct, it outputs the message $m_i$ . If it is not correct, it has to decide whether the encrypter or the helper has been misbehaving, i.e. either the signature is incorrect or the $\sigma_i$ given is incorrect. To do this he continues the decryption check:

• If the check doesn't pass, that means the helper has been misbehaving. In this case, the decrypter has to run the full decryption algorithm (either onchain or as part of recovery protocol with additional delay)
• If the check pass, that means the encrypter has inserted an invalid signature into its message and in this case, the decryption should be discarded.

In the case of a honest helper, then he can try to decrypt all the ciphertext himself before, and only include ciphertext that leads to valid signatures and reject the ones that are not. The right incentives will bias the behavior towards the honest one.

Private Decryption

Overview:

This mode uses basic El Gamal encryption where (1) a client encrypts a message to the network, then (2) the network can decrypt it to a particular recipient according to some conditions.

In comparison with the previous section, this is useful when we want that the plaintext is only revealed to the intended recipient.

Use cases: data management policies (see Calypso), private API access, the whole set of "proxy re-encryption" use cases (like distributed encrypted file storage).

Protocols Description

To decrypt the nodes will each generate a partial decryption share. There are two ways to aggregate the shares:

1. Local Decryption: the nodes send the partial decryption shares directly to recipient which will aggregate them locally and decrypt locally
1. Practical Consideration: The client needs to receive on a private channel and aggregate at least t shares.The first requirement may be hard to achieve (general connectivity between any two points on the internet is not granted). The latter one can quickly become a problem as soon as we want to grow the network size, for security reason. This tends to trap us in the "security vs usability" false dichotomy.
2. Public Aggregation: Either the nodes re-encrypt their share with the recipient public key, in a way that a liveness-trusted aggregator node can "group" them (interpolation) such the recipient perform a single constant time operation to decrypt.
1. Practical Consideration: The client in this case only makes one decryption locally. The network only needs to aggregate the shares "off chain", it can be a special aggregator node rewarded for this (if we can prove it).

Obviously the second method is preferable, but we describe first 1. and then describe 2. in the spirit of the "straw man approach".

Encryption to the DKG network:

Client wants to encrypt a message $m$ to the public dist. key $P = s G$ of the network:

1. Generate random $r \in \mathbb{F_q}$
2. Compute ciphertext $c$:

with $H(rP) \in \mathbb{F_q}$.

The encryption is bundled with a DLEQ proof of correctness.

Bundle with DLEQ proof of correctness

The prover also has to include a proof of correct encryption that shows:

1. He really holds the secret $r$ (via DLEQ proof)
2. This encryption has been made by him and for the given access control address

He does the following:

1. Generate random $t$
2. Compute $w = tG_1$ , $w’ = tG_1^{'}$ where $G_1^{'}$ is another public random base
3. Compute $u’ = rG_1^{'}$
4. Compute label $L = H(P, I, K)$ where P is the public key of the Medusa, I is the address the policy smart contract, and $K$ is the address of the encryptor
5. Compute $e = H_1(C_2,L, C_1, u', w, w’)$ and then $f = t - re$
6. Output the full ciphertext: $C, e, f, u’$

Verification of proof of correctness:

Verifier (depending on the context it can be the Medusa nodes or the smart contract) perform the following verification:

1. Compute $w = fG_1 + eC_1 = (t - re)G_1 + reG_1 = tG_1$
2. Compute $w’ = fG_1^{'} + eu’ = (t - re)G_1^{'} + erG’_1 = tG_1^{'}$
3. Check if $e == H(C_2, L,C_1, u', w, w’)$
1. Note $L$ can be computed from public information
2. Reason of this confusing order: treat C_1 = u, and then it means that we put all the “public info” at the beginning of the hash, and then all the DLEQ related info afterwards.

Submitting a ciphertext on chain

The Medusa smart contract will verify the ciphertext proof associated in the manner described just above.

Local Decryption

Each DKG node $i$ compute the decryption share and send it to recipient:

The node also computes a proof of correctness almost as similar as the encryptor.

Proof of correctness:

— TODO: since this functionality is not part of Medusa at the moment, it’s left as is.

The recipient can then interpolate locally

Public Aggregation

In this mode, the encryption to the network is done in the same way as before, however, it offers the possibility of aggregating the partial decryptions first and only send one message to the final recipient.

Each DKG node $i$ will encrypt its decryption share to the recipient's public key, such that an aggregator node can perform the Lagrange interpolation itself.

Let's call $U = uG_2$ the public key of the recipient (with private key $u$).

1. Each node computes its local encrypted decryption share

You can see the node decrypts its share and then re-encrypts it towards the public key of the recipient, but instead of using a random scalar, it uses its own share.

Proof of correctness:

The $i$-th node does the following:

1. Generate random scalar $t_i$
2. Compute $w_i=t_i(C_1 + U)$ and $w_i^{’} = t_iG_1$
3. Compute $e_i = H(D_i,w_i,w_i^{’})$ and $f_i = t_i - e_i * s_i$
4. Output proofs $[D_i,e_i,f_i]$ signed by the node (threshold key or longterm key if there is one)

Verification of the proof of correctness:

When receiving such partial reencryption, one perform the following check:

1. Computes $w_i = f_i(C_1 + U) + e_iD_i = (t_i - e_i*s_i)(C_1 + U) + (e_i*s_i)(C_1 + U) = t_i(C_1 + U)$
2. Computes $w_i^{’} = f_iG_1 + e_i(s_iG_1) = (t_i - e_i*s_i)G_1 + (e_i *s_i)G_1 = t_iG_1$
1. Note that $s_iG_1$ is available publicly since we know the whole public threshold polynomial $F(x)$ so $F(i) = s_iG_1$
3. Check that $e_i == H(D_i,w_i,w_i^{’})$

This proofs says that the node took ciphertext C1, re-encrypted it towards U and it can be publicly verifiable.

Aggregation of partial reencryptions

The aggregator collects enough shares with valid proofs and aggregate locally the ciphertext and sends it to the recipient (or to the bulletin board so the recipient sees it):

3. The recipient decrypts locally in constant time:

The recipient can compute $-usG_2$ because he knows $P = sG_2$ and his own private key $u$.

Research/Protocol Questions

1. Free Riding problem: how do incentivize nodes to DO something, and not just gaining money without actually not running any software.
2. In private decryption:
1. Can we get a proof of correct encryption of message $m$ ? i.e. that $C$ is well formed for any message $m$ ?
2. For local aggregation, can we get non-interactive proofs that the decryption shares are valid wrt to the original ciphertext ?
3. For public aggregation, can we get non-interactive proofs that the aggregated ciphertext is valid wrt to the original ciphertext?
4. Is there a "pairing" enabled encryption scheme such that ciphertexts are on $G_1$ , like BLS signature ?
1. Maybe can we re-use IBE and encrypt the result
3. Public decryption:
1. Can we a "batchable" decryption algorithm, for the same $id$ ?
4. Do we need receiver privacy ? This is likely to be tackled at the protocol level though.
5. Get a solid ground on the security of using El Gamal with type 3 bilinear maps without isomorphism between G1 and G2 (i.e. encryption only uses one or the other) , so under XDH setting → can we get cca there ?

FAQ

• Why not using proxy re-encryption techniques with a single node ?
• It is assumed the recipient and the proxy are not colluding, one of them is honest. By decentralizing the proxy, we ensure that the proxy is honest.
• In private decryption, why are encryption done on $G_2$ ?
• Using naive ElGamal encryption, it's either we put the public keys on $G_1$ but then the randomness signatures have to be on $G_2$ and therefore they're bigger. Or we put public keys on $G_2$ but then ciphertext are on $G_2$: it's a tradeoff. We can play with both.
• Why don't we use IBE for everything ? (public and private decryption)
• WE CAN ! Maybe we should ! Questions for private decryption is of integration: how do someone proves its identity, what is the identity based on etc.
• Need more literature review on this - don't know enough atm
• Why are you putting the milkmaid as background ?
• Because we're cooking something good 😋

References

Re-encryption:

Overview: https://www.cs.jhu.edu/~susan/600.641/scribes/lecture17.pdf

Green et al. https://eprint.iacr.org/2005/028.pdf

ID based, Green et al. : https://eprint.iacr.org/2006/473.pdf

Key private (hiding recipient): https://eprint.iacr.org/2008/463.pdf

Calypso: El Gamal based data management https://infoscience.epfl.ch/record/287444/files/3436905.3436917 (1).pdf