当前位置: 首页 > news >正文

同态加密和SEAL库的介绍(六)BGV 方案

         前面介绍 BFV 和 CKKS 加密方案,这两者更为常用。并且也解释了 Batch Encoder 和 级别的概念,这对接下来演示 BGV 会很有帮助。

一、BGV简介

        BGV (Brakerski-Gentry-Vaikuntanathan) 方案 是一种基于环学习同态加密(RLWE)问题的加密方案。BGV 方案可以实现任意计算电路的同态加密,特别适合于加密数据的复杂运算。

特点

  • 同态运算:支持加法和乘法的任意组合,这意味着它可以评估任意计算电路。
  • 级联密文:密文可以通过一系列同态运算来处理,而不需要在每一步进行解密和重新加密。
  • 噪声管理:在每次同态运算之后,密文中的噪声会增加。BGV 方案采用了噪声管理技术(例如重新线性化和模数切换)来控制噪声增长,确保运算的正确性。

优点

  • 灵活性:支持任意复杂的计算。
  • 效率:通过噪声管理技术提高了运算效率。
  • 安全性:基于环学习同态加密问题的安全性高。

缺点

  • 复杂性:实现和使用BGV方案比一些其他方案更为复杂。
  • 资源消耗:噪声管理和重新线性化等操作增加了计算和存储的开销。

二、3种方案比较:

先看发展顺序

  • BGV 方案:2011年 Brakerski、Gentry 和 Vaikuntanathan 提出。
  • BFV 方案:2012年 Fan 和 Vercauteren 提出。
  • CKKS 方案:2017年 Cheon、Kim、Kim 和 Song 提出。

分别的适用场景:

  • 如果需要对整数进行精确计算,BFV 方案是一个好的选择。
  • 如果需要对浮点数进行近似计算,CKKS 方案是更合适的。
  • 如果需要复杂的计算电路,BGV 方案提供了最大的灵活性。

        每种方案都有其独特的优势和适用场景,在实际应用中,选择适合的方案可以最大化地发挥同态加密技术的优势。

三、BGV 示例

        在本示例中,计算8次多项式 x^8 ,并且在整数 1、2、3、4上的加密 x。多项式的系数可以看作是明文输入计算在 plain_modulus == 1032193 模数下进行。

        在BGV方案中对加密数据进行计算类似于BFV。这个例子的主要目的是解释BFV和BGV在密文系数模数选择和噪声控制方面的区别

3.1 参数设置和创建实例

这里先使用 BFVDefault 创建 coeff_modulus,后面会介绍如何更好的设置。

EncryptionParameters parms(scheme_type::bgv);
size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::BFVDefault(poly_modulus_degree));
parms.set_plain_modulus(PlainModulus::Batching(poly_modulus_degree, 20));
SEALContext context(parms);KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);
Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);

        这里想再次强调一下,因为用的是 Batch 批处理,所以在设置 plain_modulus 的时候,要求是与 2倍 poly_modulus_degree 同余 1 的素数,这与普通的 Encoder 要求不同。上面代码中是用 PlainModulus::Batching 自动生成满足条件的随机数。
        这里输出设置的参数:

3.2 设置输入并编码

        批处理和槽操作在 BFV 和 BGV 中是相同的:

BatchEncoder batch_encoder(context);
size_t slot_count = batch_encoder.slot_count();
size_t row_size = slot_count / 2;

        这里特意设置 row_size 变量,是因为之前讲批处理的时候,强调过内部在逻辑上会编码成两行,故其实就是  \left [ 2, slotcount /2\right ] 。当然这个结构对于编码和计算是基本无感的,只有在考虑行旋转和列旋转的时候会有影响,这个下一篇会具体介绍(挖坑 + 1)。

vector<uint64_t> pod_matrix(slot_count, 0ULL);
pod_matrix[0] = 1ULL;
pod_matrix[1] = 2ULL;
pod_matrix[2] = 3ULL;
pod_matrix[3] = 4ULL;
Plaintext x_plain;
batch_encoder.encode(pod_matrix, x_plain);

