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

Help with modulus computation problem #311

Open boev opened 5 years ago

boev commented 5 years ago

Your Contact: iordan.boev@gmail.com Your environment (OS/HW): not a technical question/problem Detailed Description:

Hello,

I have a computational problem involving the plaintext modulus p^r. I am doing computations in lets say 2^20 (p = 2, lift = 20). Suppose we are multiplying n such numbers. Now if one of those numbers is 0, then the whole product is 0 and that is good. But if 20 out of the n numbers are even or worse - contain multiple factors of 2, then quickly the plaintext modulus becomes divisor of the product and when decrypted, the product is 0. Basically, my question is, if there is a smart way (not introducing much noise or computation cost) to mitigate the problem. I only want to keep the product from becoming 0, any value other than that would be okay.

Thanks for reading, any ideas are welcomed! Yordan

boev commented 5 years ago

PS: I thought about extracting the LSB via extractDigit and then adding 1-LSB to the number, in order to make it odd. I am searching for something more elegant, or a more efficient way to do the LSB trick.

shaih commented 5 years ago

One option would be to work modulo a prime number close to 2^20. Alternatively use multiple instances, each one is modulo a different small prime number, such that the product of all these small primes is close to 2^20. Then you can re-assemble the result after decryption using Chinese-Rmeaindering