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.
- Distributed Key Generation
- Pedersen DKG
- Deal Phase
- Complaint Phase
- Final Phase
- Random Beacon
- Signature Generation:
- Public Decryption (IBE)
- Intuition in blockchain context
- Protocol details
- Optimization: precomputation
- Private Decryption
- Protocols Description
- Encryption to the DKG network:
- Local Decryption
- Public Aggregation
- Research/Protocol Questions
We note the number of nodes that have a secret share, and the threshold of the network. Each node is identified by their long term public key and have a secret key .
We call the set of qualified node that have successfully ran the DKG, i.e. each node in have a partial share corresponding to the distributed secret key and public key where is the generator of the group (without indices means we refer to the "keys of the DKG").
We call the threshold network as Generalized Threshold.
We call the Lagrange basis polynomials the following:
such that and with
When not specified otherwise, we will use a pairing equipped elliptic curve of type III. Namely:
- There are three groups of order , with associated generators .
- There exists an efficiently computable bilinear map .
- We will place the key on the group: but that is not fixed.
Distributed Key Generation
Given the choice is not exactly settled, here are some potential solutions:
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)
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.
- Doing Pedersen DKG with trick from Neji (https://onlinelibrary.wiley.com/doi/abs/10.1002/sec.1651) as described in EthDKG
Each participant registered with a temporary private/public keypair 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 participants and we set the threshold as being the number of parties necessary to perform an operation with the distributed secret key.
Each participant does the following:
- Generate T random coefficients for a polynomial of degree T-1
- Compute shares
- Note in the future we might replace the indices with roots of unity
- Compute commitment to the polynomial: by multiplying all coefficients by the base generator
- Generate a random scalar and
- Compute encryption of the share for each recipient:
- For recipient i, compute where transforms the scalar into bytes in little endian format.
- Output the deal consisting of:
- Coefficients of
- Encryption vector:
Each recipient i perform the following verification:
- Compute shared key
- Decrypts share (interprets results as a scalar)
- Verify consistency:
- If consistency check is not passing, then go to complaint phase.
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.
- Generate a random
- Compute and
- Output proof
The smart contract will use the information from the deals and from the proof:
- Check if
- If not, the complaint is not valid (the smart contract can decide to slash etc, out of scope of this document)
- 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.
- If check is valid, then decrypt the share
- Verify the consistency:
- If consistency is verified, complaint is not valid (the deal was correctly created)
- If consistency check fails, the complaint is valid and the dealer must be excluded from the list of valid participants.
This phase happens after the first two and is simply the phase where the distributed keypair can be computed.
Secret Share for participant i:
for all dealers that were not excluded during the complaint phase.
for all dealers that were not excluded during the complaint phase.
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.
- Messages are consecutive rounds
- Each node partial sign
- There is an aggregation for the final signature (either by a liveness-trusted aggregator or by all nodes)
- where is a -sized set of valid partial signatures
- Check if
- Same code as in DKG (code), also works with blinded BLS signatures
- 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
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
- 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
Look into using IBE for everything (public/private encryption). See FAQ.
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 and the corresponding public key. For example, for "timed encryption", the ID would be the round number :
Encryption: A client that wishes to encrypt a message "towards" the ID will perform the following:
- This can be pre-computed
where and are both secure hash functions.
- 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 in a threshold way:
- It publishes
- At this point, anybody can decrypt the ciphertext in the following way
- Test that - if not, reject.
- M is the decrypted ciphertext
- Computation of
- Computation of :
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).
The encrypter will prefix/suffix its message with a signature over and it encrypts the results:
Once the helper has access to the signature related to the , 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 . If it is correct, it outputs the message . 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 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.
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).
To decrypt the nodes will each generate a partial decryption share. There are two ways to aggregate the shares:
- Local Decryption: the nodes send the partial decryption shares directly to recipient which will aggregate them locally and decrypt locally
- 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.
- 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.
- 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 to the public dist. key of the network:
- Generate random
- Compute ciphertext :
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:
- He really holds the secret (via DLEQ proof)
- This encryption has been made by him and for the given access control address
He does the following:
- Generate random
- Compute , where is another public random base
- Compute label where P is the public key of the Medusa, I is the address the policy smart contract, and is the address of the encryptor
- Compute and then
- Output the full ciphertext:
Verification of proof of correctness:
Verifier (depending on the context it can be the Medusa nodes or the smart contract) perform the following verification:
- Check if
- Note can be computed from public information
- 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.
Each DKG node 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
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 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 the public key of the recipient (with private key ).
- 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 -th node does the following:
- Generate random scalar
- Compute and
- Compute and
- Output proofs 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:
- Note that is available publicly since we know the whole public threshold polynomial so
- Check that
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):
- The recipient decrypts locally in constant time:
The recipient can compute because he knows and his own private key .
- Free Riding problem: how do incentivize nodes to DO something, and not just gaining money without actually not running any software.
- In private decryption:
- Can we get a proof of correct encryption of message ? i.e. that is well formed for any message ?
- For local aggregation, can we get non-interactive proofs that the decryption shares are valid wrt to the original ciphertext ?
- For public aggregation, can we get non-interactive proofs that the aggregated ciphertext is valid wrt to the original ciphertext?
- Is there a "pairing" enabled encryption scheme such that ciphertexts are on , like BLS signature ?
- Maybe can we re-use IBE and encrypt the result
- Public decryption:
- Can we a "batchable" decryption algorithm, for the same ?
- Do we need receiver privacy ? This is likely to be tackled at the protocol level though.
- 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 ?
- 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 ?
- Using naive ElGamal encryption, it's either we put the public keys on but then the randomness signatures have to be on and therefore they're bigger. Or we put public keys on but then ciphertext are on : 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 😋
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