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

Microsoft SEAL（Simple Encrypted Arithmetic Library）是微软开源的轻量级、高性能全同态加密（FHE）库，专为整数/浮点数的密文运算设计，支持BFV、CKKS、BGV等主流FHE方案，广泛应用于隐私计算、联邦学习、数据加密等场景，源码：https://github.com/microsoft/SEAL。
1 数学基础

1.1 多项式环

SEAL使用的基础环是：

BFV的所有运算都在这个多项式环中进行，符号含义如下：

Zq：系数域，即多项式的所有系数都取自“模q的整数集合”，q称为系数模数（一个大素数或多个素数的乘积），决定密文的噪声容忍度和运算深度。

xN+1：多项式模，要求N是2的整数幂（如4096、8192），满足xN≡-1 (mod xN+1)，这意味着所有多项式的次数都不会超过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远小于系数模数q（t