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

Support a large plaintext space #116

Open msunkim opened 7 years ago

msunkim commented 7 years ago

I have many situations where I have to deal with large integers of 80 bits length about. To my knowledge, HElib does not support such large plaintext spaces currently. Probably, HElib's some internal codes might use the native integer type, but I didnot check it. Is it a correct guess?

I wonder that when this guess is correct, if I replace those codes with ZZ, I can use some large plaintext space.

shaih commented 7 years ago

There are several reasons why HElib does not support large integer plaintext space, using native long is just one of them. I'm almost 100% sure that replacing int by ZZ will not be enough. Beyond the programmatic issues, using such a large plaintext space will lead to very fast growth of noise, so you iwll not be able to compute much.

The right ways to dealing with applications that require large plaintext moduli are (a) to change them so they can live with smaller moduli (e.g., use an extension field rather than a prime field), or (b) encrypt the bits of the integers of interest and implement the modular arithmetic yourself. For the 2nd solution, sometimes it would be beneficial to work with bytes rather than bits (e.g. use plaintext space 2^8, or a small prime like 127).

msunkim commented 7 years ago

I appreciate for your suggestions, and I will check if applicable to my cases. Thanks again.

fionser commented 7 years ago

@msunkim For me, I apply the Chinese-Remainder-Theorem (CRT) to decompose the desired plaintext space into multiple smaller plaintext spaces. To do so, I choose k co-prime prime fields with each of them b-bit length, and generate k public/private key pairs and encrypt the data for k times. After the homomorphic computation, and decrypting k ciphertexts, the CRT can help me to recover the result which can be at most kb-bit long.

For example, I choose two co-prime prime fields p_1 = 5 and p_2 = 7. I encrypt two integers 3 and 4 with two different public keys and get enc_1(3), enc_1(4) and enc_2(3), enc_2(4) respectively. To conduct one multiplication, I get enc_1(3) * enc_1(4) => 3 * 4 \mod 5 = 2 and enc_2(3) * enc_2(4) = 3* 4\mod 7 = 5. Having 2 and 5 and according to the CRT, I can know that the result that I want is 12.

msunkim commented 7 years ago

Using multiple pairs of keys is interesting to me. I guess it is a good idea, and I will try it in my cases.