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

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

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.

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

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?

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.

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?

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.