SEAL全同态加密BFV方案入门详解

1 数学基础1.1 多项式环SEAL使用的基础环是BFV的所有运算都在这个多项式环中进行符号含义如下Zq系数域即多项式的所有系数都取自“模q的整数集合”q称为系数模数一个大素数或多个素数的乘积决定密文的噪声容忍度和运算深度。xN1多项式模要求N是2的整数幂如4096、8192满足xN≡-1 (mod xN1)这意味着所有多项式的次数都不会超过N-1超过的项可通过xN -1降次。Rq元素形式任意元素是一个次数≤ N - 1的多项式形如1.2 明文空间明文待加密的整数会被编码为Rt中的多项式t满足t≡1 (mod 2N)这是批量加密的硬性要求明文在进行加密前要进行编码有两种编码方式单整数编码将单个整数m编码为常数多项式f(x)m即所有高次项系数为0。批量编码将N个小整数[m0,m1,...,mN-1]直接做为多项式的系数编码为1.3 RLWE问题BFV的安全性基于RLWE问题Ring Learning With Errors的计算困难性简单描述为给定多项式Rq选择一个秘密多项式s(x)∈Rq系数为0/1的短多项式以及大量的“噪声多项式对”ai(x), bi(x)其中ai(x)是随机生成的bi(x)-ai(x)s(x)ei(x) (mod q)是通过秘密多项式s(x)计算得到的“响应多项式”加入噪声ei(x)是为了让bi(x)看起来像一个完全随机的多项式从而隐藏s(x)的存在而在计算上无法从这些多项式对中恢复出秘密多项式s(x)。对于bi(x)其生成时每一部分的作用如下ai(x)从多项式环Rq中均匀随机生成的多项式相当于“公共输入”可以公开。s(x)秘密多项式系数仅为0或1是整个RLWE问题的核心必须严格保密。ei(x)小系数噪声多项式系数仅为-1、0、1是“隐藏秘密”的关键。bi(x)由ai(x)s(x)加上噪声得到的结果与ai(x)一起构成公开的“多项式对”。如果没有噪声ei(x)即ei(x)0那么bi(x)-ai(x)s(x) (mod q)此时攻击者可以通过多组(ai(x), bi(x))构建线性方程组直接解密出秘密多项式s(x)这就完全失去了安全性。而加入小噪声ei(x)后bi(x)不再是ai(x)s(x)的精确结果而是一个“近似值”这个近似值的误差被控制在很小的范围内由ei(x)的系数大小决定从计算角度目前没有任何算法包括量子算法能高效地从这些带噪声的近似结果中恢复出s(x)这正是RLWE问题的“计算困难性”来源也是BFV适合后量子秘密场景的原因。1.4 缩放因子在BFV同态加密方案中缩放因子Scaling Factor是连接明文空间Zt和密文空间Zq的核心系数本质是为了让明文多项式能“适配”系数模数q的范围同时保证解密时可以精确还原明文。BFV的明文模数t远小于系数模数qtq)比如t65537q260量级。明文多项式m(x)∈Rt的系数范围是[0, t-1]而密文多项式c(x)∈Rq的系数范围是[0, q-1]如果直接将明文m(x)放入密文公式由于t太小明文信息会被噪声和掩码完全淹没无法解密。因此需要一个缩放因子将明文系数放大到q的量级再参与密文计算。缩放因子贯穿加密和解密两个核心步骤是明文和密文的“桥梁”。1加密时明文放大在加密步骤中明文多项式m(x)不会直接代入密文公式而是先乘于缩放因子Δ再放入到公式作用将明文系数从[0, t-1]放大到[0, Δ*(t-1)]这个范围在q的量级内能避免明文被噪声覆盖。2解密时明文缩小解密的核心步骤是先计算聚合多项式D(ct)代入加密公式后可得此时需要反向缩放来还原明文概括来说缩放因子不会直接参与运算但会间接影响噪声的增长速度1) 加法运算密文加法是系数直接相加噪声线性叠加缩放因子不影响噪声增长2) 乘法运算密文乘法是多项式乘法噪声会平方增长而缩放因子Δ越大噪声的规模也会越大导致运算深度降低。因此在参数配置时需要在“明文范围t大小”和“运算深度q大小”之间做权衡若t增大→Δ减小→噪声容忍度降低→运算深度减小若t减小→Δ增大→噪声容忍度提升→运算深度增加。所以t与Δ成反比需根据业务需求平衡明文范围和运算深度。2 BFV核心流程2.1 参数配置参数配置决定方案的性能与安全性BFV核心参数有4个需严格满足数学约束参数约束需满足qt*(2N)d*Bd是目标运算深度B是噪声上限否则运算过程中噪声会“爆炸”导致解密失败。2.2 密钥生成基于RLWE问题生成私钥、公钥、重线性化密钥3中密钥核心是构造含噪声的多项式对。1私钥sk随机生成一个短多项式s(x)∈Rq系数仅为0或1如s(x) 1 x2 x5私钥就是s(x)。2公钥pk随机生成多项式a(x)∈Rq生成小希数噪声多项式e(x)∈Rq计算b(x) -a(x)s(x) e(x) (mod q)公钥是多项式对pk (b(x), a(x))可公开传播。这里的噪声e(x)让攻击者无法从公钥对中恢复私钥s(x)目的是解决“公钥本身的安全性”。3重线性化密钥rlk密文乘法会导致密文从“2项多项式”膨胀为“3项多项式”后续运算效率骤降。重线性化密钥用于将膨胀后的密文压缩回2项生成逻辑与公钥类似本质是一组扩展的RLWE多项式对。2.3 加密将明文多项式转为密文多项式BFV的密文是Rq中的2项多项式对ct (c0(x), c1(x))加密过程分两步1明文编码将整数明文m编码为明文多项式m(x)∈Rt2添加噪声与混淆随机生成两个小噪声多项式e0(x),e1(x)∈Rq随机生成一个“掩码多项式”u(x)∈Rq系数为0/1计算密文核心设计密文中包含明文信息m(x)但被噪声e0/e1和掩码u(x)混淆只有私钥能去除混淆和噪声。该步骤中的掩码多项式u(x)和噪声多项式e0(x),e1(x)是两套独立的安全机制它们解决的是完全不同的问题不能互相替代如下图u(x)通过随机缩放实现公钥和明文间的非固定线性关系噪声通过“近似”进一步打破它们之间精确的代数关系使得攻击者无法从近似值中还原精确明文。2.4 同态运算这步的核心是密文运算多项式环运算BFV支持秘密密文CtCt和密文明文CtPt的加减乘运算所有运算都在多项式环Rq中进行且无需密钥。运算后的密文仍然是合法的RLWE密文可继续参与后续运算——这就是「同态性」的体现。2.5 解密解密是加密的逆运算核心是去除噪声、还原明文多项式步骤如下1密文聚合用私钥s(x)计算聚合多项式代入加密公式可推导2噪声去除由于总噪声etotalq/(2t)可通过“舍入模运算”还原明文3明文解码将解密后的多项式m(x)转换回整数单整数取常数项批量加密取所有系数。解密成功条件总噪声etotalq/(2t)若运算次数过多导致噪声爆炸舍入后无法还原明文则会解密失败——这是BFV“层次性”的本质运算深度有限。2.6 python示例以下是一个完整的python示例程序View Code3 SEAL使用3.1 源码编译这里仅简单介绍下Windows下使用VS2022环境进行编译下载源码并安装cmake运行VS2022安装菜单下的“Developer Command Prompt for VS 2022”命令行执行命令进行配置cmake -S . -B build -G Visual Studio 17 2022 -A x64 -DCMAKE_INSTALL_PREFIX./out这里编译的是64位版本并将安装目录设置为当前目录下的out文件夹配置完成后再执行以下命令进行编译cmake --build build --config Release #编译Release版本 cmake --build build --config Debug #编译Debug版本编译完成后会生成seal-4.1.lib库文件然后执行以下命令进行安装cmake --install buildout下include中是头文件lib中是静态库文件3.2 示例程序使用VS2022创建空项目并添加demo.cpp文件内容如下View Code将之间产生的out文件夹下的include和lib拷贝到项目文件夹下配置项目的C/C编译包含头文件路径库文件路径以及输入库即可进行编译。编译完成后运行程序输出如下