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

1 核心原理1.1 编码与嵌入原理CKKS的核心创新是规范嵌入Canonical Embedding将环R上的多项式与复数空间CN/2双向映射1多项式f(x)∈R可通过分圆多项式的根映射为N/2维复数向量2复数向量可反向映射为环上多项式实现向量数据与多项式的无损转换3结合缩放因子Δ2k将浮点数放大为整数适配有限域运算槽位数量N/2例如N8192时单密文可打包4096个浮点数并行运算。R是分圆多项式环环中的元素是系数是整数严格来说是实数的N次多项式。CN/2是N/2维复数向量构成的环它里面的元素是N/2维复数向量。规范嵌入是环同构保持环加法与乘法的双向一一映射设ζj ei(2j1)π/Nj 0,1,...,N-1是xN 1 0即xN -1 eiπ的N个元根则σ从左到右表示为σ有以下关键性质1加法映射为向量加法即σ(fg) σ(f) σ(g)2乘法映射为向量逐元素乘法Hadamard积σ(f•g) σ(f) • σ(g)3双射可逆可以从向量还原多项式逆映射接下来以N8为例从正反两个方面进行分析。1 正向映射canomical embedding R-C4当N8时环表示为环中的元素为多项式f(x)a0a1xa2x2...a7x7x810的元根为xei(2k1)π/8k0,1,...,7由元根的共轭可知则正向映射将多项式映射为复数向量表示为以上只取前4个根因为由于共轭有以多项式f(x) 1 2x 3x2为例计算第一个槽同理可得4维向量的其他分量从而完成多项式向复向量的映射σ(f) (z0,z1,z2,z3)∈C4。这一步本质上就是FFT的前半部分()有8个实自由度而复向量看起来只有4个自由度但是因为i是复数它本身有2个实自由度所以总体上来说复向量有4x28个实自由度。2 逆向映射C4-R逆向映射将复数向量映射为多项式由(z0,z1,z2,z3)∈C4恢复一个多项式构造长度为8的“频域向量”唯一多项式f(x)满足f(ζk) zkk 0,1,2,...,7利用Lagrange插值工程上对应inverse FFT即可得到其中所有ai∈R。这里的双向映射正是CKKS Encode/Decode在做的事1.2 缩放因子Scale及近似计算CKKS不追求绝对精确解密结果与原始明文存在极小精度误差误差可控且远低于机器学习/数值分析的容忍阈值这是效率与实用性的平衡设计为了实现该目标引入了缩放因子缩放因子在“把实/复数嵌入整数多项式环”时由“缩放舍入”不可避免引入了精度误差仍以N8为例说明相应流程原本映射是一对零误差的严格双射但是CKKS要做一件“非法的事”逆向映射由实/复数转换成整系数多项式就是操作本身就不可能精确完成原因很简单左边是连续域右边是离散格CKKS的解决方案是进行“缩放舍入误差源头”首先引入一个scale Δ在映射前对复向量进行缩放这一步只是放大并没有引入误差接下来进行逆embeddingIFFT得到实系数多项式理论上这一步仍然是精确的但是在进行随后一步舍入到整系数时会产生误差令其中e(x)的每个系数都满足|ei|≤1/2当映射回slot空间时会对m(x)再做canonical embedding而所以其中εk e(ζk)最后会除于scale Δ这就是CKKS的“近似”对比BFV中的“舍入”他们的含义完全不同BFV的舍入是在模t意义下向整数添加噪声再把“整数小噪声”映射回同一个整数只要噪声受控该过程就是之前操作的精确逆操作。CKKS的舍入是把“连续实数”映射到最近的整数再把整数映射回实数该过程并不是之前操作的精确逆操作所以产生“近似”。一句话BFV里round用于“纠错”CKKS里round用于“近似”。在SEAL中常用2^40精度与噪声达到平衡。1.3 噪声管理在CKKS中噪声管理主要依靠Rescaling重缩放机制它配合RNS链实现了对噪声的“阶梯式”精准控制。1 CKKS噪声的组成部分CKKS的噪声e并不是单一来源它是由三部分叠加而成的初始噪声erlwe加密时引入的离散高斯噪声用于保障安全性。编码误差eenc将浮点数缩放并舍入到整数多项式时参数的损失。计算误差ecomp同态乘法和重线性化引入的噪声。在CKKS中我们不区分“噪声”和“误差”。缩放因子Δ决定了明文的精度而噪声只要不侵蚀到Δ定义的有效位计算就是可靠的。2 核心机制Rescaling重缩放当我们做一次同态乘法如果不处理连续乘法会导致数值迅速爆炸超出模数q的范围。此时将密文除于一个RNS素数ql通常设ql≈Δ并进行舍入结果1缩放因子回归Δ2/ql ≈ Δ有效位回到了正确的位置。2噪声同步缩减原本的噪声e也被除于了ql新噪声为e/ql舍入误差可见Rescaling不仅把膨胀的数值拉回来同时顺手把增长的噪声也按比例缩小了。3 RNS链与层Levels的噪声控制在实际实现中模数Q是L个小模数之积Qq0·q1·...·qL-1每一层计算都对应链中的一个素数以L4为例给出流程以上每一层Rescaling都会吃掉总模数Q的约p比特假设Δ2p当RNS链只剩下最后一个素数q0时无法再进行Rescaling此时再做乘法噪声将无法被缩小会迅速覆盖掉有效明文位。假设Q为600bitΔ为40bitQ能支撑约600/4015层乘法算到第15层时模数只剩40bit左右此时噪声和明文混在一起无法再分。与BFV的区别BFV的噪声管理是为了保住“整数的绝对准确”CKKS的噪声管理是为了保住“浮点数的有效精度”。2 CKKS标准流程划分以SEAL库为例完整流程分为5个阶段。2.1 系统初始化与参数生成输入参数多项式模次数N2的整数幂模数链系数{q1,q2,...,qL}递减序列决定运算深度缩放因子Δ2k控制计算精度高斯噪声分布χRLWE基础噪声输出参数合法的SEAL上下文2.2 密钥生成基于RLWE问题生成密钥组私钥绝对保密公钥/辅助密钥可公开分发。1私钥sk随机采样小范数多项式sk∈R系数仅为-1/0/12公钥pk(b,a)a环上随机多项式bb-(a·sk epk)其中epk是高斯噪声多项式3重线性化密钥rlk用于密文乘法后的维度压缩由私钥加密派生服务器执行重线性化时使用。4旋转密钥rot_k可选用于密文槽位旋转实现向量数据重排、求和等高阶运算。2.3 编码与加密步骤1 明文编码浮点数/复数-多项式该步会将实数/复数向量z∈CN/2转换为明文多项式。1构造对称向量Symmetry Construction在进行变换前首先构造一个长度为N的向量Z向量的后部部分是前半部分的共轭这种对称性保证了下一步IFFT出来的多项式系数全部是实浮点数。2正则嵌入逆变换IFFT将长度为N的对称向量Z进行逆变换得到一个多项式p(x)其系数ai理论上应该是实数由于浮点数计算精度问题可能会有极小的虚部通常直接舍弃。3缩放与舍入Scaling Rounding对实浮点数系数进行操作由此得到了系数为实整数的多项式pt。以N4为例假设z(3,4)则首先对z进行扩展Z(3,4,4,3)因为3和4可以看作是虚部为零的复数所以Z向量后半部分的共轭和前半部分完全相同。接下来目标是将Z映射为多项式p(x)a0a1xa2x2a3x3即需要找到多项式的实系数a0a1a2a3。在CKKS中使用x410的单位根它们是ζ0 eiπ/4ζ1 ei3π/4ζ2 ei5π/4ζ3 ei7π/4ζ2和ζ3是ζ1和ζ0的共轭则对于多项式p(x)满足p(ζ0) y0 3p(ζ1) y1 4p(ζ2) y2 4p(ζ3) y3 3可以利用IFFT逆变换系数公式进行求解依次计算各个系数计算a0计算a1由可知计算a2由于ζ0-2 -iζ1-2 iζ2-2 -iζ3-2 i可知计算a3由可知以上多项式系数的计算过程可以看到系数中的虚部会因为共轭对称完全抵消只剩实部得到多项式是p(x)3.5-0.3535x0.3535x3后续将在此多项式的基础上对齐系数进行放大及舍入完成编码流程。步骤2 明文加密明文-密文编码后的明文多项式pt被转换为一个包含两个多项式的密文对(c0,c1)图中ab是公钥对儿的两部分u是小范数随机多项式e0e1是高斯噪声多项式Q是密文大模数。2.4 密文同态运算支持加法、标量乘、密文乘、旋转、求和等运算是CKKS的核心能力。1 密文加法同态加输入两个同维度密文ct(ct0,ct1)ct(ct0,ct1)输出ctadd(ct0ct0,ct1ct1)特性无维度膨胀无需重线性化噪声线性叠加运算后缩放因子保持不变。2 密文乘法同态乘原始乘法两个二元组密文相乘输出三元组密文ctmult(c0,c1,c2)其中c0ct0•ct0c1ct0•ct1ct1•ct0c2ct1•ct1。重线性化使用重线性化密钥rlk将三元组压缩回标准二元组恢复密文结构重缩放乘法后缩放因子变成Δ2为了防止数值爆炸会将密文除于Δ并舍入模切换降低模数同步缩放数据压缩噪声保证后续运算可行性特性噪声指数级增长必须配合重线性化模切换使用。3 高阶运算标量乘法密文与公开常数相乘无需密钥槽位旋转移动单个槽位数据配合旋转密钥使用槽位求和批量数据聚合适用于统计计算2.5 解密与解码1 密文解密输入密文ct(ct0,ct1)、私钥sk输出解码前明文多项式解密公式最后部分可以看作是总噪声则有ptdec pt etotal。2 明文解码1去除模数映射将多项式转换为复数向量2除于缩放因子Δ还原为原始尺度的浮点数3舍弃虚部实数场景得到最终计算结果