Search code examples
c++seal

Choosing the suitable parameters for SEAL and clarifying some mathematical operations

A) I'm having trouble to understand the relationship between those setting:

parms.set_poly_modulus("1x^2048 + 1");
parms.set_coeff_modulus(coeff_modulus_128(2048));
parms.set_plain_modulus(1 << 8);

and this table from the SEAL manual.

enter image description here

I'm interested in particular in the number 54 and how was it calculated in respect to parms.set_poly_modulus("1x^2048 + 1") and parms.set_coeff_modulus(coeff_modulus_128(2048)).

B) I'm trying to find the right parameters for my use case. Let's say I have 10000 fractional numbers between -180 and +180 and I want to encode each of those numbers using the FractionalEncoder. The preformed operations are going to be: subtract, add, multiply, square and exponentiate. The result is going to be saved in a separate Ciphertext variable.

So in respect to my use case what are the optimal parameters for:

  1. n, q, t in

    parms.set_poly_modulus("1x^n + 1");
parms.set_coeff_modulus(coeff_modulus_128(q));
parms.set_plain_modulus(t);

  2. a and b in seal::FractionalEncoder encoder(context.plain_modulus(), context.poly_modulus(), a, b, 2). I'm using a = 512 and b = 128, which is way too high for my use case.

How can I calculate those parameters myself if my use case changes?

Solution

  • A) In your example you are using a polynomial modulus of dimension 2048 and the 128-bit security level default value for the coefficient modulus. To see what that value precisely is, take a look at SEAL/seal/util/globals.cpp. The coefficient modulus is a vector of SmallModulus objects, which are positive integers representing up to 60-bit factors of the total coefficient modulus. For example, for your parameters the coefficient modulus consists of just one single prime number factor 0x3fffffff000001, but you'll see that for larger parameters it can have many more factors.

    The security level depends on both the degree of the polynomial modulus (larger is higher security) and the bit-length of the total coefficient modulus (smaller is high security). Thus, for a fixed polynomial modulus there should be a largest acceptable coefficient modulus providing a fixed level of security. Since it is not at all easy to know what this upper bound on the coefficient modulus is, SEAL provides it conveniently as the default value through coeff_modulus_128 (and coeff_modulus_192 and coeff_modulus_256 for higher security levels). In some cases you may want to use a smaller coefficient modulus than the default, but you should never use a larger one unless you really know what you are doing (and probably not even then). The bit-length of 54 bits is obtained using Martin Albrecht's LWE estimator: https://bitbucket.org/malb/lwe-estimator.

    B) A typical workflow in determining parameters in this kind of situation would be to first figure out a large enough plain_modulus so that you get correctness for your computation. If you run out of noise budget, just tune up your coeff_modulus until it works.

    Once you have found a large enough plain_modulus, try to optimize coeff_modulus by setting it to a smallest value leaving you with non-zero noise budget. For simplicity, you could just try the different default values obtained through coeff_modulus_128. If you really care a lot about performance you may want to hand-pick your coeff_modulus prime numbers to really find the smallest value that works.

    Next, choose your poly_modulus to be large enough so that your total coefficient modulus is at most equal to the default value for that poly_modulus degree.

    Finally you may want to hand-tune the decomposition_bit_count used in relinearization. By default you should use the value 60 which results in better computational performance but more noise growth. In some cases you may want to drop this to e.g. 30, if you happen to be in a situation where some extra noise budget saved would allow you to switch to smaller encryption parameters. In most cases this level of fine-tuning should not be necessary.

    What exactly the resulting optimal parameters will be depends totally on your computation, so without very specific details it's impossible to give a direct answer here.

    Parametrization of the FractionalEncoder is a different matter. I would recommend experimenting with different values to get an idea of how these choices affect accuracy. What is wrong with the a=512, b=128 choice?