Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Craig Gentry's thesis talks about circuit privacy being straight forward from fully homomorphic encryption in the last chapter.
Can somebody explain in simpler terms what that means ? I have read it couple of times but could not get it. While the definition of Circuit privacy is simple the realization of the same using FHE in the last chapter is what is tough to understand.
Let $\rho$ be the 'initial noise level' of ciphertexts output by FHE.Enc. Fix any such ciphertexts $c_1$, ..., $c_k$.
Fix some function, written as a circuit $C$. Let $\rho_f$ be the 'final noise level' of ciphertexts output by FHE.Eval($C$, $c_1$, ..., $c_k$).
And observe that it should be easy to distinguish a ciphertext $c$ with noise-level $\rho$ from a ciphertext $c'$ with noise-level $\rho_f$, since they will be in geometrically different regions of the lattice (due observably differing noise levels).
Now, to achieve circuit privacy, we define the goal to have the distribution of ciphertexts output by FHE.Enc and the distribution of ciphertexts output by FHE.Eval be indistinguishable. Clearly, this is initially not the case (given the above discussion about noise levels).
So: To fix the problem, we "drown out" both the noise terms of size $\rho$ and size $\rho_f$ by introducing a MUCH BIGGER noise term $\rho^*$. To be specific, this means adding $c^*$ (a ciphertext encrypting 0 with noise level $\rho^*$) to the outputs of BOTH FHE.Enc and FHE.Eval.
E.g. define ciphertext $c_{re-rand} \stackrel{\rm def}{=} c + c^*$, and ciphertext $c'_{re-rand} \stackrel{\rm def}{=} c' + c^*$. (And from here on, we will be comparing the distribution of ciphertexts $c_{re-rand}$ vs the distribution of ciphertexts $c'_{re-rand}$, generated in these respective ways.)
In fact, we will set $\rho^*$ to be super-polynomially larger than $\rho_f$. Thus, statistically, since $\rho^* \ggg \rho_f > \rho$, we only need to consider the $\rho^*$-sized noise terms when arguing indistinguishability.
But since the noise terms in both $c_{re-rand}$ and $c'_{re-rand}$ that are of size $\rho^*$ were drawn independently (and from the same distribution), the distributions of re-randomized ciphertexts are indistinguishable, as desired.
