OpenFHE CKKS chooses modulus chain that doesn't guarantee 128 bits of security

Library Questions
1

I slightly changed the advanced CKKS example by replacing the ring dimension and the security level by

parameters.SetRingDim(1 << 16);
parameters.SetSecurityLevel(HEStd_128_classic);

Since I chose the security level as 128 bits and N=2^{16}, I should have the integer modulus (the product of the prime factors) with around 1750 bits. However, it seems that it has 2371 bits, which gives me much less than 128 bits of security.

Do you know what is going wrong here? I thought that by using parameters.SetSecurityLevel(HEStd_128_classic), openFHE would choose the parameters correctly already…

More detail:

std::cout << "Parameters " << parameters << std::endl << std::endl;

outputs this

Parameters scheme: CKKSRNS; ptModulus: 0; digitSize: 0; standardDeviation: 3.19; secretKeyDist: UNIFORM_TERNARY; maxRelinSkDeg: 2; ksTech: HYBRID; scalTech: FLEXIBLEAUTO; batchSize: 0; firstModSize: 60; num LargeDigits: 3; multiplicativeDepth:29; scalingModSize: 59; securityLevel: HEStd_128_classic; ringDim: 65536; evalAddCount: 0; keySwitchCount: 0; encryptionTechnique: STANDARD; multiplicationTechnique: HPS; multiHopModSize: 0; PREMode: INDCPA; multipartyMode: FIXED_NOISE_MULTIPARTY; executionMode: EXEC_EVALUATION; decryptionNoiseMode: FIXED_NOISE_DECRYPT; noiseEstimate: 0; desiredPrecision: 25; statisticalSec urity: 30; numAdversarialQueries: 1

I wrote this function to print the modulus chain:

void print_moduli_chain(const DCRTPoly& poly){
    int num_primes = poly.GetNumOfElements();
    double total_bit_len = 0.0;
    for (int i = 0; i < num_primes; i++) {
        auto qi = poly.GetParams()->GetParams()[i]->GetModulus();
        std::cout << "q_" << i << ": " 
                    << qi
                    << ",  log q_" << i <<": " << log(qi.ConvertToDouble()) / log(2)
                    << std::endl;
        total_bit_len += log(qi.ConvertToDouble()) / log(2);
    }   
    std::cout << "Total bit length: " << total_bit_len << std::endl;
}

and when I run it on the public key, that is,

const std::vector<DCRTPoly>& ckks_pk = keyPair.publicKey->GetPublicElements();
    std::cout << "Moduli chain of pk: " << std::endl;
    print_moduli_chain(ckks_pk[0]);

I get this

q_0: 1152921504606584833, log q_0: 60
q_1: 576460752395173889, log q_1: 59
q_2: 576460752386129921, log q_2: 59
q_3: 576460752405135361, log q_3: 59
q_4: 576460752395960321, log q_4: 59
q_5: 576460752399106049, log q_5: 59
q_6: 576460752284418049, log q_6: 59
q_7: 576460752347332609, log q_7: 59
q_8: 576460752286253057, log q_8: 59
q_9: 576460752319414273, log q_9: 59
q_10: 576460752289005569, log q_10: 59
q_11: 576460752347201537, log q_11: 59
q_12: 576460752289529857, log q_12: 59
q_13: 576460752315482113, log q_13: 59
q_14: 576460752289923073, log q_14: 59
q_15: 576460752342876161, log q_15: 59
q_16: 576460752298180609, log q_16: 59
q_17: 576460752340123649, log q_17: 59
q_18: 576460752321642497, log q_18: 59
q_19: 576460752337502209, log q_19: 59
q_20: 576460752325705729, log q_20: 59
q_21: 576460752331210753, log q_21: 59
q_22: 576460752329113601, log q_22: 59
q_23: 576460752329900033, log q_23: 59
q_24: 576460752328327169, log q_24: 59
q_25: 576460752329506817, log q_25: 59
q_26: 576460752298835969, log q_26: 59
q_27: 576460752319021057, log q_27: 59
q_28: 576460752300015617, log q_28: 59
q_29: 576460752308273153, log q_29: 59
q_30: 1152921504598720513, log q_30: 60
q_31: 1152921504597016577, log q_31: 60
q_32: 1152921504595968001, log q_32: 60
q_33: 1152921504592822273, log q_33: 60
q_34: 1152921504592429057, log q_34: 60
q_35: 1152921504589938689, log q_35: 60
q_36: 1152921504586530817, log q_36: 60
q_37: 1152921504583647233, log q_37: 60
q_38: 1152921504581419009, log q_38: 60
q_39: 1152921504580894721, log q_39: 60
Total bit length: 2371

