前言
时光飞逝,前段时间我们一直在致力于分析SEAL库比较底层的核心代码,遵循的思路也是从底层往上层的应用层去挖掘,这样有利也有弊吧,好处自然就是深入了解底层实现机制,弊端就是缺少一个整体的把握。
so,从本篇开始,我们开始试图暂时跳脱出native/src文件夹,主要是底层代码基于我们的分工也完成的差不多了,接下来的一个月也到了收获的时节,我将开始试图分析examples文件夹下的代码。
与之前的工作相比,这些代码显得更具整体性,也能更好体现出SEAL的工作原理以及流程,算是对前面的集大成者了,因此很有分析的必要。
BFV
本篇我们将分析examples/1_bfv_basics.cpp。看一看SEAL对于bfv是如何实现的。
先照例补充一些理论基础。
对于全同态加密,之前介绍过了。经过研究,我们发现,现在主流的研究方案包括 FHEW、TFHE、GSW、BGV、BFV、CKKS。
其中 FHEW、TFHE、GSW为布尔电路上的实现,其特性:
- 快速比较
- 支持任意布尔电路
- 快速 bootstrapping(噪声刷新过程,减少因密文计算而产生的噪音,降低失败可能性)
BGV、BFV是算数电路上的实现,其特性:
- 在整数向量上进行高效的SIMD计算(使用批处理)
- 快速高精度整数算术
- 快速向量的标量乘法
- Leveled design(通常不使用bootstrapping)
CKKS则是17年才提出来的,其特性:
- 快速多项式近似计算
- 相对快速的倒数和离散傅里叶变换
- 深度近似计算,如逻辑回归学习
- 在实数向量上进行高效的SIMD计算(使用批处理)
- Leveled design(通常不使用bootstrapping)
OK,本篇我们重点介绍的是BFV。
BFV方案来源于文章 “Somewhat Practical Fully Homomorphic Encryption”,它是基于 RLWE (Ring-Learning With Errors)难题的全同态加密方案。
先来讲一下环上多项式环,这部分挺重要的,如果不了解的话,可能会对文章阅读造成困难。这里需要比较深厚的离散数学基础。
更多理论基础可以详见这篇博客:
https://www.zhihu.com/column/c_1320055686139813888
代码分析
占位符