bfv同态加密_同态加密SEAL库的使用及其案例解析

bfv同态加密_同态加密SEAL库的使⽤及其案例解析

核⼼概念

⼤多数加密⽅案由三种功能组成:密钥⽣成、加密和解密。对称密钥加密⽅案使⽤相同的密钥进⾏加密和解密;公钥加密⽅案分别使⽤公钥加

密和私钥解密。因此，公钥加密⽅案允许任何知道公钥的⼈对数据进⾏加密，但是只有知道私钥的⼈才能解密和读取数据。对称密钥加密可

以有效地加密⼤量数据，并⽀持安全的外包云存储。公钥加密是当今实现安全在线通信的⼀个基本概念，但其效率通常⽐对称密钥加密低得

多。

虽然传统的对称和公钥加密可以⽤于安全的存储和通信，但是任何外包的计算都必须在进⾏计算之前删除这些加密层。因此，提供外包计算

能⼒的云服务必须能够访问这些密钥，并实现访问策略以防⽌未经授权的员⼯访问这些密钥。、

同态加密

同态加密是指允许云直接在加密数据上计算，⽽不需要先对数据进⾏解密的加密⽅案。这种加密计算的结果仍然是加密的，并且只能使⽤私

钥(由数据所有者)解密。在过去的⼗年中，⼈们发明了多种具有不同功能和优缺点的同态加密⽅案;其中⼤部分是公钥加密⽅案，尽管可能并

不总是需要公钥功能。

同态加密不是⼀种通⽤技术:只能对加密数据进⾏⼀些计算。它还带来了巨⼤的性能开销，因此在未加密的数据上执⾏已经⾮常昂贵的计算可

能在加密数据上不可⾏。此外，使⽤同态加密加密的数据⽐未加密的数据⼤很多倍，因此使⽤这种技术加密整个⼤型数据库可能没有意义。

相反，有意义的⽤例是在严格的隐私要求完全禁⽌未加密的云计算的场景中，但是计算本⾝是相当轻量级的。

通常，同态加密⽅案有⼀个由数据所有者持有的私钥。对于多个不同的私有数据所有者希望参与协作计算的场景，同态加密可能不是⼀个合

理的解决⽅案。

同态加密不能⽤于使数据科学家绕过GDPR。例如，云服务⽆法使⽤同态加密从加密的客户数据中获取信息。相反，加密计算的结果仍然是

加密的，只能由数据所有者(例如云服务客户)解密。

Microsoft SEAL

Microsoft SEAL是⼀个同态加密库，它允许在加密的整数或实数上执⾏加法和乘法。其他操作，如加密⽐较、排序或正则表达式，在⼤多

数情况下都⽆法使⽤此技术对加密数据进⾏评估。因此，只有程序中特定的隐私关键型云计算部分才能使⽤Microsoft SEAL实现。

将未加密的计算转换为加密数据上的计算并不总是容易或直接的，例如，不可能在加密数据上进⾏分⽀。Microsoft SEAL本⾝有⼀个陡峭

的学习曲线，它要求⽤户理解许多同态加密的特定概念，尽管最终的API并不太复杂。即使⽤户能够使⽤Microsoft SEAL编写和运⾏特定

的计算，⾼效实现和低效实现之间的差异也可能是数量级的，⽽且新⽤户很难知道如何改进他们的计算性能。

Microsoft SEAL提供了两种不同的同态加密⽅案，它们具有⾮常不同的属性。BFV⽅案允许在加密的整数上执⾏模运算。CKKS⽅案允许

对加密的实数或复数进⾏加法和乘法，但只能得到近似的结果。在诸如汇总加密的真实数字、评估加密数据上的机器学习模型或计算加密位

置的距离等应⽤程序中，ckk将是最佳选择。对于需要精确值的应⽤程序，BFV⽅案是惟⼀的选择。

Installing Microsoft SEAL

Windows

Linux and macOS

(1) Global install

(2) Local install

Installing Microsoft SEAL for .NET

(1)Windows

(2)Linux and macOS

程序结构：

SEAL/native/examples/examples.h

六个例⼦:

void example_bfv_basics();

void example_encoders();

void example_levels();

void example_ckks_basics();

void example_rotation();

void example_performance_test();

Helper函数：

Helper function: Prints the name of the example in a fancy banner.

inline void print_example_banner(std::string title)

Helper function: Prints the parameters in a SEALContext.

inline void print_parameters(std::shared_ptr<:alcontext> context)