2

OpenFHE security analysis follows the analysis in the homomorphic encryption standard, which lists recommended (R)-LWE parameters for ring dimensions \{2^{10}, \ldots, 2^{15}\}. For parameters requiring a larger ring dimension than the supported range (as in your case), OpenFHE returns a default ring dimension 2^{16}.

If your application requires such large ring dimensions, you may refer to the LWE estimator to find the ring dimension that offers the desired security level. From experience, it appears to me that you would need a ring dimension 2^{17} to support 128-bit security level for a coefficient modulus of the order ~2300 bits.

I would like to remark that we are working on this issue to support a wider set of parameters in OpenFHE.

3

I want to add further clarification. We have an issue for this: Add entries for N = 64K and N = 128K to the security tables for LWE · Issue #147 · openfheorg/openfhe-development · GitHub The main problem is that the tables of the security standard document do not list higher ring dimensions (we use these tables in OpenFHE) and the estimation for all attacks using the lattice estimator takes quite a bit of time. We are planning to resolve this in in one of the bugfix versions for 1.0.x

4

Hello! Thank you both for the answers. I know that for N=2^16, ternary secret keys and noise parameter sigma=3.2, one has to use modulus chain PQ such that log(PQ) ~= 1730 (I have already used the lattice estimator for this case).

Now I understand that OpenFHE cannot select parameters automatically for such N, but then, how can I manually specify the length of the modulus chain, please?

5

The most straightforward way is to keep changing the multiplicative depth parameter until you reach the bit length you are interested in.

If you are using CKKS, you can also control the size of the moduli chain by setting the parameters: dcrtBits and firstMod but these might affect the precision of your computation, in particular the latter.

6

Well… But this will reduce the bit length of each prime. Instead, is there a way of reducing the number of primes in the modulus chain?

7

If you set the multiplicative depth to a small number, you would have a small modulus.

Try setting 2 in uint32_t levelsUsedBeforeBootstrap = 2; here, that should reduce the total multiplicative depth.

You can also use std::vector<uint32_t> levelBudget = {1, 1}; here to save extra 4 levels in bootstrapping, at the expense that bootstrapping will become slower.

8

Sorry for being naive, but I am new to FHE and learning the implementation. By levelsUsedBeforeBootstrap, do you mean levelsAvailableAfterBootstrap as per the current repository example for CKKS bootstrapping? Also, how would reducing the value from 14 to 2 affect bootstrapping? Would it mean more frequent bootstrapping? I am sure changing the multiplicative depth incur some difference in the performance of the overall bootstrapping example. TIA

9

By levelsUsedBeforeBootstrap, do you mean levelsAvailableAfterBootstrap as per the current repository example for CKKS bootstrapping?

There was some confusion with labeling this variable in the prior version of the example (before next bootstrapping or after the current bootstrapping). It is the same variable.

Also, how would reducing the value from 14 to 2 affect bootstrapping?

Bootstrapping itself would get faster but more bootstrapping invocations would be needed.

10

How is log_q and Q related to the ciphertext modulus chain in the example output presented above. What I mean to understand is, the above output shows 40 log_q bits, each of size 60 bits, which sums up to 2371 bits. So is the value of q=2^40 in this case? wanted to run the above example on lattice simulator

11

In the lattice estimator, you need to use Q (or QP if hybrid key switching is used) as the input for ciphertext modulus. These are the moduli used for the encryption of evaluation keys (PQ). Note that the lattice estimator will take a lot of time to find parameters for such large QP. OpenFHE v1.2 (Release Release v1.2.0 · openfheorg/openfhe-development · GitHub) now includes entries up to 2^{17}. So OpenFHE will automatically choose 2^{17} for you.

12

Hello @Caesar ! I was a little confused about the composition of the modular chain. I set the multDepth=22, scalingModSize = 40, firstModSize = 60, and I used the function print_moduli_chain to output the modular chain, the output showed that q_0,q_1,…q_22 is 40bit, q_23 is 19bit, and q_24,q_25,…,q_29 is 60bit. I want to know why q_23 is 19bit and why there are six 60bit modules.

13

Please create a separate thread for your question with a MWE.

14

Sure, i will create a separate thread for the question