1
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Apr 8 at 21:10
  • $\begingroup$ @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. $\endgroup$
    – ProfCornDog
    Commented Apr 9 at 7:42
  • $\begingroup$ Who will later decrypt things? Bob, obtaining $\mathsf{Enc}(M, Y_A)$, which is then transmitted to (and fully decrypted by) Alice? $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Apr 9 at 8:11
  • 1
    $\begingroup$ 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). $\endgroup$
    – ProfCornDog
    Commented Apr 9 at 8:20
  • $\begingroup$ 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. $\endgroup$
    – ProfCornDog
    Commented Apr 9 at 9:25

1 Answer 1

Reset to default
0
$\begingroup$

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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.