AES and Homomorphic Encryption

Question

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.

Answer 1

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:

\begin{equation} f(\mathsf{Enc}(x), \mathsf{Enc}(y)) = \mathsf{Enc}(f(x,y)) \end{equation}

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:

\begin{equation} 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))) \end{equation}

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:

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

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

Answer 2

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.