Hi there, I am looking for an HE library for a specific use case I am thinking on implementing:
The requirements are:
large plaintext prime moduli of up to 256 bit
leveled scheme (about a multiplicative depth of 2 or 3) so no bootstrapping required
either BGV or BFV, no preference
The main issue obviously is the big plaintext prime, can you tell me if OpenFHE supports these out of the box? If no, how difficult is it to extend OpenFHE to implement encryption for large primes (for me)? I guess it should just be the encoding/encryption algorithms, and potentially finding suitable HE parameters? Otherwise, do you know any library supporting big plaintext primes out of the box?
OpenFHE does not support this large plaintext modulus out of the box - max is ~60 bits. I also do not think other libraries support such large plaintext modulus.
You may want to decompose the input plaintext space into sub-spaces each working with a distinct plaintext modulus, run multiple instances of your application - each instance with a distinct plaintext modulus, and generate a set of results that can be combined using the Chinese Remainder Theorem to create an output in the original plaintext space.
An example of how to use this approach can be found here - Section 3.1.
Hi, thanks for the fast answer! However, I do want to avoid the CRT since it has a blowup of factor 4 in computational cost… How much work would it for me (just an estimate) to extend OpenFHE for larger plaintext primes?
The large plaintext modulus would be a product of primes (or co-primes). If you use a 256-bit directly, every multiplication level will require more than 256 bits as the noise grows as roughly 2 N t, where t is a plaintext modulus and N is the ring dimension. This is one of the reasons the use of large plaintext moduli is discouraged. At a high level, the use of plaintext CRT is always more efficient because the noise will grow proportionally to a co-prime factor in t rather than t itself.
Thanks again, however my use case requires me to have a specific 256 bit prime as plaintext modulus, so I can not use CRT. So the only option seems to be to use this prime as the plaintext modulus directly, for which I need to adapt the library.
It might be helpful to share further details about what you are trying to achieve. Your problem might be solvable if the product of the plaintext moduli is greater than the 256-bit prime plaintext modulus you are interested in - that is no reduction modulo the 256-bit is done except maybe at the end of computation upon decryption.
Anyway, if your main concern is performance runtime, the CRT approach will be more efficient than the “multi-precision” approach you are seeking due to the reasons @ypolyakov pointed out. Plus, the CRT approach is inherently parallel as the instances are independent.
Sorry, no I need arithmetic in this large prime field, so absolutely no CRT possible. i at this point just want to know what is needed to get large primefiield moduli into the library, I would even implement it myself.
Again, CRT is not possible in my example
The following is very hairy and I have no idea how it will evolve. But if you need to do it in OpenFHE, then one approach would be the following.
Consider using [NTL ZZ_p](https://libntl.org/doc/ZZ_p.cpp.html) class for the plaintext modulus.
OpenFHE supports NTL as a math backend. To enable NTL, you should build it with WITH_NTL=ON. I am certain many things inside OpenFHE will break and you will need to fix them.
Have you looked at Lol? They claim in the abstract of the associated paper that they could:
implement an advanced fully homomorphic encryption (FHE) scheme in 2–5 lines of code per feature, via code that very closely matches the scheme’s mathematical definition.
It would be very hard to achieve it in OpenFHE. Moreover, it will be extremely inefficient in principle (\log Q would be large). Our intent was not to support plaintext moduli larger than 60 bits (except if plaintext CRT is used in the application itself; otherwise, any solution becomes impractical).