Seal library official example: levels.cpp parsing

This code is mainly about modulus switching. Simply put, the function is to reduce the noise of the ciphertext. This should be in the BGV scheme, but the official example is BFV. There is no such process in BFV. It embeds the modulo switching into the multiplication operation. At the end of the code, it is said that BFV does not need to set the modulus chain, so its own multiplication-related operations should have its own modulo switching. (Personally, I feel that this code should use BGV as an example. The effect of BFV is not obvious, and it is also mentioned later in the code... It should be related to the fact that the SEAL library did not have BGV code at first, and it was added later.)

When the SEALContext is created, the SEAL library will automatically generate a modulus exchange chain. The parameters in the modulus exchange chain are the same as the original parameters. The difference is that the modulus will be reduced, and each layer will remove the last part of the modulus chain. A modulus until the modulo chain is unavailable. The parameter set in each modulus chain has its own unique index, which can be obtained at any time. The larger the index value, the more it is in the front of the chain.

The first is the parameter setting

EncryptionParameters parms(scheme_type::bfv);

size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 50, 30, 30, 50, 50 }));
parms.set_plain_modulus(PlainModulus::Batching(poly_modulus_degree, 20));//only for bfv

SEALContext context(parms);
print_parameters(context);
cout << endl;

The order of the modulus chain is important, the last prime number is called special prime, because all key objects are created at this highest level, while all data objects can only be created at lower levels. A non-strict requirement is that the special prime should be as large as the largest of the other primes in coeff_modules. (we don't know why)

Parameter output result

The method of obtaining the data information of the module exchange chain
SEALContext::key_context_data(): access to key level ContextData
SEALContext::first_context_data(): access to highest data level ContextData
SEALContext::last_context_data(): access to lowest level ContextData

Print die exchange chain data information, a total of 5 layers (4-0)
The first key level

print_line(__LINE__);
cout << "Print the modulus switching chain." << endl;
auto context_data = context.key_context_data();
cout << "----> Level (chain index): " << context_data->chain_index();
cout << " ...... key_context_data()" << endl;
cout << "      parms_id: " << context_data->parms_id() << endl;
cout << "      coeff_modulus primes: ";
cout << hex;
for (const auto &prime : context_data->parms().coeff_modulus())
{
    cout << prime.value() << " ";
}
cout << dec << endl;
cout << "\\" << endl;
cout << " \\-->";

It looks like this, mainly the ID and modulus of the parameter set

remaining data level

context_data = context.first_context_data();
while (context_data)
{
    cout << " Level (chain index): " << context_data->chain_index();
    if (context_data->parms_id() == context.first_parms_id())
    {
        cout << " ...... first_context_data()" << endl;
    }
    else if (context_data->parms_id() == context.last_parms_id())
    {
        cout << " ...... last_context_data()" << endl;
    }
    else
    {
        cout << endl;
    }
    cout << "      parms_id: " << context_data->parms_id() << endl;
    cout << "      coeff_modulus primes: ";
    cout << hex;
    for (const auto &prime : context_data->parms().coeff_modulus())
    {
        cout << prime.value() << " ";
    }
    cout << dec << endl;
    cout << "\\" << endl;
    cout << " \\-->";

    /*
    Step forward in the chain.
    */
    context_data = context_data->next_context_data();
}

In this way, you can see that the modulus chain is getting smaller layer by layer, and the last modulus is removed each time.

When the key is created, the parameters of the key level will be called. The following code creates the key and checks whether the parameters are called

KeyGenerator keygen(context);
auto secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);

print_line(__LINE__);
cout << "Print the parameter IDs of generated elements." << endl;
cout << "    + public_key:  " << public_key.parms_id() << endl;
cout << "    + secret_key:  " << secret_key.parms_id() << endl;
cout << "    + relin_keys:  " << relin_keys.parms_id() << endl;

Compared with the parameter set id of the previous key level, it is the same, indicating that it is indeed called.

The plaintext of BFV does not call the parameter set, but the ciphertext calls

Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);
Plaintext plain("1x^3 + 2x^2 + 3x^1 + 4");
Ciphertext encrypted;
encryptor.encrypt(plain, encrypted);
cout << "    + plain:       " << plain.parms_id() << " (not set in BFV)" << endl;
cout << "    + encrypted:   " << encrypted.parms_id() << endl << endl;

The module exchange function is to reduce the noise caused by the homomorphic operation. Its operation is to switch the parameter set used by itself to the next level parameter in the ciphertext operation to perform the calculation of the next level. This function is irreversible, that is, it cannot Switch up, only switch down. Because, each layer has one less modulus, assuming that the previous one is Q Q Q, the next level is Q ′ Q' Q′, then the essence of the modulo switching operation is to multiply the ciphertext by Q ′ / Q Q'/Q Q′/Q is 1 / q i 1/q_i 1/qi​, the corresponding noise is multiplied by so much, and the purpose of reducing the noise is achieved. The functions provided in the library are as follows,
Evaluator::mod_switch_to_next: switch to the next layer
Evaluator::mod_switch_to: You can switch the parameter id for exchange
The following code shows the modulus switching of each data level

