Score:1

How to set parameters (i.e., gen, ords and mvec) for bootstrapping in HElib?

bb flag

I'm using the homomorphic encryption library, HElib, to do experiments. I tried to use bootstrapping with parameters that are not in the table provided with HElib. But I have no idea how to choose the parameters (i.e, gen, ords and mvec) for bootstrapping.

Below is an example in HElib (examples/BGV_binary_arithmetic.cpp)

  // Plaintext prime modulus.
  long p = 2;
  // Cyclotomic polynomial - defines phi(m).
  long m = 4095;
  // Hensel lifting (default = 1).
  long r = 1;
  // Number of bits of the modulus chain.
  long bits = 500;
  // Number of columns of Key-Switching matrix (typically 2 or 3).
  long c = 2;
  // Factorisation of m required for bootstrapping.
  std::vector<long> mvec = {7, 5, 9, 13};
  // Generating set of Zm* group.
  std::vector<long> gens = {2341, 3277, 911};
  // Orders of the previous generators.
  std::vector<long> ords = {6, 4, 6};

My question: In my experiment, I need the ciphertext with the exact number of slots (such as slots= 256, 1024, 4096). Thus, I have to find the proper m, p, bits to generate such a ciphertext with these slots. But for these m, p, bits, I don't know how to set mvec, gens, ords.

Here is a particular example:

    long m = 12800;
    long p = 127;
    long r = 1;
    long bits = 119;
    long c = 2;
    vector<long> mvec = {25, 512};
    vector<long> gens = {2, 128};
    vector<long> ords = {43, 4351};

Throw an exception: terminating with uncaught exception of type helib::LogicError: Bad user-supplied generator

// Some Information about this context:
m = 12800, p = 127, phi(m) = 5120
  ord(p) = 20
  normBnd = 1.23107
  polyNormBnd = 1.23107
  factors = [2 5]
  generator 43 has order (== Z_m^*) of 128
  generator 4351 has order (== Z_m^*) of 2
r = 1
nslots = 256
hwt = 0
ctxtPrimes = [6,7]
specialPrimes = [8]
number of bits = 173

security level = 98.4643

Update: I run an example with the parameters found by HElib (misc/psi/params.cpp), but throw an exception LogicError: rawModSwitch scaled noise exceeds bound: 309684.692524.

The given parameters are: phim=7056, d=28, m=12789, m=(3^2)*7^2*{29}, m/phim(m)=1.81, C=74 D=2 E=2, mvec="[49 261]" gens="[11224 7106]" ords="[42 6]"

The code is written for performing multiple multiplications while checking the noise and performing bootstrapping.

    long m = 12789;
    long p = 127;
    long r = 1;
    long bits = 119;
    long c = 2;
    // Factorisation of m required for bootstrapping.
    vector<long> mvec = {49, 261};
    // Generating set of Zm* group.
    vector<long> gens = {11224, 7106};
    // Orders of the previous generators.
    vector<long> ords = {42, 6};
    
    Context context = ContextBuilder<BGV>()
                                   .m(m)
                                   .p(p)
                                   .r(r)
                                   .gens(gens)
                                   .ords(ords)
                                   .bits(bits)
                                   .c(c)
                                   .bootstrappable(true)
                                   .mvec(mvec)
                                   .build();
    // Key management
    SecKey secret_key(context);
    secret_key.GenSecKey();
    addSome1DMatrices(secret_key);
    addFrbMatrices(secret_key);
    secret_key.genRecryptData();
    const PubKey& public_key = secret_key;
    const EncryptedArray& ea = context.getEA();

    // create a ciphertext
    std::vector<long> ptxt(nslots);
    for (int i = 0; i < nslots; ++i) {
        ptxt[i] = 2;
    }
    Ctxt ctxt(public_key);
    ea.encrypt(ctxt, public_key, ptxt);

    // multiplication and bootstrapping
    for (int i = 0; i < 10; i++) {
        if (ctxt.bitCapacity() <= 50)
        {
            cout << "Begin bootstrapping!" << endl;
            public_key.thinReCrypt(ctxt);
        }
        ctxt.square();
    }

The exception:

Begin bootstrapping!
libc++abi: terminating with uncaught exception of type helib::LogicError: rawModSwitch scaled noise exceeds bound: 309684.692524
terminating with uncaught exception of type helib::LogicError: rawModSwitch scaled noise exceeds bound: 309684.692524
Hilder Vitor Lima Pereira avatar
us flag
I think that Helib can choose the generators and orders for you if you don't pass them to the context.
kelalaka avatar
in flag
[Homomorphic Encryption Standardization](https://crypto.stackexchange.com/a/74939/18298)
Dylan avatar
bb flag
@HilderVitorLimaPereira Hi, Hilder. I have tried to create the context without passing the generators and orders to it, but it failed due to `LogicError: Cyclotomic polynomial mismatch`. Then I run the example given by HElib without passing them to the context, it doesn't work for the same reason. So it seems HElib does not support this.
Dylan avatar
bb flag
@kelalaka Many thanks for your sharing!
Hilder Vitor Lima Pereira avatar
us flag
I have already used the following code and it worked. Helib found the generators by itself. However, it is not using bootstrapping, so maybe that is the catch. You could test... `helib::Context context = helib::ContextBuilder<helib::BGV>().m(16384).p(257).r(1).bits(250).c(3).skHwt(0).build();`
Dylan avatar
bb flag
@HilderVitorLimaPereira, you're right, I used the above code and checked the generated `gens` and `ords` using the provided functions `context.getZMStar().ZmStarGen()` and `context.getZMStar().OrderOf()`. However, I failed to run the code due to `rawModSwitch scaled noise exceeds bound` when I use the params `m = 8471, p=127, bits=200, r=1, c=2, gens = {3744, 2366}, ords = {42, -2}, mvec = {43, 197}` (security level is around `80`). But it's ok for the provided params in `benchmarks/bgv_fatboot.cpp`, although the security level is `0`.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.