这里对编码结果打印输出一下:


3.3 直接运算

Ciphertext x_encrypted;
cout << "Encrypt x_plain to x_encrypted." << endl;
encryptor.encrypt(x_plain, x_encrypted);
cout << "+ noise budget in freshly encrypted x: " << decryptor.invariant_noise_budget(x_encrypted) << " bits" << endl;

这里先对输入进行加密,并输出噪声预算:


先计算 x^2

Ciphertext x_squared;
evaluator.square(x_encrypted, x_squared);
cout << "+ size of x_squared: " << x_squared.size() << endl;
evaluator.relinearize_inplace(x_squared, relin_keys);
cout << "+ size of x_squared (after relinearization): " << x_squared.size() << endl;
cout << "+ noise budget in x_squared: " << decryptor.invariant_noise_budget(x_squared) << " bits" << endl;

        因为是 密文乘密文,为了减少乘法后的密文大小,这里进行了重新线性化,并输出了噪声预算,同时进行解密验证:

可以看出,运算中间结果是正确的,并且重新线性化后,密文大小从3减小到2。


再计算 x^4

Ciphertext x_4th;
evaluator.square(x_squared, x_4th);
cout << "+ size of x_4th: " << x_4th.size() << endl;
evaluator.relinearize_inplace(x_4th, relin_keys);
cout << "+ size of x_4th (after relinearization): " << x_4th.size() << endl;
cout << "+ noise budget in x_4th: " << decryptor.invariant_noise_budget(x_4th) << " bits" << endl;

同样进行了重新线性化,并输出目前噪声预算,同时进行解密验证:

可以看出这里的噪声预算下降的特别快,只剩 35 bits 了。


最后计算 x^8

Ciphertext x_8th;
evaluator.square(x_4th, x_8th);
cout << "+ size of x_8th: " << x_8th.size() << endl;
evaluator.relinearize_inplace(x_8th, relin_keys);
cout << "+ size of x_8th (after relinearization): " << x_8th.size() << endl;
cout << "+ noise budget in x_8th: " << decryptor.invariant_noise_budget(x_8th) << " bits" << endl;

        噪声预算已经达到0,这意味着解密无法得到正确的结果。故此,引出 BGV需要模数切换以减少噪声增长!


3.4 加入模数切换的运算

下面演示在每次重新线性化后插入模数切换:(避免啰嗦,这里直接完整计算)

cout << "+ noise budget in x_squared (previously): " << decryptor.invariant_noise_budget(x_squared) << " bits" << endl;
evaluator.square(x_encrypted, x_squared);
evaluator.relinearize_inplace(x_squared, relin_keys);
evaluator.mod_switch_to_next_inplace(x_squared);
cout << "+ noise budget in x_squared (with modulus switching): " << decryptor.invariant_noise_budget(x_squared) << " bits" << endl;evaluator.square(x_squared, x_4th);
evaluator.relinearize_inplace(x_4th, relin_keys);
evaluator.mod_switch_to_next_inplace(x_4th);
cout << "+ noise budget in x_4th (with modulus switching): " << decryptor.invariant_noise_budget(x_4th) << " bits" << endl;evaluator.square(x_4th, x_8th);
evaluator.relinearize_inplace(x_8th, relin_keys);
evaluator.mod_switch_to_next_inplace(x_8th);
cout << "+ noise budget in x_8th (with modulus switching): " << decryptor.invariant_noise_budget(x_8th) << " bits" << endl;decryptor.decrypt(x_8th, decrypted_result);
batch_encoder.decode(decrypted_result, pod_result);

这里对中间结果也进行解密,并输出其噪声预算的变化:

        这里仔细对比可以发现:虽然通过模数切换 x_squared 的噪声预算比之前少,但噪声预算的消耗速率较慢,故最后可以正确解密。

