# AES and Homomorphic Encryption

Is it possible to do the following?

Input would be to generate a new AES key, encrypt the private data with that key, encrypt the AES key with the FHE key, and send the FHE-encrypted AES key along with the AES encrypted data to the compute node.

It is possible to do, but depending on the performed operation, it may not be useful at all, so you have to choose the operation carefully.

The ultimate goal of FHE is to perform generic computations over encrypted data. That is, you have a generic function $f$ and you want to be able to compute it using encrypted inputs, so that:

$$f(\mathsf{Enc}(x), \mathsf{Enc}(y)) = \mathsf{Enc}(f(x,y))$$

If you encrypt the AES key, and perform generic computations on the encrypted key and some other encrypted input, then, thanks to the homomorphism of the FHE scheme, you will obtain after decryption the computation over the key and the other input to the function. Therefore, depending on the computation (i.e., the function $f$), this could produce a different AES key, and the AES encrypted data cannot be retrieved with the resulting key.

However, that does not mean that what you suggest is not useful at all. A possible scenario is that the operation you perform over the encrypted data does not modify the original value, for example, when FHE is used for implementing a proxy re-encryption functionality. In this case, the original message would be the AES key encrypted under some public key $pk_1$, and the homomorphic function is actually decrypting the AES key under $pk_1$ and encrypting it again under $pk_2$. This way, when someone uses $sk_2$ to decrypt the result, he will obtain the original AES key.

Suppose that you have your AES key, $K$, encrypted under $pk_1$, that is, $\mathsf{Enc}_{pk_1}(K)$. You also have a FHE scheme so that $f(\mathsf{Enc}_{pk_2}(x), \mathsf{Enc}_{pk_2}(y)) = \mathsf{Enc_{pk_2}}(f(x,y))$, for some other public key $pk_2$. Now simply set $x = sk_1$, and $y = \mathsf{Enc}_{pk_1}(K)$, so:

$$f(\mathsf{Enc}_{pk_2}(sk_1), \mathsf{Enc}_{pk_2}(\mathsf{Enc}_{pk_1}(K))) = \mathsf{Enc_{pk_2}}(f(sk_1,\mathsf{Enc}_{pk_1}(K)))$$

As you can see, if $f$ is designed to decrypt ciphertexts using the corresponding secret key, that is, $f(sk_1,\mathsf{Enc}_{pk_1}(K)) = K$, you are implementing a proxy re-encryption scheme that transforms ciphertexts from one public key to another, without altering the original message:

$$f(\mathsf{Enc}_{pk_2}(sk_1), \mathsf{Enc}_{pk_2}(\mathsf{Enc}_{pk_1}(K))) = \mathsf{Enc_{pk_2}}(K)$$

There are other types of use cases; see for example the ones in mikeazo's answer.

• Proxy re-encryption is just a specific use-case. You could just use trans-encryption to drastically reduce the transmission size, and then do your computation on the data as usual. – Dillinur Jun 25 '15 at 13:36
• @Dillinur I merely put it as an example. I will edit the answer for clarifying that. – cygnusv Jun 25 '15 at 13:38

Yes,

Where I have seen this idea primarily mentioned is to minimize the number of homomorphic operations that the client has to do.

1. Encrypt the AES key with FHE.
2. Encrypt the inputs with AES.
3. Send encrypted inputs and encrypted key to cloud.
4. Cloud uses encrypted AES key and AES encrypted inputs and runs the AES decryption circuit homomorphically. The outputs are FHE encrypted inputs.
5. Run computations on the FHE encrypted inputs.
6. Return FHE encrypted result to client.

Without doing this, the process would look like this:

1. Encrypt the inputs with FHE.
2. Send encrypted inputs to cloud.
3. Cloud runs computations on the FHE encrypted inputs.
4. Return FHE encrypted result to client.

This second option has far fewer steps, but since the FHE encrypt operation is typically very expensive (and produces large ciphertexts), the client has more work to do, and there is more data to transfer to the cloud. By encrypting the data with AES (a relatively cheap operation) and the key with FHE, the client is able to push off expensive computations to the cloud. This, along with the much smaller ciphertext sizes of AES compared to all existing FHE ciphers, are the major benefits of the approach you outline.

You just have to make sure you encrypt the inputs with AES in such a way that when the AES circuit is executed homomorphically, the outputs are useful for computation.

• You're kind of missing the point, after the decryption, you get the exact same inputs as you'd have received without using trans-encryption, so no "trick" is needed for it to be useful. The main advantage (and it's a tremendous one) is that you avoid the extremely severe data size inflation for the upload (your symmetric ciphertext having the same size as the cleartext). Please also note that 'AES' should be understand as 'a generic symmetric cipher', you wouldn't use AES with homomorphic encryption. – Dillinur Jun 25 '15 at 13:26
• @Dillinur I don't think I am missing the point at all. Your comment relates to one minor sentence at the end of my answer. The rest of my answer is exactly what you say. Also, I disagree that with your assertion that "no trick is needed". If I take a long string of integers separated by commas and encrypt it directly with AES-CBC it is going to be very hard for the cloud to do very useful operations with that. – mikeazo Jun 25 '15 at 13:30
• Regarding the useful operations, it will be as hard as if you just sent the same string with plain homomorphic encryption. You're only trading upload bandwidth with decryption overhead, beside that there is no impact on the algorithms you're willing to use on the data. – Dillinur Jun 25 '15 at 13:35
• @Dillinur would it? You would have to then split the homomorphically encrypted string on the commas, convert the ASCII representations of integers into usable integers. I'm not convinced that all that is as easy as you are implying. Remember, equality tests can't be done without interaction. – mikeazo Jun 25 '15 at 13:41
• If you send the same data, using both of your methods, you'll get the exact same problem. Sending the same string with just homomorphic encryption does not alleviate the problem you're stating in any way. Properly formating your inputs would solve this problem in both cases. – Dillinur Jun 25 '15 at 13:44