3_levels

在SEAL中，一组加密参数(不包括随机数生成器)由参数的SHA-3唯一标识。这个哈希值称为"parms_id"，任何参数的改变都会导致哈希值的改变。

当为给定的加密参数创建SEALContext时，SEAL自动创建一个"模数转换链"，链中的参数与原始参数是相同的，但系数模数的大小沿着链向下递减。更准确地说，链中的每个参数集都试图从前一个集合中移除最后一个系数模数素数；这种情况一直持续到参数集不再有效为止(例如，plain_modulus大于剩余的coeff_modulus)。遍历链并访问所有参数集是很容易的。此外，链中的每个参数集都有一个"链索引"，该索引表示其在链中的位置，最后一个参数集的索引为0。如果一组加密参数或携带这些参数的对象的链索引更大，则称其在链中的级别更高。

链中的每一组参数都包含SEALContext创建时执行的唯一预计算，存储在SEALContext::ContextData对象中。该链基本上是一个SEALContext::ContextData对象的链表，每个节点都可以通过特定参数的parms_id来标识(poly_modulus_degree保持不变，但coeff_modulus会变化)。

1
2
3
4
EncryptionParameters parms(scheme_type::bfv);

size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);

本例中，我们使用自定义的coeff_modulus，包含size为50、30、30、50和50位的个素数

1
CoeffModulus::MaxBitCount(poly_modulus_degree)

返回218(大于50+30+30+50+50=210)

由于模数转换链的关系，五个素数的顺序是重要的。最后一个素数具有特殊含义，称之为"特殊素数"。因此，模数转换链中的第一个参数集是唯一涉及到特殊素数的参数集。所有密钥对象，如SecretKey都是在这个最高级别创建的。所有数据对象(如密文)只能在较低的级别上。特殊模数应该与coeff_modulus中最大质数一样大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
          special prime +---------+
                                  |
                                  v
coeff_modulus: { 50, 30, 30, 50, 50 }  +---+  Level 4 (all keys; `key level')
                                           |
                                           |
    coeff_modulus: { 50, 30, 30, 50 }  +---+  Level 3 (highest `data level')
                                           |
                                           |
        coeff_modulus: { 50, 30, 30 }  +---+  Level 2
                                           |
                                           |
            coeff_modulus: { 50, 30 }  +---+  Level 1
                                           |
                                           |
                coeff_modulus: { 50 }  +---+  Level 0 (lowest level)
1
2
3
4
5
6
7
8
9
10
11
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 50, 30, 30, 50, 50 }));

/*
In this example the plain_modulus does not play much of a role; we choose
some reasonable value.
*/
parms.set_plain_modulus(PlainModulus::Batching(poly_modulus_degree, 20));

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

提供了一些简便方法来访问重要level的SEALContext::ContextData

1
2
3
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

遍历每个参数集并打印parms_id

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
print_line(__LINE__);
cout << "Print the modulus switching chain." << endl;

/*
First print the key level parameter information.
*/
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 << " \\-->";

/*
Next iterate over the remaining (data) levels.
*/
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();
}
cout << " End of chain reached" << endl << endl;

/*
We create some keys and check that indeed they appear at the highest level.
*/
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;

Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);

在BFV方案中，明文没有parms_id参数，但密文有，注意最高数据level的新加密密文

1
2
3
4
5
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;

"模数切换"是一种改变密文参数的技术。函数Evaluaor::mod_switch_to_next切换到链的下一层，Evaluator::mod_switch_to切换到与给定parms_id对应的链下的参数集。但无法在链中向上切换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;

正确解密

1
2
3
4
5
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;

好处：密文的大小线性取决于系数模数中素数的数量。因此，如果不需要或不打算对给定的密文执行任何进一步的计算，那么在将其发送回密钥持有者进行解密之前，我们不妨将其切换到链中的最小(最后的)参数集。

首先重新创建原始密文并执行计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;

模数切换对噪声预算没有任何影响

1
2
3
evaluator.mod_switch_to_next_inplace(encrypted);
cout << "    + Noise budget after modulus switching:  " << decryptor.invariant_noise_budget(encrypted) << " bits"
     << endl;

这意味着在做足够的计算后，降低一些系数模数没有任何坏处。在某些情况下，可能想要更早地切换到较低level，这牺牲了过程中的一些噪声预算，通过较小的参数获得计算性能。

1
2
3
4
5
6
7
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;

密文仍然可以正确解密，它的大小是非常小的，计算高效。解密器可以用于解密在模数转换链上任何level的密文

1
2
3
decryptor.decrypt(encrypted, plain);
cout << "    + Decryption of the 8th power (hexadecimal) ...... Correct." << endl;
cout << "    " << plain.to_string() << endl << endl;

在BFV中，模数切换是不必呀的，某些情况下，除了最高两个级别，用户可能不希望创建模数转换链，可以通过SEALContext设置

1
context = SEALContext(parms, false);

检查是否只有最高两个level

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;

SEAL
SEAL FHE 密码学

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！