How useful is proxy re-encryption if we end up needing a symmetric key?

Question

I'm trying to design a system using proxy re-encryption (PRE) to allow the sharing of data between a user (delegator) and other users he delegates access to (delegatees). The goal is to use a PRE scheme to prevent the sharing of the delegator's private key.

I wanted to have a DB where all data is encrypted, each delegator's data encrypted under his private key. If someone requests access to a delegator's data there are 2 options:

1. Has legitimate access permission, in which case data should be returned;
2. Doesn't have access to what was requested, data should not be returned;

The proxy would have a re-encryption key and the delegatee would have another key to convert the proxy's (partially decrypted) ciphertext to plaintext.

My problem: if I have my records encrypted under my symmetric key and I allow a delegatee to see that key (after the proxy partially decrypts that key, the definition of delegatee would mean he's someone who can finalise decryption), he can then have access to all delegator files.

I was thinking a solution could be to have each record encrypted under a different key, so the delegatee would only have access to the key which encrypts the files he requested. This seems like it would have insane computational/storage overheads.

Another alternative would be to have some sort of proxy to DB which could generate keys on fly and encrypt data before sending it to a valid delegatee. Problem here is that that data was encrypted in the DB so the proxy would have to be able to decrypt it before encrypting it again under this new key. This means the proxy would have to know the key, defeating the whole point of a PRE scheme (also, the delegator would not know the key which encrypts his own files, which is undesirable).

Finally, the reason I'm posting this here is because I believe this is related to the understanding of PRE schemes and how they can be used in practise.

Answer 1

Let's look at an example of proxy re-encryption:

1. User A encrypts a some specific number (which is the message) under their own public key producing ct.
2. User A sends ct to a proxy.
3. User A determines that users B and C should be able to decrypt ct and uses their public keys and A's secret key to produce two re-encryption keys which are sent to the proxy. The proxy doesn't have any secret key that can be used to decrypt ct and recover the number.
4. Users B and C can identify themselves against the proxy which will use the corresponding re-encryption keys to produce the final ct$_B$ or ct$_C$. The proxy must store all three versions of the ciphertext (original + two re-encrypted versions). The requesting users only get their corresponding ciphertext.
5. Users B and C can use their secret keys to decrypt their corresponding ciphertexts.

There is a size limit at which messages can be encrypted, because ElGamal-style schemes work in cyclic groups which permit only elements (numbers) of a specific size.

If we want to encrypt messages that are larger, we need to use some kind of strategy to wrap the whole large message in an additional security layer. This can be symmetric encryption. When combined with asymmetric encryption is called hybrid encryption.

1. User A generates a random AES key and encrypts the large message using AES under that AES key producing the symmetric ciphertext ct$_s$. Then the AES key is converted to a number and encrypted under their own public key producing the asymmetric ciphertext ct$_a$.
2. User A sends ct$_s$ and ct$_a$ to a proxy.
3. User A determines that users B and C should be able to decrypt ct and uses their public keys and A's secret key to produce two re-encryption keys which are sent to the proxy. The proxy doesn't have any secret key that can be used to decrypt ct$_s$ or ct$_a$ and recover the number or the original message.
4. Users B and C can identify themselves against the proxy which will use the corresponding re-encryption keys to produce the final ct$_{a,B}$ or ct$_{a,C}$. The proxy must store all three versions of the asymmetric ciphertext (original + two re-encrypted versions) and only one version of the symmetric ciphertext. Each requesting user receives the symmetric and their corresponding asymmetric ciphertext. For example, user B receives ct$_{a,B}$ and ct$_s$.
5. Users B and C can use their secret keys to decrypt their corresponding asymmetric ciphertexts and then use the recovered numbers to convert them to AES keys and decrypt the symmetric ciphertexts.

When the messages get large, only the asymmetric ciphertext requires additional processing and storage for each additional user. Depending on the used primitives, the asymmetric ciphertext typically has a size of 512 to 4096 bits. The size of the non-duplicated symmetric ciphertext almost the same as the size of the original message (differs only by a constant amount such as at most 256 bit for AES with a sensible mode).

The crucial part is that user A must generate a fresh and random AES key for each message they want to send if the recipients might be different. But this kind of key-wrap method can be used to deduplicate multiple messages further when they are always intended to be received by the same group of users. Then user A must assign each group of users a unique and random AES key (which doesn't leave the system of user A).

Answer 2

Recap: Proxy Re-Encryption

We have some data $d$ encrypted for user $U_1$ as $Enc_{U_1}(d)$ and a re-encryption proxy which will transform it into $Enc_{U_2}(d)$ so that user $U_2$ can decrypt it.

It is similar to a secret sharing for the key of $U_1$ between the proxy and $U_2$.

Note that the proxy always creates a re-encrypted version of the data for every user. So if you have large amounts of data that you want to re-encrypt the amount of data will scale linearly with the amount of users.

However, if you have several pieces of data $d_1, ..., d_n$ you can use symmetric keys $k_1, ..., k_n$ to encrypt the data and then only have an encrypted version of the symmetric key duplicated for each valid user. Since the size of a symmetric key is only a few bytes this might be feasible.

Answer 3

PRE scheme is used for 'reads'. But in your case, it has lot of 'writes'(DB records are changed very often, also need indexing). PRE scheme may not be a good choice for you. Every time you update a record, the re-encryptions for each authorized user will be done again even if you don't change the symmetric keys. DB will be drained. If I were you, I will give up the PRE scheme, and use client-side encryption instead.