Hello, I’m trying to set parameters for BFV scheme and have some questions on how plaintext modulus should be set appropriately for my application -
// uint64_t p = 65537;
uint64_t p = 12869861377;
// uint64_t p=9899511922689010000;
double sigma = 3.2;
SecurityLevel securityLevel = HEStd_128_classic;
uint32_t depth = 3;
CryptoContext<DCRTPoly> cc = CryptoContextFactory<DCRTPoly>::genCryptoContextBFVrns(p, securityLevel, sigma, 0, depth, 0, OPTIMIZED);
int32_t n = cc->GetCryptoParameters()->GetElementParams()->GetCyclotomicOrder() / 2;
double log2_q = log2(cc->GetCryptoParameters()->GetElementParams()->GetModulus().ConvertToDouble());
- If the plaintext modulus is too large, I get the following error-
For plaintextmodulus 9899511922689010000, error got is- terminate called after throwing an instance of 'lbcrypto::config_error'
what(): $PATH/palisade-release/src/core/lib/encoding/packedencoding.cpp:66 the plaintext modulus size is larger than the size of CRT moduli; either decrease the plaintext modulus or increase the CRT moduli.
I require a large plaintext modulus as numbers in my application are large. How do I increase the CRT modulii to accomplish this?
- I checked that plaintextmodulus can only be set such that the following is satisfied-
terminate called after throwing an instance of 'lbcrypto::math_error'
what(): $PATH/palisade-release/src/core/lib/math/nbtheory.cpp:281 Please provide a primeModulus(q) and a cyclotomic number(m) satisfying the condition: (q-1)/m is an integer. The values of primeModulus = 1000123465987 and m = 32768 do not satisfy this condition
Why is this condition necessary? Also, is there any easy way to get a prime plaintext modulus q, that satisfies the condition that (q-1)/m is an integer? (Also, I think it would be better to replace q by p in this error message, as q is the large modulus used for ring…?)
My plaintext-modulus should be in range 10^18 as that’s how big the numbers in my application are.
The prime “9899511922689010000” is 64-bit long which is quite large.
I suggest you consider using the Chinese Remainder Theorem trick, that is, decomposing your problem over two smaller plaintext modulus instead of one big plaintext modulus.
Say your preferred plaintext modulus size is 10^{18} which is almost 60-bit long. Find two primes, each of size 30-bit or maybe 3 each of size 20 bits.
Run your application modulo each of the small primes as your plaintext modulus in BFV, say you get a vector of result = {result1 modulo p1, result 2 modulo p2, … etc},
Then you can use the Chinese Remainder Theorem reconstruction map to get the result back in the “10^{18} domain”.
This paper shows an example of how to apply this trick, check Section 4.2 onwards.
The constraint over the prime you are referring to is to ensure getting the maximum number of slots in BFV.
Thank you for the response!
I have some further comments on this.
CRT will only allow us to recover the output if all the intermediate operations are arithmetic right (+ and *)? What if there are other operations in the middle like (?: , floating-point multiplication, logical AND, right shift)?
I think we can find polynomial approximation for some of these operations like right shift, ReLU, etc.
But what about other operations? How to find polynomial procedures for these?
Yes, you are correct that CRT works nicely only for RNS-friendly operations, such as component-wise addition, multiplication, and scalar multiplication. When we need operations that work with the scale/magnitude of numbers, CRT gets complicated… Probably some procedures can potentially be developed based on the techniques proposed in An Improved RNS Variant of the BFV Homomorphic Encryption Scheme and A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes where large-precision arithmetic is needed only during precomputations, but I would expect these procedures to be quite challenging to implement.
One another idea I had was to use a small plaintext modulus and split a big number into vector of smaller numbers, such that each number is smaller than the plaintext modulus. Can you suggest how arithmetic operations can be achieved for such a vector of Ciphertext if such a setting were to be used? There would be wrapping when plaintext modulus is crossed during additions/multiplications and carry-over involved - If p=7, v1=[2 2 2], v2=[2 2 2], then result of per-slot addition will be [-3 -3 -3]. [-3 -3 -3]+[-3 -3 -3] will involve carry over.
I think you are referring to a positional/radix number system as opposed to RNS. In other words, the small numbers correspond to digits. Theoretically this can be done, but dealing with the carries can be quite complicated and may potentially involve comparisons (or extra operations), which are expensive in BFV… For more information on both radix and CTR representations, I suggest reading Parameter Optimization & Larger Precision for (T)FHE (they are discussed there in the TFHE/FHEW context)