search

homenc / HElib

HElib is an open-source software library that implements homomorphic encryption. It supports the BGV scheme with bootstrapping and the Approximate Number CKKS scheme. HElib also includes optimizations for efficient homomorphic evaluation, focusing on effective use of ciphertext packing techniques and on the Gentry-Halevi-Smart optimizations.
https://homenc.github.io/HElib
Other
3.11k stars 761 forks source link

Additional primes for p>2 or r>1 in Test_General.cpp #210

Open smerte opened 6 years ago

smerte commented 6 years ago

I was wondering about this for quite some time now:

In the test file Test_General.cpp when initializing the value for L there is the condition of (plaintext base p>2) or (lifting r>1). If this condition holds then there are additional primes added for each round, specifically: 2*ceil(log((double)p)*r*3)/(log(2.0)*FHE_p2Size) +1

What is the basis of this expressions?

Suppose we have T successive multiplications to be preformed on a single Ctxt that is in plaintext base p>2, does that mean that we need to add the following amount of rounds to enable successful execution and decryption: 2*ceil(log((double)p)*r*T)/(log(2.0)*FHE_p2Size) +1?

shaih commented 6 years ago

The expression itself is a hack, but the phenomena is that the noise grows faster when the plaintext modulus is larger.

The reason is that in the BGV cryptosystem, multiplication includes a step of rounding (inside the modulus-switching procedure). When using plaintext space t=p^r, you round things to the closest multiple of t, and the rounding amount (times something) is added to the noise. Hence the larger p^r is, the more noise is being added in each multiplication step. The same phenomena holds also for other operations (but sometimes for different reasons).

In principle this should be compensated by making each level wider (which you can do making the "B" parameter in the context bigger). But for reasons related to the specific implementation in HElib, this solution is not really applicable beyond just a few more bits. So instead Test_General just adds a whole bunch of levels, to make sure that you have enough of them so as not to get decryption errors.