Proxy Re-Encryption

Table of contents

What it is

A Proxy Re-Encryption scheme allows for the modification of a ciphertext that was encrypted under key A to be decryptable with a different key B. This ciphertext modification can be done by any untrusted third party as it won’t learn anything about the underlying plaintext or the private keys involved.

How it works

Note: The Proxy Re-Encryption scheme presented here is a simplified version of a variant that uses the Diffie-Hellman Key Exchange protocol. It’s discussed here for educational purposes only and shouldn’t be used in a production environment.

In our example we have four different parties we call Alice, Bob, Charlie and Dave:

1. Alice receives an encrypted message from Charlie and wants Bob to be able to decrypt that message as well
2. Bob who relies on Dave, the untrusted third Party, to be able to decrypt Alice’s message
3. Charlie who sends a message to Alice encrypted under her public key
4. Dave, the untrusted third party who acts as a proxy to allow Bob to decrypt Alice’s message without learning anything about the message or the private keys involved

In this writeup we’ll be working with an Elliptic Curve $E$ that is of order $q$ and has a generator $G$. All calculations are done $\bmod\ q$ if not stated otherwise.

As a first step, Alice, Bob and Charlie generate their private- and public keys.

Alice does this by sampling a random value from $\mathbb{Z}_q$ which serves as her private key $a$.

This value is then multiplied by the generator $G$ to calculate her public key $A$.

Bob follows the exact same steps and starts the key generation procedure by sampling a random value from $\mathbb{Z}_q$ which is interpreted as his private key $b$.

His private key $b$ is then multiplied by $G$ to derive the corresponding public key $B$.

The exact same steps are followed by Charlie who generates his private key $c$ by sampling a random value from $\mathbb{Z}_q$.

He then also multiplies this private key $c$ by $G$ to calculate his public key $C$.

Given that Charlie wants to send a message to Alice he needs to get access to her public key $A$, so both Alice and Charlie do a key exchange of their public keys $A$ and $C$.

As Alice wants Bob to be able to decrypt her message she’ll receive from Charlie, she needs to get access to Bob’s public key to generate a re-encryption key for Bob. Both of them therefore also do a key exchange of their public keys $A$ and $B$.

Charlie is now able to send Alice a message that’s encrypted under her public key $A$.

To do that, he generates a shared secret $X$ following the regular Elliptic Curve Diffie-Hellman protocol by multiplying his private key $c$ with Alice’s public key $A$.

This shared secret $X$ can then be used to “blind” the plaintext message $M$ Charlie wants to send to Alice. The “blinding” is a simple multiplication of $M$ by $X$ which results in the ciphertext $E_A$.

Charlie sends this ciphertext to Alice.

Given that Alice wants Bob to be able to read the plaintext message $M$ of $E_A$, she can use Bob’s public key to calculate a re-encryption key $rk$ that can be used by Dave, the untrusted third party to create a decryption key for Bob which he can use to decrypt Alice’s message with his own private key $b$.

Alice calculates $rk$ by dividing her private key by a Hash of the multiplication of Bob’s public key with her private key. The Hash is computed via a cryptographic hash function $H$.

Notice that the multiplication of Bob’s public key $B$ with Alice’s private key $a$ is another instance of the regular Elliptic Curve Diffie-Hellman protocol in which Alice and Bob can use their public- and private keys to derive a shared secret only both of them have access to. We’ll see a similar computation later on when Bob derives the same shared secret by multiplying Alice’s public key $A$ with his private key $b$.

This re-encryption key $rk$ can be publicly shared. Alice send the re-encryption key $rk$ as well as Charlie’s public key $C$ to the untrusted third-party Dave.

Using this information, Dave creates a decryption key $b'$ for Bob that allows Bob to later decrypt Alice’s ciphertext $E_A$. The decryption key is calculated by multiplying Charlie’s public key $C$ with the re-encryption key $rk$.

Notice that Dave learns nothing about Alice’s, Bob’s or Charlie’s private keys as he’s only working with the publicly shareable re-encryption key $rk$ as well as Charlie’s public key $C$. In addition to that, he also doesn’t learn anything about the plaintext message $M$.

Dave can now send this decryption key $b'$ to Bob who can use it to decrypt Alice’s ciphertext $E_A$.

In our case, we assume that Alice forwarded $E_A$ to Bob, but it doesn’t really matter who sends $E_A$ to Bob as it’s a ciphertext which can be kept by different entities. The only important part is that it’s the correct $E_A$ Bob get’s access to.

Now that Bob got his decryption key $b'$ from Dave which itself is based on the re-encryption key $rk$ Alice calculated, he can decrypt the message Charlie sent to Alice using $b'$ and his own private key $b$.

To do so, Bob first recomputes the blinding factor $X$ by multiplying $b'$ with a hash of a multiplication of his private key $b$ by Alice’s public key $A$. The Hash is computed via a cryptographic hash function $H$.

Again, notice that the multiplication of Alice’s public key $A$ with Bob’s private key $b$ is an instance of the regular Elliptic Curve Diffie-Hellman protocol. Bob therefore derives the same shared secret Alice also computed in a prior step.

Bob can then use $X$ to recover the plaintext message $M$. To do so, he divides the ciphertext $E_A$ by $X$.

Why it works

The first thing to note is that the message $M$ that Charlie initially sent to Alice is “blinded” by the value $X$ which is a shared secret that both Alice and Charlie can calculate following the regular Elliptic Curve Diffie-Hellman protocol. Due to the usage of this “blinding” factor, the resulting ciphertext $E_A$ looks like random noise and thanks to the “hardness” assumption of the discrete logarithm, it’s impossible to recover $X$ from $E_A$ and therefore learn anything about $M$.

The re-encryption key $rk$ that Alice calculates also uses a shared secret $Ba$ that both Alice and Bob can calculate. This shared secret is hashed with a cryptographic hash function $H$ and serves as the denominator in the equation of $rk$.

Given that Bob also has Alice’s public key, he’s able to recompute the denominator of $rk$ himself using his private key $b$ to derive the same shared secret and hashing it with the same cryptographic hash function $H$.

Bob can now recompute the blinding factor $X$ himself as his decryption key $b'$ is just a multiplication of $rk$ with Charlie’s public key $C$. He can use $H(Ab)$ to “isolate” a multiplication of Alice’s private key $a$ by Charlie’s private key $c$ multiplied by the generator $G$.

Note that this is the exact $X$ that Charlie used to “blind” his message $M$ he sent to Alice.

Given that Bob has now access to $X$ he can recover the plaintext $M$ by dividing $E_A$ by $X$.

To show that this is indeed a message originally intended for Alice, we can show that Alice can recover $M$ as well. To do that she calculates $X$ by multiplying her private key with Charlie’s public key $C$. As a reminder, this is just the regular Elliptic Curve Diffie-Hellman protocol to derive a shared secret.

She’s then also able to use this $X$ (which is the same $X$ that Bob was able to calculate) to recover $M$ by dividing the ciphertext $E_A$ by $X$.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.

• Wikipedia - Proxy Re-Encryption
• Cryptography Stack Exchange - How proxy re-encryption works - layman perspective
• David Nunez - Umbral: A Threshold Proxy Re-Encryption Scheme
• Susan Hohenberger - Special Topics in Theoretical Cryptography - Lecture 17: Re-encryption