A minimal decentralized key distribution protocol

Problem: In the Rair protocol the method for distributing media decryption keys from media owners to decryption nodes relies on a centralized service. A decentralized protocol would allow keys to be distributed in the case that this centralized service fails.

Prior art

• LIT protocol is a distributed key generation service that uses MPC to do distributed key generation and signing. Using MPC has the downside that communication between participants is required each time a new key is introduced
• The McFly paper introduces the idea of Signature based Witness Encryption (SWE) used here. This protocol design is based mainly on this paper
• vetKeys contributes the idea of encrypting the signatures with public key encryption so that keys can be public but only viewed by the intended recipient
• Octopus Contract was also a major inspiration for this work

Background

SWE

Signature based Witness Encryption (SWE) as defined in the McFLY paper allows for an encryptor to encrypt data with respect to a public tag to a set of signing keys. The data can be decrypted by anyone with access to a threshold number of signatures by the signers (e.g. m-of-n) of the public tag.

Unlike MPC based key sharding this has the advantage that there is no private channel required with the signers and no direct communication. The protocol can be coordinated using public persistant data (e.g. a blockchain).

SWE can be instantiated using BLS signatures and is tractable in terms of encryption/decryption times and ciphertext size. All 3 scale linearly with the number of signers.

Unfortuantely a production grade implementation of SWE does not exist at this time but could likely be built on top of arkworks or a similar library.

Protocol

The entire protocol is basically SWE with encrypted signatures.

Encryption

1. Encryptor SWE encrypts key to their chosen set of signers for a unique tag
2. Publish ciphertext and tag

Decryption

1. Conditions for key distribution are met (e.g. new rair node approved on-chain)
2. Signers obtain public key for key recipient
3. Signers sign tag and encrypt signature for key recipient public key. Publish these encrypted signatures
4. Key recipient obtains m-of-n encrypted signatures, decrypts them and uses this to perform the SWE decryption

Incentivisation

As described there is no incentivisation for the signers who do the work securing the protocol. Adding this would require an addional proof that the encrypted signature publised by a signer is correct. Given this the protocol could automatically pay out to signers when the participate. For example:

1. Key recipient is approved by on-chain logic
2. Key recipient submits funds on-chain that can be unlocked by signers for providing valid encryped signatures
3. signers submit their signatures and are rewarded for doing so.

This is simple and could be implemented in a single contract assuming the proof verification is cheap.

An addional consideration is for misbehaving signers. This could be addressed by having them bonded and if a encrypted signature is submitted for a non-approved recipient this could be used as proof to slash them. Keys could then have some notion of economic security.

Protocol Properties

Features

• New signers can be added in a permissionless way. When a new key is added the key generator can chose who should secure it
• No communication required between key generator and signers, or between signers
• Coordination can be done in public (on-chain)

Limitations

• Key can be leaked if threshold majority of signers collude or are bribed