### Threshold proxy re-encryption for scalable end-to-end encrypted data sharing

We’re excited to announce the fulfillment of one of our major milestones: the definition and implementation of Umbral, a threshold proxy re-encryption scheme that powers the NuCypher KMS network.

Umbral allows secure delegation of decryption rights, enabling private data sharing between arbitrary numbers of participants in public consensus networks. This is achieved without revealing data encryption keys to intermediary entities. Umbral’s defining feature is arguably its split-key mechanism, whereby the re-encryption process (i.e. the cryptographic process through which data is securely shared) is distributed through a set of nodes rather than just one node, as it would be in a traditional proxy re-encryption scheme. To proceed, Umbral requires a quorum — a minimum number of nodes to complete the re-encryption, In this way, the trust is split between them in a manner similar to Shamir’s Secret Sharing — except with re-encryption key shares, rather than private key shares. The name “Umbral” comes from the Spanish word for “threshold”, emphasizing the split-key characteristic of the scheme, given its core role in the decentralized architecture of NuCypher KMS.

Our cryptosystem comes also with its first reference implementation in Python, pyUmbral. Built with Cryptography.io and OpenSSL, pyUmbral is a ready-to-use, open-source proxy re-encryption toolkit.

### A primer on Proxy Re-Encryption

Proxy re-encryption (PRE) is a set of algorithms which allows a semi-trusted proxy to transform ciphertext from being encrypted under one key to another, without learning anything about the underlying plaintext. To do so, Alice — the original data owner — creates a special key called “re-encryption key” that allows the proxy to transform ciphertexts so Bob can open them, in a process called “re-encryption”.

Proxy re-encryption is well-suited for use cases in which one wants to share encrypted data with multiple parties. Rather than naively sharing your private key with recipients (a highly insecure approach) or encrypting the entire message for each recipient, proxy re-encryption allows you to encrypt the data once and then delegate access to it based on the recipients’ public keys. This removes the requirement for the data owner to be online and also facilitates revocation of access — which the proxy can administer based on specified conditions, such time-boxed access.

### Umbral: a new proxy re-encryption scheme

With Umbral, Alice (the data owner) can delegate decryption rights to Bob through a re-encryption process performed by a set of N semi-trusted proxies (called “Ursulas”, in the terminology of NuCypher KMS). When at least M of these proxies (out of N) participate by performing re-encryption, Bob is able to decrypt the original message using his private key. Umbral is an example of threshold cryptosystem, since the re-encryption process requires a quorum of M out of N Ursulas.

On a more technical note, Umbral was loosely inspired by ECIES and the BBS98 proxy re-encryption scheme, although with several improvements. This includes the use of non-interactive zero-knowledge (NIZK) proofs in order to verify the correctness of re-encryption, so that KMS nodes cannot cheat without being caught. The threshold functionality of Umbral reuses ideas from Shamir’s Secret Sharing in order to make re-encryption a distributed process.

A more detailed specification of Umbral can be found in the technical paper.

### pyUmbral

Our cryptosystem is far less valuable without a proper instantiation. pyUmbral is our first reference implementation of Umbral, open-source and written in Python. It uses elliptic curve cryptography (in particular, curve secp256k1) and ChaCha20+Poly1305 as authenticated encryption primitive, all provided by Cryptography.io’s OpenSSL bindings. As a side note, pyUmbral is not only an implementation of Umbral: it also provides a nice and simple framework to perform basic elliptic curve arithmetic, facilitating fast-prototyping of other ECC-based cryptosystems.

Using pyUmbral is very easy: we show to use it here, in just a few steps. Let’s first create keys for both Alice and Bob:

from umbral import pre, keys

# Generate umbral keys for Alice.
alices_private_key = keys.UmbralPrivateKey.gen_key()
alices_public_key = alices_private_key.get_pubkey()

# Generate umbral keys for Bob.
bobs_private_key = keys.UmbralPrivateKey.gen_key()
bobs_public_key = bobs_private_key.get_pubkey()

Now, anyone who knows Alice’s public key can encrypt a message for her, as in typical public-key encryption. She can decrypt it with her private key:

# Encrypt data with Alice's public key.
plaintext = b'Proxy Re-encryption is cool!'
ciphertext, capsule = pre.encrypt(alices_public_key, plaintext)

# Decrypt data with Alice's private key.
cleartext = pre.decrypt(capsule, alices_private_key,
ciphertext, alices_public_key)

Note that the result of the encryption is a ciphertext and a capsule. With Umbral, the bulk data is encrypted by a symmetric cipher using a fresh key, which results in the ciphertext, while the capsule contains the necessary information to reproduce this fresh key during decryption, provided a valid private key is given. For the interested reader, this is a typical key encapsulation mechanism.

So far we haven’t seen proxy re-encryption in action. Let’s start by generating a set of re-encryption key fragments, called “kfrags”, that allow to delegate decryption rights of ciphertexts from Alice to Bob. Since Umbral is a threshold cryptosystem, we will indicate the total number of fragments (N) and the required threshold (M).

# Alice generates split re-encryption keys for Bob with "M of N".
kfrags = pre.split_rekey(alices_private_key, bobs_public_key, 10, 20)

In the NuCypher KMS network, kfrags would be distributed among the nodes of the network, so Bob will have to communicate with several Ursulas to obtain the whole re-encryption. In this example we will simply re-encrypt locally:

# Ursula re-encrypts the capsule to obtain a cfrag.
# Bob attaches the cfrags to the capsule.
for kfrag in kfrags:
cfrag = pre.reencrypt(kfrag, capsule)
capsule.attach_cfrag(cfrag)

Finally, Bob only has to decrypt the result using his private key:

# Bob activates and opens the capsule.
cleartext = pre.decrypt(capsule, bobs_private_key,
ciphertext, alices_public_key)

Here’s a video of pyUmbral in action:

pyUmbral reference implementation:
https://github.com/nucypher/pyUmbral

Umbral technical specification:
https://github.com/nucypher/umbral-doc/blob/master/umbral-doc.pdf

Questions? You can find us in our Discord channel:
https://discord.gg/7rmXa3S