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

CKKS（Cheon–Kim–Kim–Song）是2017年论文《Homomorphic Encryption for Arithmetic of Approximate Numbers》中提出的近似计算同态加密算法，论文的作者是Cheon等四位韩国研究者，如今该方案已经是面向浮点/复数近似同态计算的主流方案，广泛应用于密文机器学习、数值计算场景。不同于以往同态加密算法中所追求的解密结果和明文完全一致，CKKS算法的目标是做近似计算。这并不偏离需求，因为现实生活中大部分运算，面对的是实数（复数），而实数（复数）的运算，往往只需要保留一部分有效数字即可。此外，允许误差，放宽准确性的限制，使得CKKS对比于其他基于LWE/RLWE难题的同态方案，细节有了较大的简化，计算效率也有了很大提升。

1 核心原理

1.1 编码与嵌入原理

CKKS的核心创新是规范嵌入（Canonical Embedding），将环R上的多项式与复数空间CN/2双向映射：

（1）多项式f(x)∈R可通过分圆多项式的根映射为N/2维复数向量

（2）复数向量可反向映射为环上多项式，实现向量数据与多项式的无损转换

（3）结合缩放因子Δ=2k，将浮点数放大为整数，适配有限域运算

槽位数量=N/2，例如N=8192时，单密文可打包4096个浮点数并行运算。R是分圆多项式环：

环中的元素是系数是整数（严格来说是实数）的N次多项式。

CN/2是N/2维复数向量构成的环，它里面的元素是N/2维复数向量。规范嵌入是环同构（保持环加法与乘法的双向一一映射）：

设ζj = ei(2j+1)π/N，j = 0,1,...,N-1是xN + 1 = 0，即xN = -1 = eiπ的N个元根，则σ从左到右表示为：

σ有以下关键性质：
（1）加法映射为向量加法，即σ(f+g) = σ(f) + σ(g)
（2）乘法映射为向量逐元素乘法（Hadamard积）σ(f•g) = σ(f) • σ(g)
（3）双射（可逆）
可以从向量还原多项式（逆映射），接下来以N=8为例，从正反两个方面进行分析。
1 正向映射（canomical embedding R->C4）

当N=8时，环表示为：

环中的元素为多项式：f(x)=a0+a1x+a2x2+...+a7x7，x8+1=0的元根为：x=ei(2k+1)π/8，k=0,1,...,7，由元根的共轭可知：

则正向映射将多项式映射为复数向量，表示为：

以上只取前4个根，因为由于共轭有：

以多项式f(x) = 1 + 2x + 3x2为例，计算第一个槽：

同理可得4维向量的其他分量，从而完成多项式向复向量的映射，σ(f) = (z0,z1,z2,z3)∈C4。这一步本质上就是FFT的前半部分，
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

感谢，下载保存了