SEAL 学习第四天： ckks_basics_seal中ckks的参数选取

SEAL 学习第四天： ckks_basics

简介说明

通常一个好的策略是为CKKS选择参数方案如下:

    (1) 选择一个60位素数作为coeff_modulus中的第一个素数.这将解密时给出最高的精度; 
    (2) 选择另一个60位素数作为coeff_modulus的最后一个元素，,同时这将被用作特殊的素数，应该与其他质数中最大的一样打；
    (3) 选择中间素数彼此接近
1
2
3

我们使用CoeffModulus::Create来生成适当大小的素数。请注意我们的coeff_modulus是200位的总和，这低于

poly_modulus_degree: CoeffModulus::MaxBitCount(8192)返回218。

scale

比例增大输入的浮点系数数据

即使在纯文本元素的CKKS方案基本上是多项式的整数系数 x^n

编码的位精度;自然会影响精度结果。

所以设置一个放大比例系数是很有必要的。

有了scale 必然有rescale

rescale

通常在乘法后执行

目的: 乘法后： scale = scale + scale = 2*scale 即 $ \Delta^{2}\to \Delta $

Encoding & Decoding

计算

对于多项式 不同的计算顺序消耗的噪声预算以及性能不同

在这个样例中:

求 $F(x)=\pi \ast x^3+0.4\ast x+1$

Plaintext plain_coeff3, plain_coeff1, plain_coeff0;
// 编码
encoder.encode(3.14159265, scale, plain_coeff3);// PI
encoder.encode(0.4, scale, plain_coeff1); // 0.4
encoder.encode(1.0, scale, plain_coeff0); // 1


// x^2
evaluator.square(x1_encrypted, x3_encrypted); // x3_encrypted = x1_encrypted * x1_encrypted
evaluator.relinearize_inplace(x3_encrypted, relin_keys);
evaluator.rescale_to_next_inplace(x3_encrypted); // 重新调整scale 规模

// PI * x
evaluator.multiply_plain(x1_encrypted, plain_coeff3, x1_encrypted_coeff3);// x1_encrypted_coeff3 = x1_encrypted * plain_coeff3
evaluator.rescale_to_next_inplace(x1_encrypted_coeff3);

// 0.4*x
evaluator.multiply_plain_inplace(x1_encrypted, plain_coeff1);
evaluator.rescale_to_next_inplace(x1_encrypted);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

然后就可以三项之和；然而,有一个严重的问题是:

​ 这三个术语使用的加密参数都是不同是由于模数从缩放转换而来。

​ 而加密的加法和减法要求输入的level为相同并且加密参数(parms_id)匹配。

​ 如果有不匹配时，求值器将抛出异常。

我们验证可以发现三者的level是不一样的

在这个样例中 level的变化过程

- Product x^2 has scale 2^80 and is at level 2;
- Product PI*x has scale 2^80 and is at level 2;
- We rescaled both down to scale 2^80/P_2 and level 1;
- Product PI*x^3 has scale (2^80/P_2)^2;
- We rescaled it down to scale (2^80/P_2)^2/P_1 and level 0;
- Product 0.4*x has scale 2^80;
- We rescaled it down to scale 2^80/P_2 and level 1;
- The contant term 1 has scale 2^40 and is at level 2.
1
2
3
4
5
6
7
8

三者的scale 虽然接近，但也是不一样的

这里有几种方法来解决这个scale问题

1. 既然P_2和P_1非常接近2 ^ 40,我们可以简单欺骗 Microsoft SEAL，把scale 设置成一样的，因为以及非常接近2^40

   // 重新设置两者的scale
   x3_encrypted.scale() = pow(2.0, 40);    
   x1_encrypted.scale() = pow(2.0, 40);
   1
   2
   3

2. 另一种方法就是将1 编码成 2^80/P_2 在做一个 multiply_plain 将level降到与0.4*x 保持一致

解决掉上面的问题后我们还有加密参数不匹配的问题。这是很容易的通过使用modulus switching (no rescaling) 来解决

CKKS支持modulus switching就像BFV格式一样、

cout << "Normalize encryption parameters to the lowest level." << endl;
parms_id_type last_parms_id = x3_encrypted.parms_id();
evaluator.mod_switch_to_inplace(x1_encrypted, last_parms_id);
evaluator.mod_switch_to_inplace(plain_coeff0, last_parms_id);
1
2
3
4

到现在这三种密文现在都是兼容的，可以进行add运算了

cout << "Compute PI*x^3 + 0.4*x + 1." << endl;
Ciphertext encrypted_result;
evaluator.add(x3_encrypted, x1_encrypted, encrypted_result);
evaluator.add_plain_inplace(encrypted_result, plain_coeff0);
1
2
3
4

结果验证:

输出一个真的，然后将加密的解密解码，做对比验证

