全同态加密+对称密码+隐私计算学习记录
全同态加密
-
全同态加密目前都指的是环同态
给定两个环结构A和B，各自定义了两种运算$(+_A,\times_A)$和$(+_B,\times_B)$，
如果存在一个映射f: A->B，满足
$f(a_0 +_A a_1)=f(a_0) +_B f(a_1)$
$f(a_0 \times_A a_1)=f(a_0) \times_B f(a_1)$
则称f是A到B的同态映射。
对于密码方案来说，可以理解为
$a_0 +_A a_1=Dec(Enc(a_0) +_B Enc(a_1))$
-
如何构造全同态？
有两个难点，一是如何找到两种环结构，二是如何如何针对两种环结构设计出同态映射。
2009年，MIT的博士生Gentry基于格构造出了首个全同态方案，这个方案的实际性能很差，但是它其中的思想却一直贯彻未来的全同态方案设计当中。直接点说，Gentry基于格的方案是含有噪声的，因此必须要保证最终解密时噪声控制在某个界内，因为同态本质是针对运算做出限制，所以只需要保证每次运算后都能控制噪声在界内即可。Gentry提出了一种叫做“自举”的方法，对运算后的密文进行“同态地解密”，事实上，我觉得这个同态解密的说法不合适。下面想讲一下我个人的理解：
-
理解“自举”
一般来说，全同态加密会有一对密钥：pk、sk，也就是公钥和私钥。
$c=Enc_{pk}(m),m=Dec_{sk}(c)$
现在如果再构造一对密钥：$\overline{bsk},\overline{pk}$，满足$\overline{bsk}=\overline{Enc}_{\overline{pk}}(sk)$
自举最关键的步骤是需要把$c=Enc_{pk}(m),m=Dec_{sk}(c)$变为$\overline{c}=\overline{Enc}_{\overline{pk}}(m)$，这一步也被称作重加密，这个称呼是比较贴切的，相当于换个公钥重新加密，解密后的密文可以通过参数的调整保证噪声以“极大概率”落在界内。之后还需要进行一步密钥切换，就是从$\overline{c}=Enc_{\overline{pk}}(m)$变成$\hat{c}=Enc_{pk}(m)$，此时也可以通过调整参数使得噪声以“极大概率”落在界内。这里需要注意一点，自举都是概率性的，无法保证100%成功。
$\overline{Enc}_{\overline{pk}}(m)=\overline{Enc}_{\overline{pk}}(Dec_{sk}(c))=Dec_{\overline{bsk}}(\overline{Enc}_{\overline{pk}}(c))$
通过这个公式，可以看出同态解密这个说法有点不合适，准确的理解应该是先对自举前的密文进行加密再同态地解密。
$$ c=Enc_{pk}(m),m=Dec_{sk}(c)\\ \overline{bsk}=\overline{Enc}_{\overline{pk}}(sk)\\ \overline{Enc}_{\overline{pk}}(m)=\overline{Enc}_{\overline{pk}}(Dec_{sk}(c))=Dec_{\overline{bsk}}(\overline{Enc}_{\overline{pk}}(c)) $$当然，也有对称形式的：
$$ c=Enc_{sk}(m),m=Dec_{sk}(c)\\ \overline{bsk}=Enc_{\overline{sk}}(sk)\\ Enc_{\overline{sk}}(m)=Enc_{\overline{sk}}(Dec_{sk}(c))=Dec_{\overline{bsk}}(Enc_{\overline{sk}}(c)) $$-
注意到，在RLWE中似乎都使用非对称形式的全同态加密，在LWE中更倾向于使用对称形式的，这里应该有一些原因，需要我仔细分析一下。
-
自举难点
$Dec_{\overline{bsk}}(\overline{Enc}_{\overline{pk}}(c))$，这里很显然有一个问题：$c$本身就是密文，如果对密文进行加密呢？这需要对$\overline{Enc}$进行特别设计，既要和原来的$Enc$能够转换又要满足可以对密文进行同态加密。这是一个非常值得讨论的问题，可以通过这个切入点来看BGV/BFV/CKKS/TFHE等全同态方案的自举是如何设计的？
-
自举的设计
全同态编码
seal库里面直接系数编码
|
|
批处理编码CRT
混合同态加密
- 比较不同同态算法下一些国产对称密码的使用效果
- 比较不同同态算法下一些统计或机器学习的算法实现效果