Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
To be brutally honest, it is a Ph.D. dissertation. That document earned someone a doctoral degree at a top university. I would not expect it to be easy to read. That being said, what is it exactly that you are having trouble with? Are you having problems with the definition of circuit privacy, or is it how Gentry transforms his scheme into a circuit-private one? Or both? –  Reid Jun 11 '13 at 12:02
    
the transformation is tough, i have edited the question thanks anyway –  sashank Jun 11 '13 at 14:26
    
It sounds like @Reid has not attempted to read the final paragraph of chapter 20, which is light on details :). I think this question is valid and also very unlikely to get an answer. My advice to the OP: If you want to understand homomorphic encryption constructions and circuit privacy, it'll be a lot easier if you start with subsequent works that extracted, simplified, and extended the ideas in this thesis. The paper linked here is particularly nice: cs.toronto.edu/~vinodv/BrakerskiV-FOCS2011.pdf –  David Cash Jun 12 '13 at 15:09
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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