4 ms·
(c(mod p)) (mod 2) = (p * q + 2 * r + m (mod p)) (mod 2) = 2r + m (mod 2) = m This breaks if 2*r > p. Even if you choose r to be small during encryption, the
by pieguy 8y ago
(c(mod p)) (mod 2) = (p * q + 2 * r + m (mod p)) (mod 2) = 2r + m (mod 2) = m
This breaks if 2*r > p. Even if you choose r to be small during encryption, the r values accumulate with each homomorphic operation and will eventually be too big. The only restriction stated is that r is "from a different interval than the private key one". This should be made more clear.
- tuxxy 8y agoI agree. The noise ceiling was only hinted at when the post started explaining Gentry's Bootstrapping method.
- jMyles 8y ago> Even if you choose r to be small during encryption, the r values accumulate with each homomorphic operation and will eventually be too big As @tuxxy points out, there is a metaphor for describing this - a "noise ceiling". To see this phrase used in context, see, for example: https://eprint.iacr.org/2011/277.pdf https://eprint.iacr.org/2011/277.pdf