Is it possible to homomorphically evaluate an encryption circuit?

I know that it is possible to homomorphically evaluate a decryption circuit as it is the main idea behind bootstrapping, but I was wondering if it was possible to evaluate an encryption circuit homomorphically (without exceeding the noise budget obviously)?

With simplified notations, the idea is that for a message $$M$$ encrypted by Alice with her public key $$Y_A$$ giving the ciphertext $$C_1 = \mathrm{Enc}(M, Y_A)$$, I want Bob (with public key $$Y_B$$) to calculate $$C_2 = \mathrm{Enc}(\mathrm{Enc}(M, Y_B), Y_A)$$.

I do not want Bob to access $$M$$ so re-encryption is not an option here, since I would obtain $$\mathrm{Enc}(M, Y_B)$$ before $$C_2$$, which can be decrypted by Bob with his secret key.

From what I understood it might be possible within the noise budget, but I wasn't able to find a documented answer (although it is likely that I have missed something). Thank you!

• Is there a reason you prefer the "iterated encryption" that you have written down, compared to other techniques to simultaneously encrypt under the keys $\vec s, \vec s'$, etc? This later problem ("Multi-key FHE") is better studied. Apr 8 at 21:10
• @MarkSchultz-Wu thank you fr your suggestion! It is not clearly stated in my question as I have tried to make it pretty generic, sorry for that. In my specific application I do think it is explicitly required, as Bob has multiple public keys $(Y_{B,1},\dots,Y_{B,n})$ and I do not want Alice to know which one of those keys is used, and I do not want Bob to know the message $M$. Also the order of encryption is important for later proxy re-encryption. But it is very possible that I am missing something. Apr 9 at 7:42
• Who will later decrypt things? Bob, obtaining $\mathsf{Enc}(M, Y_A)$, which is then transmitted to (and fully decrypted by) Alice? Apr 9 at 8:11
• A third party Charlie with public key $Y_C$. Therefore the idea is to create $C_3 = \mathrm{Enc}(\mathrm{Enc}(M, Y_{B,i}), Y_C)$ (for Bob's chosen key $Y_{B,i}$) so that Charlie can obtain $\mathrm{Enc}(M, Y_{B,i})$ (which will not be decrypted). Apr 9 at 8:20
• I do see that there are obvious flaws, and I will have to work on them (and Multi-key FHE might be useful). I am adapting an existing system that already exists and trying to not change to much, but it is not a good idea because FHE works very differently... But in anyway I thought that the general question was worth asking. Apr 9 at 9:25

Maybe you can use programmable bootstrapping (PBS) to solve this issue, it is a way to evaluate an arbitrary function during bootstrapping. e.g., $$PBS(Enc(M, K_1), f) = Enc(f(M), K_1)$$. Inyour application, let $$f$$ be the encryption function under $$K_2$$ with some fresh noise, i.e., $$f(m) = Enc(m, K_2)$$.
The main challenge is to deal with the different plaintext and ciphertext space since usually the plaintext space is much smaller than the ciphertext space. One way to deal with problem is to perform multiple PBS with multiple $$f_i$$, where every $$f_i$$ gives $$i$$th chunk of the ciphertext. In other words, $$f_1(M) \Vert \dots \Vert f_n(M) = Enc(M, K_2)$$.