• 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

• 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

Pedersen DKG

Security:

Plan

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

Specs

Deal Phase

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$

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

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’]$

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

Random Beacon

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

• 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

• 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

Protocol details

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:

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

1. Computation of $\sigma$

2. Computation of $M$:

Optimization: precomputation

• 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).

• 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.

Private Decryption

Overview:

Protocols Description

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).

Encryption to the DKG network:

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

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

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’$

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.

Local Decryption

Public Aggregation

1. Each node computes its local encrypted decryption share

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)

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^{’})$

3. The recipient decrypts locally in constant time:

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