Plaintext plain_result;
print_line(__LINE__);
cout << "Decrypt and decode PI*x^3 + 0.4x + 1." << endl;
cout << "    + Expected result:" << endl;
vector<double> true_result;
for (size_t i = 0; i < input.size(); i++)
{
    double x = input[i];
    true_result.push_back((3.14159265 * x * x + 0.4) * x + 1);
}
print_vector(true_result, 3, 7);

/*
    Decrypt, decode, and print the result.
 */
decryptor.decrypt(encrypted_result, plain_result);
vector<double> result;
encoder.decode(plain_result, result);
cout << "    + Computed result ...... Correct." << endl;
print_vector(result, 3, 7);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

源代码

#include "examples.h"

using namespace std;
using namespace seal;


void example_ckks_basics() {
	
	print_example_banner("Example: CKKS Basics");
	

	/*
	In this example we demonstrate evaluating a polynomial function

		PI*x^3 + 0.4*x + 1

	on encrypted floating-point input data x for a set of 4096 equidistant points
	in the interval [0, 1]. This example demonstrates many of the main features
	of the CKKS scheme, but also the challenges in using it.

	We start by setting up the CKKS scheme.
	*/

	EncryptionParameters parms(scheme_type::ckks);
	
	size_t poly_modulus_degree = 8192;  //long long unsigned int
	parms.set_poly_modulus_degree(poly_modulus_degree);
	parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 60, 40, 40, 60 }));
	/*
	* 我们选择初始比例为2^40 
	* this leaves us 60-40=20 bits of precision before the decimal point, and enough (roughly
    10-20 bits) of precision after the decimal point. Since our intermediate
    primes are 40 bits (in fact, they are very close to 2^40), we can achieve
    scale stabilization as described above.
	*/
	double scale = pow(2.0, 40);

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

	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);
	GaloisKeys galois_keys;
	keygen.create_galois_keys(galois_keys);

	Encryptor encryptor(context, public_key);
	Evaluator evaluator(context);
	Decryptor decryptor(context, secret_key);
	
	CKKSEncoder encoder(context);
	size_t slot_count = encoder.slot_count();
	cout << "Number of slots: " << slot_count << endl;

	vector<double> input;
	input.reserve(slot_count); // 申请空间

	double curr_point = 0;
	//static_cast<double> 将size_t 转成成double 在运算
	double step_size = 1.0 / (static_cast<double>(slot_count) - 1); // 
	for (size_t i = 0; i < slot_count; i++)
	{
		input.push_back(curr_point);
		curr_point += step_size;
	}
	cout << "Input vector: " << endl;
	print_vector(input,3,7); // 打印vector 前3 项后3项,  保留小数点后7位

	cout << "Evaluating polynomial PI*x^3 + 0.4x + 1 ..." << endl;

	Plaintext plain_coeff3, plain_coeff1, plain_coeff0;
	// 编码
	encoder.encode(3.14159265, scale, plain_coeff3);
	encoder.encode(0.4, scale, plain_coeff1);
	encoder.encode(1.0, scale, plain_coeff0);

	Plaintext x_plain;
	print_line(__LINE__);
	cout << "Encode input vectors." << endl;
	encoder.encode(input, scale, x_plain);
	// 加密
	Ciphertext x1_encrypted;
	encryptor.encrypt(x_plain, x1_encrypted);
	/*
	* 为了计算x^3，我们首先计算x^2并重新线性化。然而，scale已经现在变成了2的80次方。
	*/


	// x^2
	Ciphertext x3_encrypted;
	print_line(__LINE__);
	cout << "Compute x^2 and relinearize:" << endl;
	evaluator.square(x1_encrypted, x3_encrypted); // x3_encrypted = x1_encrypted * x1_encrypted

	evaluator.relinearize_inplace(x3_encrypted, relin_keys);

	cout << "    + Scale of x^2 before rescale: " << log2(x3_encrypted.scale()) << " bits" << endl;

	/*
	* 现在重新调节;rescale
	* 除了modulus switch 方法外，scale 减少的系数等于被转移的质数（40位质数）
	* 因此,	新的比例尺应该接近2^40。然而，scale != 2^40 :这是因为40位素数只是接近2^40。
	* 
	*/
	print_line(__LINE__);
	cout << "Rescale x^2." << endl;
	evaluator.rescale_to_next_inplace(x3_encrypted); // 重新调整scale 规模
	cout << "    + Scale of x^2 after rescale: " << log2(x3_encrypted.scale()) << " bits" << endl;

	/*
	* 现在x3_encrypted与x1_encrypted处于不同的级别
	* 这阻止了我们 x3_encrypted*x1_encrypted 来计算x^3
	* 因此通过modulus switch 链 将x1_encrypted 切换到与x3_encrypted 同一级别,
	* 但又需要计算PI* x^3  所以 我们先计算 PI*x  然后调整scale 从2^80 -> 2^40 
	* 然后在计算 Pi*x * x^2 
	* 
	*/
	print_line(__LINE__);

	// PI * x
	cout << "Compute and rescale PI*x." << endl;
	Ciphertext x1_encrypted_coeff3;
	evaluator.multiply_plain(x1_encrypted, plain_coeff3, x1_encrypted_coeff3);// x1_encrypted_coeff3 = x1_encrypted * plain_coeff3
	cout << "    + Scale of PI*x before rescale: " << log2(x1_encrypted_coeff3.scale()) << " bits" << endl;
	evaluator.rescale_to_next_inplace(x1_encrypted_coeff3);
	cout << "    + Scale of PI*x after rescale: " << log2(x1_encrypted_coeff3.scale()) << " bits" << endl;
	
	//(PI*x)*x^2.
	print_line(__LINE__);
	cout << "Compute, relinearize, and rescale (PI*x)*x^2." << endl;
	evaluator.multiply_inplace(x3_encrypted, x1_encrypted_coeff3);
	evaluator.relinearize_inplace(x3_encrypted, relin_keys);
	cout << "    + Scale of PI*x^3 before rescale: " << log2(x3_encrypted.scale()) << " bits" << endl;
	evaluator.rescale_to_next_inplace(x3_encrypted);
	cout << "    + Scale of PI*x^3 after rescale: " << log2(x3_encrypted.scale()) << " bits" << endl;

	// 0.4*x
	print_line(__LINE__);
	cout << "Compute and rescale 0.4*x." << endl;
	evaluator.multiply_plain_inplace(x1_encrypted, plain_coeff1);
	cout << "    + Scale of 0.4*x before rescale: " << log2(x1_encrypted.scale()) << " bits" << endl;
	evaluator.rescale_to_next_inplace(x1_encrypted);
	cout << "    + Scale of 0.4*x after rescale: " << log2(x1_encrypted.scale()) << " bits" << endl;

	/*
	* 现在我们希望计算这三项的和。然而,有一个严重的问题是:
	这三个术语使用的加密参数都是不同是由于模数从缩放转换而来。
	加密的加法和减法要求输入的刻度为相同，
	并且加密参数(parms_id)匹配。如果有不匹配时，求值器将抛出异常。
	*/
	cout << endl;
	print_line(__LINE__);
	cout << "Parameters used by all three terms are different." << endl;
	cout << "    + Modulus chain index for x3_encrypted: "
		<< context.get_context_data(x3_encrypted.parms_id())->chain_index() << endl;
	cout << "    + Modulus chain index for x1_encrypted: "
		<< context.get_context_data(x1_encrypted.parms_id())->chain_index() << endl;
	cout << "    + Modulus chain index for plain_coeff0: "
		<< context.get_context_data(plain_coeff0.parms_id())->chain_index() << endl;
	cout << endl;

	print_line(__LINE__);
	cout << "The exact scales of all three terms are different:" << endl;
	ios old_fmt(nullptr);
	old_fmt.copyfmt(cout);
	cout << fixed << setprecision(10);
	cout << "    + Exact scale in PI*x^3: " << x3_encrypted.scale() << endl;
	cout << "    + Exact scale in  0.4*x: " << x1_encrypted.scale() << endl;
	cout << "    + Exact scale in      1: " << plain_coeff0.scale() << endl;
	cout << endl;
	cout.copyfmt(old_fmt);


	print_line(__LINE__);
	cout << "Normalize scales to 2^40." << endl;
	x3_encrypted.scale() = pow(2.0, 40);
	x1_encrypted.scale() = pow(2.0, 40);
	/*
	* 我们还有加密参数不匹配的问题。这是很容易的通过使用modulus switching (no rescaling) 来解决
	*/
	print_line(__LINE__);
	cout << "Normalize encryption parameters to the lowest level." << endl;
	parms_id_type last_parms_id = x3_encrypted.parms_id();
	evaluator.mod_switch_to_inplace(x1_encrypted, last_parms_id);
	evaluator.mod_switch_to_inplace(plain_coeff0, last_parms_id);

	/*
	到现在这三种密文现在都是兼容的，可以进行add运算了
	*/
	print_line(__LINE__);
	cout << "Compute PI*x^3 + 0.4*x + 1." << endl;
	Ciphertext encrypted_result;
	evaluator.add(x3_encrypted, x1_encrypted, encrypted_result);
	evaluator.add_plain_inplace(encrypted_result, plain_coeff0);


	Plaintext plain_result;
	print_line(__LINE__);
	cout << "Decrypt and decode PI*x^3 + 0.4x + 1." << endl;
	cout << "    + Expected result:" << endl;
	vector<double> true_result;
	for (size_t i = 0; i < input.size(); i++)
	{
		double x = input[i];
		true_result.push_back((3.14159265 * x * x + 0.4) * x + 1);
	}
	print_vector(true_result, 3, 7);

	/*
	Decrypt, decode, and print the result.
	*/
	decryptor.decrypt(encrypted_result, plain_result);
	vector<double> result;
	encoder.decode(plain_result, result);
	cout << "    + Computed result ...... Correct." << endl;
	print_vector(result, 3, 7);
	return;
}
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222