Helper function: Prints the `parms_id' to std::ostream.

inline std::ostream &operator <

Helper function: Prints a vector of floating-point values.

template

inline void print_vector(std::vector vec, std::size_t print_size = 4, int prec = 3)

Helper function: Prints a matrix of values.

template

inline void print_matrix(std::vector matrix, std::size_t row_size)

Helper function: Print line number.

inline void print_line(int line_number)

SEAL/native/examples/

打印使⽤说明：

int main()

cout << "+---------------------------------------------------------+" << endl;

cout << "| The following examples should be executed while reading |" << endl;

cout << "| comments in associated files in native/examples/. |" << endl;

cout << "+---------------------------------------------------------+" << endl;

cout << "| Examples | Source Files |" << endl;

cout << "+----------------------------+----------------------------+" << endl;

cout << "| 1. BFV Basics | 1_bfv_ |" << endl;

cout << "| 2. Encoders | 2_ |" << endl;

cout << "| 3. Levels | 3_ |" << endl;

cout << "| 4. CKKS Basics | 4_ckks_ |" << endl;

cout << "| 5. Rotation | 5_ |" << endl;

cout << "| 6. Performance Test | 6_ |" << endl;

cout << "+----------------------------+----------------------------+" << endl;

选择例⼦：

switch (lection)

{

ca 1:

example_bfv_basics();

break;

ca 2:

example_encoders();

break;

ca 3:

example_levels();

break;

ca 4:

example_ckks_basics();

break;

ca 5:

example_rotation();

break;

ca 6:

example_performance_test();

break;

例1 example_bfv_basic：

#include "examples.h"

using namespace std;

using namespace al;

void example_bfv_basics()

......

在本例中，我们演⽰了使⽤BFV加密⽅案对加密的整数执⾏简单计算(多项式求值)。

第⼀个任务是设置EncryptionParameters类的实例。

了解不同参数的⾏为⽅式、它们如何影响加密⽅案、性能和安全级别⾮常重要。需要设置三个加密参数:

poly_modulus_degree(多项式模度);

系数模量([密⽂]系数模量);

明⽂模量(明⽂模量;只适⽤于BFV⽅案)。

BFV⽅案不能对加密数据执⾏任意计算。相反，每个密⽂都有⼀个特定的量，称为“不变噪声预算”——简称为“噪声预算”——以⽐特来

衡量。新加密密⽂(初始噪声预算)中的噪声预算由加密参数决定。同态操作以同样由加密参数决定的速率消耗噪声预算。在BFV中，允许对

加密数据进⾏的两种基本操作是加法和乘法，⼀般认为加法与乘法相⽐，在噪声预算消耗⽅⾯⼏乎是免费的。由于顺序乘法的噪声预算消耗

是复合的，因此选择合适的加密参数时最重要的因素是⽤户希望对加密数据进⾏评估的算术电路的乘性深度。⼀旦密⽂的噪声预算达到零，

它就会被破坏得⽆法解密。因此，必须选择⾜够⼤的参数来⽀持所需的计算;否则，即使使⽤密钥，结果也不可能有意义。

EncryptionParameter parms(scheme_type::BFV);

我们设置的第⼀个参数是‘多项式模’的次数。这⼀定是2的正次幂，表⽰2的幂次多项式的次数;没有必要去理解这是什么意思。

较⼤的poly_modulus_degree使密⽂的⼤⼩更⼤，所有的操作都更慢，但允许更复杂的加密计算。推荐值为1024、2048、4096、

8192、16384、32768，但是也可能超出这个范围。

在这个例⼦中，我们使⽤⼀个相对较⼩的多项式模。任何⼩于此值的操作都只允许⾮常有限的加密计算。

size_t poly_modulus_degree = 4096;

_poly_modulus_degree(poly_modulus_degree);

接下来，我们设置[密⽂]“系数模量”(coeff_modules)。该参数是⼀个⼤整数，它是不同素数的乘积，每个素数的⼤⼩最⼤为60位。它被

表⽰为这些素数的⼀个向量，每个素数由smallmodules类的⼀个实例表⽰。coeff_modules的位长是指它的质数因⼦的位长之和。

更⼤的coeff_模数意味着更⼤的噪声预算，因此更加密的计算能⼒。然⽽，coeff_modulus_degree确定了coeff_modul_modules总⽐特

长度的上限，具体如下:

±---------------------------------------------------+

| poly_modulus_degree | max coeff_modulus bit-length |

±--------------------±-----------------------------+

| 1024 | 27 |

| 2048 | 54 |

| 4096 | 109 |

| 8192 | 218 |

| 16384 | 438 |

| 32768 | 881 |

±--------------------±-----------------------------+

1743/5000

这些数字也可以在函数SEAL_HE_STD_PARMS_128_TC中的native/src/al/util/hestdpar .h中找到，也可以从函数

coeff::MaxBitCount(poly_modulus_degree)中获得。

例如，如果poly_modulus_degree为4096，则coeff_modul_modules可以由3个36位素数(108位)组成。

Microsoft SEAL附带⽤于选择coeff_modules的辅助函数。

对于新⽤户来说，最简单的⽅法就是使⽤

CoeffModulus::BFVDefault(poly_modulus_degree),

它返回std::vector，对于给定的poly_modulus_degree，这是⼀个很好的选择。

_coeff_modulus (CoeffModulus:: BFVDefault (poly_modulus_degree));

明⽂模数可以是任何正整数，即使这⾥我们取它为2的幂。事实上，在很多情况下，我们可能希望它是质数;我们将在后⾯的例⼦中看到这⼀

点。明⽂模量决定了明⽂数据类型的⼤⼩和乘法中噪声预算的消耗。因此，为了获得最佳性能，必须尽量保持明⽂数据类型尽可能⼩。新加

密密⽂的噪声预算是

~ log2 (coeff_modulus / plain_modulus)(位)

同态乘法的噪声预算消耗为log2(plain - modulo) + (other terms)。

明⽂模量是特定于BFV⽅案的，在使⽤CKKS⽅案时⽆法设置。

_plain_modulus (256);

既然所有的参数都设置好了，我们就可以开始构建⼀个SEALContext对象了。这是⼀个繁重的类，它检查我们刚刚设置的参数的有效性和

属性。

auto context = SEALContext::Create(parms);

Print the parameters that we have chon.

print_line(__LINE__);

cout << "Set encryption parameters and print" << endl;

print_parameters(context);

cout << endl;

cout << "~~~~~~ A naive way to calculate 2(x^2+1)(x+1)^2. ~~~~~~" << endl;

Microsoft SEAL中的加密⽅案是公钥加密⽅案。对于不熟悉这个术语的⽤户，公钥加密⽅案有⼀个⽤于加密数据的单独公钥和⼀个⽤于解

密数据的单独密钥。通过这种⽅式，多个参与⽅可以使⽤相同的共享公钥对数据进⾏加密，但是只有正确的数据接收⽅可以使⽤密钥对数据

进⾏解密。

现在，我们已经准备好⽣成密钥和公钥。为此，我们需要KeyGenerator类的⼀个实例。构造密钥⽣成器会⾃动⽣成公钥和密钥，可以⽴即

将其读⼊本地变量。

KeyGenerator keygen(context);

PublicKey public_key = _key();

SecretKey cret_key = _key();

为了能够加密，我们需要构造Encryptor的⼀个实例。注意，正如预期的那样，Encryptor只需要公钥。

Encryptor encryptor(context, public_key);

对密⽂的计算是⽤求值程序类执⾏的。在实际的⽤例中，评估器不会由持有密钥的同⼀⽅构建。

Evaluator evaluator(context);

当然，我们希望对结果进⾏解密，以验证⼀切都⼯作正常，因此还需要构造Decryptor实例。注意，解密器需要密钥。

Decryptor decryptor(context, cret_key);

作为⼀个例⼦，我们求4次多项式的值

2x^4 + 4x^3 + 4x^2 + 4x + 2

通过加密的x = 6。多项式的系数可以看作明⽂输⼊，如下所⽰。计算是以明⽂模256为模数进⾏的。

虽然这个例⼦简单易懂，但是没有什么实⽤价值。在后⾯的⽰例中，我们将演⽰如何更有效地计算加密的整数和实数或复数。

BFV⽅案中的明⽂是次数⼩于多项式模的次数的多项式，系数整数模的明⽂模。对于有环理论背景的读者，明⽂空间为多项式商环

Z_T[X]/(X^N+1)，其中N为多项式模数，T为明⽂模数。

⾸先，我们创建⼀个包含常数6的明⽂。对于明⽂元素，我们使⽤⼀个构造函数，该构造函数将所需的多项式作为⼀个字符串，其系数表⽰

为⼗六进制数。

print_line(__LINE__);

int x = 6;

Plaintext x_plain(to_string(x));

cout << "Express x = " + to_string(x) +

" as a plaintext polynomial 0x" + x__string() + "." << endl;

/*

然后对明⽂进⾏加密，⽣成密⽂。

print_line(__LINE__);

Ciphertext x_encrypted;

cout << "Encrypt x_plain to x_encrypted." << endl;

t(x_plain, x_encrypted);

在Microsoft Seal中，⼀个有效的密⽂由两个或多个多项式组成，其中它们的系数是整数 mod(在coeff_modulus中素数的乘积)。密⽂中

多项式的个数称为其“size”，由Ciphertext::size()给出。新加密的密⽂的⼤⼩总是2。

cout << " + size of freshly encrypted x: " << x_() << endl;

/*

There is plenty of noi budget left in this freshly encrypted ciphertext.

*/

cout << " + noi budget in freshly encrypted x: "

<< ant_noi_budget(x_encrypted) << " bits" << endl;

/*

We decrypt the ciphertext and print the resulting plaintext in order to

demonstrate correctness of the encryption.

*/

Plaintext x_decrypted;

cout << " + decryption of x_encrypted: ";

t(x_encrypted, x_decrypted);

cout << "0x" << x__string() << " ...... Correct." << endl;

当使⽤Microsoft SEAL时，以最⼩化最长的顺序乘法链的⽅式进⾏计算通常是有利的。换句话说，加密计算最好以最⼩化计算乘法深度的

⽅式进⾏评估，因为总噪声预算消耗与乘法深度成正⽐。例如，在我们的例⼦计算中，因式分解多项式是有利的

2 x ^ 4 + 4 x ^ 3 + 4 x ^ 2 + 4 + 2 = 2 (x + 1) ^ 2 * (x ^ 2 + 1)

来获得⼀个简单的深度2表⽰。因此，我们分别计算(x + 1)^2

和(x^2 + 1)然后再乘以2。

⾸先，我们计算x^2并添加⼀个明⽂“1”。从打印结果中我们可以清楚地看到，乘法消耗了⼤量的噪⾳预算。⽤户可以改变

plain_modules参数来查看它对噪声预算消耗率的影响

print_line(__LINE__);

cout << "Compute x_sq_plus_one (x^2+1)." << endl;

Ciphertext x_sq_plus_one; //把密⽂记作x_sq_plus_one

(x_encrypted, x_sq_plus_one);

//先利⽤内置函数square ,平⽅x_encrypted,刷新⼊x_sq_plus_one

Plaintext plain_one("1"); //添加明⽂ 1

_plain_inplace(x_sq_plus_one, plain_one);

//利⽤内置函数密⽂加

加密的乘法会导致输出密⽂的⼤⼩增加。更准确地说，如果输⼊密⽂的⼤⼩为M和N，那么同态乘法后的输出密⽂的⼤⼩为M+N-1。在这种

情况下，我们执⾏平⽅，并观察⼤⼩增长和噪声预算消耗。

cout << " + size of x_sq_plus_one: " << x_sq_plus_() << endl;

cout << " + noi budget in x_sq_plus_one: "

<< ant_noi_budget(x_sq_plus_one) << " bits" << endl;

Even though the size has grown, decryption works as usual as long as noi

budget has not reached 0.

Plaintext decrypted_result;

cout << " + decryption of x_sq_plus_one: ";

t(x_sq_plus_one, decrypted_result);

cout << "0x" << decrypted__string() << " ...... Correct." << endl;

/*

Next, we compute (x + 1)^2.

*/

print_line(__LINE__);

cout << "Compute x_plus_one_sq ((x+1)^2)." << endl;

Ciphertext x_plus_one_sq;

_plain(x_encrypted, plain_one, x_plus_one_sq);

_inplace(x_plus_one_sq);

cout << " + size of x_plus_one_sq: " << x_plus_one_() << endl;

cout << " + noi budget in x_plus_one_sq: "

<< ant_noi_budget(x_plus_one_sq)

<< " bits" << endl;

cout << " + decryption of x_plus_one_sq: ";

t(x_plus_one_sq, decrypted_result);

cout << "0x" << decrypted__string() << " ...... Correct." << endl;

/*

Finally, we multiply (x^2 + 1) * (x + 1)^2 * 2.

*/

print_line(__LINE__);

cout << "Compute encrypted_result (2(x^2+1)(x+1)^2)." << endl;

Ciphertext encrypted_result;

Plaintext plain_two("2");

ly_plain_inplace(x_sq_plus_one, plain_two);

ly(x_sq_plus_one, x_plus_one_sq, encrypted_result);

cout << " + size of encrypted_result: " << encrypted_() << endl;

cout << " + noi budget in encrypted_result: "

<< ant_noi_budget(encrypted_result) << " bits" << endl;

cout << "NOTE: Decryption can be incorrect if noi budget is zero." << endl;

cout << endl;

cout << "~~~~~~ A better way to calculate 2(x^2+1)(x+1)^2. ~~~~~~" << endl;

噪声预算已经达到0，这意味着不能期望解密给出正确的结果。这是因为密⽂x_sq_plus_one和x_plus_one_sq都是由3个多项式组成，这

是由于前⾯的平⽅运算造成的，⽽对⼤密⽂的同态运算⽐⼩密⽂的计算消耗更多的噪声预算。在更⼩的密⽂上计算也要便宜得多。

“Relinearization”是⼀种将密⽂的⼤⼩乘回初始⼤⼩2的操作。因此，在下⼀次乘法之前对⼀个或两个输⼊密⽂进⾏再初始化，可以对噪

声增长和性能产⽣巨⼤的积极影响，即使再初始化本⾝有很⼤的计算成本。只可能将⼤⼩为3的密⽂重新初始化为⼤⼩为2的密⽂，因此⽤

户通常希望在每次乘法之后重新初始化，以将密⽂⼤⼩保持为2。

Relinearization需要特殊的“Relinearization密钥”，可以将其视为⼀种公钥。使⽤密钥⽣成器可以很容易地创建重新初始化密钥。

Relinearization在BFV和CKKS⽅案中都是类似地使⽤，但是在本例中我们继续使⽤BFV。我们重复以前的计算，但这次是在每次乘法之后

重新查找。

我们*使⽤KeyGenerator::relin_keys()来创建relinization密钥*。

print_line(__LINE__);

cout << "Generate relinearization keys." << endl;

auto relin_keys = _keys();

/*

We now repeat the computation relinearizing after each multiplication.

*/

print_line(__LINE__);

cout << "Compute and relinearize x_squared (x^2)," << endl;

cout << string(13, ' ') << "then compute x_sq_plus_one (x^2+1)" << endl;

Ciphertext x_squared;

(x_encrypted, x_squared);

cout << " + size of x_squared: " << x_() << endl;

arize_inplace(x_squared, relin_keys);

cout << " + size of x_squared (after relinearization): "

<< x_() << endl;

_plain(x_squared, plain_one, x_sq_plus_one);

cout << " + noi budget in x_sq_plus_one: "

<< ant_noi_budget(x_sq_plus_one) << " bits" << endl;

cout << " + decryption of x_sq_plus_one: ";

t(x_sq_plus_one, decrypted_result);

cout << "0x" << decrypted__string() << " ...... Correct." << endl;

print_line(__LINE__);

Ciphertext x_plus_one;

cout << "Compute x_plus_one (x+1)," << endl;

cout << string(13, ' ')

<< "then compute and relinearize x_plus_one_sq ((x+1)^2)." << endl;

_plain(x_encrypted, plain_one, x_plus_one);

(x_plus_one, x_plus_one_sq);

cout << " + size of x_plus_one_sq: " << x_plus_one_() << endl;

arize_inplace(x_plus_one_sq, relin_keys);

cout << " + noi budget in x_plus_one_sq: "

<< ant_noi_budget(x_plus_one_sq) << " bits" << endl;

cout << " + decryption of x_plus_one_sq: ";

t(x_plus_one_sq, decrypted_result);

cout << "0x" << decrypted__string() << " ...... Correct." << endl;

print_line(__LINE__);

cout << "Compute and relinearize encrypted_result (2(x^2+1)(x+1)^2)." << endl;

ly_plain_inplace(x_sq_plus_one, plain_two);

ly(x_sq_plus_one, x_plus_one_sq, encrypted_result);

cout << " + size of encrypted_result: " << encrypted_() << endl;

arize_inplace(encrypted_result, relin_keys);

cout << " + size of encrypted_result (after relinearization): "

<< encrypted_() << endl;

cout << " + noi budget in encrypted_result: "

<< ant_noi_budget(encrypted_result) << " bits" << endl;

cout << endl;

cout << "NOTE: Notice the increa in remaining noi budget." << endl;

/*

Relinearization clearly improved our noi consumption. We have still plenty

of noi budget left, so we can expect the correct answer when decrypting.

*/

print_line(__LINE__);

cout << "Decrypt encrypted_result (2(x^2+1)(x+1)^2)." << endl;

t(encrypted_result, decrypted_result);

cout << " + decryption of 2(x^2+1)(x+1)^2 = 0x"

<< decrypted__string() << " ...... Correct." << endl;

cout << endl;

/*

For x=6, 2(x^2+1)(x+1)^2 = 3626. Since the plaintext modulus is t to 256,

this result is computed in integers modulo 256. Therefore the expected output

should be 3626 % 256 == 42, or 0x2A in hexadecimal.

*/

运⾏结果