print_line(__LINE__);
cout << "Perform modulus switching on encrypted and print." << endl;
context_data = context.first_context_data();
cout << "---->";
while (context_data->next_context_data())
{
    cout << " Level (chain index): " << context_data->chain_index() << endl;
    cout << "      parms_id of encrypted: " << encrypted.parms_id() << endl;
    cout << "      Noise budget at this level: " << decryptor.invariant_noise_budget(encrypted) << " bits" << endl;
    cout << "\\" << endl;
    cout << " \\-->";
    evaluator.mod_switch_to_next_inplace(encrypted);
    context_data = context_data->next_context_data();
}
cout << " Level (chain index): " << context_data->chain_index() << endl;
cout << "      parms_id of encrypted: " << encrypted.parms_id() << endl;
cout << "      Noise budget at this level: " << decryptor.invariant_noise_budget(encrypted) << " bits" << endl;
cout << "\\" << endl;
cout << " \\-->";
cout << " End of chain reached" << endl << endl;

The results are as follows. It can be seen that the ID of each layer corresponds to the parameter id of the data level above, and the noise budget of each layer is also decreasing.

Doesn't seem to do anything, just switch the number of layers and the noise budget is consumed? The previous article said that the larger the polynomial coefficient modulus, the stronger the computing power, and the computing power is reflected in the noise calculation. Here the mode is reduced.
The noise budget is not 0, the decryption is correct

print_line(__LINE__);
cout << "Decrypt still works after modulus switching." << endl;
decryptor.decrypt(encrypted, plain);
cout << "    + Decryption of encrypted: " << plain.to_string();
cout << " ...... Correct." << endl << endl;

Without modulo switching, calculate the power of 2 and power of 4 of the ciphertext.

cout << "Computation is more efficient with modulus switching." << endl;
print_line(__LINE__);
cout << "Compute the 8th power." << endl;
encryptor.encrypt(plain, encrypted);
cout << "    + Noise budget fresh:                   " << decryptor.invariant_noise_budget(encrypted) << " bits"
     << endl;
evaluator.square_inplace(encrypted);
evaluator.relinearize_inplace(encrypted, relin_keys);
cout << "    + Noise budget of the 2nd power:         " << decryptor.invariant_noise_budget(encrypted) << " bits"
     << endl;
evaluator.square_inplace(encrypted);
evaluator.relinearize_inplace(encrypted, relin_keys);
cout << "    + Noise budget of the 4th power:         " << decryptor.invariant_noise_budget(encrypted) << " bits"
     << endl;

Calculate the 8th power after using modulo switching

evaluator.mod_switch_to_next_inplace(encrypted);
cout << "    + Noise budget after modulus switching:  " << decryptor.invariant_noise_budget(encrypted) << " bits"
     << endl;
evaluator.square_inplace(encrypted);
evaluator.relinearize_inplace(encrypted, relin_keys);
cout << "    + Noise budget of the 8th power:         " << decryptor.invariant_noise_budget(encrypted) << " bits"
     << endl;
evaluator.mod_switch_to_next_inplace(encrypted);
cout << "    + Noise budget after modulus switching:  " << decryptor.invariant_noise_budget(encrypted) << " bits"
     << endl;
decryptor.decrypt(encrypted, plain);
cout << "    + Decryption of the 8th power (hexadecimal) ...... Correct." << endl;
cout << "    " << plain.to_string() << endl << endl;

The result is as follows,

It can be seen that applying modulus swapping in BFV has little effect, which means, after doing enough calculations, there is no harm at all in lowering some coefficients. In some cases, that is, when the ciphertext calculation does not require more noise operations, we can switch to a lower level slightly earlier to speed up the calculation. Decryption can be done at any layer, the lower the number of layers, the lower the modulus, and the faster the calculation speed.

In addition, in BFV, modulus switching is not necessary. In the BFV scheme, this operation is approximately put into the multiplication operation, so there is no need for a too long modulus switching chain, which can be changed by setting so that it only generates the previous Two layers, that is, key level and highest data level (so I should actually take BGV as an example)

context = SEALContext(parms, false);

print it out

cout << "Optionally disable modulus switching chain expansion." << endl;
print_line(__LINE__);
cout << "Print the modulus switching chain." << endl;
cout << "---->";
for (context_data = context.key_context_data(); context_data; context_data = context_data->next_context_data())
{
    cout << " Level (chain index): " << context_data->chain_index() << endl;
    cout << "      parms_id: " << context_data->parms_id() << endl;
    cout << "      coeff_modulus primes: ";
    cout << hex;
    for (const auto &prime : context_data->parms().coeff_modulus())
    {
        cout << prime.value() << " ";
    }
    cout << dec << endl;
    cout << "\\" << endl;
    cout << " \\-->";
}
cout << " End of chain reached" << endl << endl;

This does not generate subsequent chains.

It is needed in BGV, and rescaling is used in ckks, but the principle is basically similar.

Tags: Algorithm

Posted by coalgames on Thu, 01 Dec 2022 20:18:14 +0300