[数据结构与算法]CKKS加密简介

CKKS是目前比较流行的同态加密方案，出自于论文《Homomorphic encryption for arithmetic of approximate numbers》，名称是其作者的首字母简称。

CKKS相较于BGV和BFV，最大的优势是能够处理浮点数，甚至是复数。CKKS的明文域是复数向量。

其实，CKKS是基于BGV或者BFV构造的，其亮点，是编码。但是其编码需要的数学知识很复杂，在这里只是大概介绍一下。

首先，有一个多项式，其中d是2的整数次幂，也就是一个分圆多项式。构造环。CKKS的明文空间（维度为d/2的复数向量）与环是同构的。编码就是将明文从映射到环上，使得加密的明文是一个多项式。其解码是编码的逆过程。其具体过程是通过的单位本原根来实现的。把的本原根代入，每一个本原根对应向量中的一个值。实际上是两个本原根对应一个复数。然后，多项式的系数，得到一个实多项式。

但是，一个实多项式，并不能够直接加解密。所以呢，需要乘以一个大整数，然后借取整数部分，使之变为整数系数多项式。这样完全就可以使用BGV或者BFV来加密。但是，CKKS这里采用的并不是像BGV或者BFV采用的是噪声在一定范围内，是无误差解密的。CKKS采用的是有小差错的解密。也就是私钥和密文点乘以后，得到的结果是，是一个小的噪声，也就是解密误差。但是，在解码的时候除以后，就可以将误差控制得非常小了。

在具体介绍CKKS的加解密时，首先介绍一下CKKS中提出的重缩放技术。CKKS是一个层次的加密，其乘法的深度在初始化参数中就已经确定。每一次重缩放操作，会在减少噪声的同时，降低密文的层次。将CKKS的深度记为，那么我们需要一个递增的密文模序列，相邻密文模的商应该接近。每一次的重缩放操作，将密文从密文模降到。我描述为密文从降到了。具体做法是，假设密文为，则重缩放后的密文

接下来描述CKKS的密钥生成和加解密。

假设噪声分布为是一个与安全级别有关的在环上的离散高斯分布，是环上的均匀随机分布。

密钥生成：在噪声中采样得到，则私钥。然后，在中采样得到和，在中采样得到和，计算公钥，辅助密钥，其中是一个大数。

加密：m是编码过的明文多项式，在中采样得到，在中采样得到和。则密文。注意，加密得到的新鲜密文都是层的。

解密：是层的密文，则，e是解密噪声。

重线性化：两个层的密文与相乘后，得到，，将三维的密文，变为两维，且私钥不变。