四、总结

        通过之前的介绍实验,我们能发现,有时候进行模数切换会损耗噪声预算,但是进行到一定乘法深度后,再进行切换就不会损耗噪声,这种情况是一定适合加入模数切换的。
        同时上面发现虽然降低了 x_squared 的噪声预算,但是噪声预算的消耗减慢,故这种情况也适合加入模数切换

        但是这些不意味着在每次计算后都应该进行模数切换,因为要权衡减少的预算和减缓消耗的速度,最好自己进行实验比对。"故为了在应用中实现噪声预算的最佳消耗速率,需要仔细选择插入模数切换的位置,并手动选择 coeff_modulus。"


下篇介绍对密文进行的 行旋转 和 列旋转(未完待续。。。)

相关文章:

  • 北京网站建设多少钱?
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Android开发 java回调
  • 学习日志8.8--防火墙精细化策略管控
  • 【算法模板】基础:反悔贪心
  • NAT、服务代理、内网穿透
  • WPF篇(3)- WrapPanel控件(瀑布流布局)+DockPanel控件(停靠布局)
  • 全新博客X主题/简约WordPress主题模板/主题巴巴/免授权版源码+自适应设计
  • Vue+Element Plus后台管理主界面搭建实现
  • MySQL:基本概念,DDL语句,数据库约束,索引视图
  • 低代码开发
  • 【MySQL】数据基本的增删改查操作
  • 聊聊使用场景法进行性能测试
  • 科技赋能生活——便携气象站
  • 假如有一个嵌套集合,怎么通过stream流将集合放到一个集合之中?
  • MySQL数据库基础:约束
  • 【Android】手写笔适配
  • [LeetCode] Wiggle Sort
  • 5分钟即可掌握的前端高效利器:JavaScript 策略模式
  • ES6之路之模块详解
  • go append函数以及写入
  • jdbc就是这么简单
  • Laravel 中的一个后期静态绑定
  • Linux编程学习笔记 | Linux IO学习[1] - 文件IO
  • nginx 配置多 域名 + 多 https
  • Puppeteer:浏览器控制器
  • zookeeper系列(七)实战分布式命名服务
  • 翻译:Hystrix - How To Use
  • 记录一下第一次使用npm
  • 使用iElevator.js模拟segmentfault的文章标题导航
  • 算法-插入排序
  • 通过npm或yarn自动生成vue组件
  • shell使用lftp连接ftp和sftp,并可以指定私钥
  • 阿里云移动端播放器高级功能介绍
  • 正则表达式-基础知识Review
  • ​ 全球云科技基础设施:亚马逊云科技的海外服务器网络如何演进
  • ​configparser --- 配置文件解析器​
  • ​必胜客礼品卡回收多少钱,回收平台哪家好
  • # Swust 12th acm 邀请赛# [ E ] 01 String [题解]
  • ###51单片机学习(2)-----如何通过C语言运用延时函数设计LED流水灯
  • #define与typedef区别
  • #if和#ifdef区别
  • (3)选择元素——(14)接触DOM元素(Accessing DOM elements)
  • (Matlab)基于蝙蝠算法实现电力系统经济调度
  • (MonoGame从入门到放弃-1) MonoGame环境搭建
  • (二)Kafka离线安装 - Zookeeper下载及安装
  • (二)构建dubbo分布式平台-平台功能导图
  • (二)换源+apt-get基础配置+搜狗拼音
  • (转)Android中使用ormlite实现持久化(一)--HelloOrmLite
  • (转)ORM
  • (转)setTimeout 和 setInterval 的区别
  • (转载)OpenStack Hacker养成指南
  • .bat批处理(十一):替换字符串中包含百分号%的子串
  • .cfg\.dat\.mak(持续补充)
  • .NET BackgroundWorker
  • .NET CF命令行调试器MDbg入门(三) 进程控制
  • .Net Core 中间件与过滤器