How proxy re-encryption works - layman perspective

Question

Here is the use case: A uses B's public key to encrypt a message and sent it to B. In later stages, a new member C joins and B would like to let C be able to see this encrypted message (i.e., give the decryption ability to C) without sharing his/her private key or letting A encrypt the message again using C's public key. It is in this question. A useful solution in that question is proxy re-encryption. In that case, B will generate a re-encryption key using B's private key and C's public key and send it to a proxy. The proxy will re-encrypt the encrypted message using the re-encryption key and send it to C. Then C can use his/her private key to decrypt the re-encrypted message to get the original one.

The main question is, after the encrypted message that was encrypted using B's public key earlier is re-encrypted using the re-encryption key generated from B's private key and C's public key, how can C use his/her private key to decrypt the re-encrypted message to get the original one? What makes this happen?

Could anyone please give a gentle introduction on how this proxy re-encryption works? I know there are many papers about it and I have tried to understand them but still cannot make anything of them (e.g., Lecture 17: Re-encryption, the most gentle material I found but still cannot understand...). Could anyone introduce it in a layman perspective, maybe via a working example? Introductions like these would be of great help.

Sorry if this question is too shallow here, but I really need such introductions because I am not a cryptography guy while I need to use this concept and need to understand basic principles of it. Thank you!

Answer 1

The following is a simple, unidirectional PRE scheme that doesn't use bilinear pairings, in case you find them distracting. It uses a static Diffie-Hellman exchange (i.e, combining the public key of one person with the private key of another) to make it unidirectional. BTW, I'm more used to describing proxy re-encryption as a delegation between Alice and Bob, rather than Bob to Charlie, so I'll use that convention here.

Alice:

• private key: $a$
• public key: $g^a$

Bob

• private key: $b$
• public key: $g^b$

Alice creates a Re-Encryption key for Bob using his public key:

• $rk = \frac{a}{H((pk_B)^{sk_A})} = \frac{a}{H(g^{ab})}$

Anyone can encrypt a message originally intended for Alice:

• $C_A = (g^r, M · g^{ar})$

The proxy re-encrypts $C$ using the re-encryption key:

• $C_B = ( (g^r)^{rk}, M · g^{ar}) = ( g^{\frac{ar}{H(g^{ab})}}, M · g^{ar})$

Bob decrypts using his private key, assuming he knows it was originally Alice's ciphertext (so he knows her public key $g^a$):

1. $ x = (C_{B,1})^{H(pk_A^{sk_B})} = g^{ar}$
2. $ M = \frac{C_{A,2}}{x}$

As you can see, the main idea is that the same secret that blinds the message ($g^{ar}$) can be produced with normal encryption with Alice's public key, and after re-encryption & decryption by Bob. In other words, you can produce $g^{ar}$ in two ways:

1. Alice can produce $g^{ar}$ by taking the $g^r$ component and using her private key $a$.
2. The re-encryption process transforms the $g^r$ component of the ciphertext into $g^{\frac{ar}{H(g^{ab})}}$, and Bob completes the process by removing the $H(g^{ab})$ using his private key $b$.

Once you have two methods to produce the same secret by Alice (only by decryption) and Bob (through re-encryption & decryption), then there you go, you have a proxy re-encryption scheme. There are many ways to do this (with bilinear pairings, without them, with lattices, etc.) and the tricks used by each scheme may vary, but in general that's the idea.

For the record, this is a super-simplified version of the Umbral proxy re-encryption scheme used by the NuCypher Network, a distributed network that provides a proxy re-encryption service with hundreds of proxies.