0


CKKS加密简介

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

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

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

首先,有一个多项式f(x)=x^d+1,其中d是2的整数次幂,也就是一个分圆多项式。构造环R=\mathbb{Z}[x]/f(x)。CKKS的明文空间\mathbb{C}^{\frac{d}{2}}(维度为d/2的复数向量)与环R是同构的。编码就是将明文从\mathbb{C}^{\frac{d}{2}}映射到环R上,使得加密的明文是一个多项式m。其解码是编码的逆过程。其具体过程是通过f(x)的单位本原根来实现的。把f(x)的本原根代入,每一个本原根对应向量中的一个值。实际上是两个本原根对应一个复数。然后,多项式的系数,得到一个实多项式。

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

在具体介绍CKKS的加解密时,首先介绍一下CKKS中提出的重缩放技术。CKKS是一个层次的加密,其乘法的深度在初始化参数中就已经确定。每一次重缩放操作,会在减少噪声的同时,降低密文的层次。将CKKS的深度记为L,那么我们需要一个递增的密文模序列\{q_0,q_1,q_2,...,q_L\},相邻密文模的商应该接近\Delta。每一次的重缩放操作,将密文从密文模q_l降到q_{l-1}。我描述为密文从q_l降到了q_{l-1}。具体做法是,假设密文为\mathbf{c},则重缩放后的密文\mathbf{c^\prime}=\lfloor \frac{q_{l-1}}{q_l}\rceil \mathbf{c} \mod q_{l-1}

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

假设噪声分布为\chi是一个与安全级别\lambda有关的在环R上的离散高斯分布,\chi ^\prime是环R上的均匀随机分布。

密钥生成:在噪声\chi中采样得到s,则私钥sk=(1,s)。然后,在\chi ^\prime中采样得到aa^\prime,在\chi中采样得到ee^\prime,计算公钥pk=(b=-as+e,a),辅助密钥evk=-a^\prime s+e^\prime +Ps^2 \mod P \cdot q_L,其中P是一个大数。

加密****:m是编码过的明文多项式,在\chi ^\prime中采样得到v,在\chi中采样得到e_0e_1。则密文\mathbf{c}=v \cdot pk +(m+e_0,e_1) \mod q_L。注意,加密得到的新鲜密文都是q_L层的。

解密:\mathbf{c}=(c_0,c_1)q_l层的密文,则m+e=\mathbf{c} \cdot sk=c_0+c_1s \mod q_l,e是解密噪声。

重线性化:两个q_l层的密文(b_0,a_0)(b_1,a_1)相乘后,得到(d_0,d_1,d_2)=(b_0b_1,b_0a_1+b_1a_0,b_1a_1) \mod q_l\mathbf{c^\prime}=(d_0,d_1)+\lfloor P^{-1} \cdot d_2 \cdot evk \rceil \mod q_l,将三维的密文,变为两维,且私钥不变。

标签: 安全 同态加密

本文转载自: https://blog.csdn.net/watqw/article/details/123285986
版权归原作者 咸鱼菲菲 所有, 如有侵权,请联系我们删除。

“CKKS加密简介”的评论:

还没有评论