同态加密：一个基于多方计算的CKKS方案

这篇文章主要介绍LattiGo团队搞出来的一个多方同态加密的工作。个人觉得比较优雅，而且有库支持，方便把玩，所以记一下。
在攒毕业论文的时候整了这么个看上去很烂，但是（个人觉得）有一点意思的烂活，没心思写那么多的公式，各位dalao凑合看，欢迎轻喷。

简介和亮点

实现了CKKS方案的一个多方计算版本（对BFV也适用）。这个多方版本的方案将私钥拆分成了$n$份分给$n$个计算方，一方一个。

对应的安全性：只要这$n$方别都是内鬼（比如所有方都沆瀣一气，沟通私钥），这个同态加密方案就具有语义安全性。

可以基于上述私钥拆分的想法设计一些有趣的多方解密/自举方案。

预备知识：CKKS同态加密方案的简介

引个流，看这儿。

LattiGo的多方CKKS方案

首先定义 $n$ 个计算方：$\mathcal{P}=P_1,...,P_N$。

私钥生成

参与计算的$n$方都随机生成一个私钥碎片$s{k}_i,\text{for}i=1,...,n$。最后$sk=\sum s{k}_i$就是完整的私钥多项式。这意味着每一方都持有一个私钥的碎片。

在具体操作中，可以让客户端先线下生成$n$个私钥碎片再分发给$n$个计算方，或者每个计算方先生成私钥碎片再发送给客户端。

在方案运行过程中，各个计算方持有一个私钥碎片和全部的公钥。

其他钥生成（不费脑子版本）

我们先假设客户端持有私钥。那么客户端其实已经可以根据私钥计算出一系列的公钥，比如加密公钥、重线性化钥、旋转钥blablabla，然后公布给$n$个计算方使用。

至于$n$个计算方如何派生出这一系列公钥，可以在看完下面多方解密和多方自举部分后留作文末习题（doge

多方解密和多方自举

我们先通过介绍多方解密和多方自举方案来阐明文章里的一些核心想法。

多方解密

对于密文多项式对$c=(c_0,c_1)$，解密方案就是求解$m=c_0+c_1\cdot sk$。

这里，多方参与完成解密就是计算$c_0+c_1\cdot \sum s{k}_i$。

解密方法如下：

各方计算$c_1\cdot s{k}_i+e_i$，其中$e_i$是噪声。然后计算

$$c_0+\sum (c_1\cdot s{k}_i+e_i)$$

就完成了解密（虽然带了点噪声）。

在这个方案中，RLWE问题的语义安全性保证了$s{k}_i$很难被爆破，于是只要至少有一个计算方不是内鬼（不是内鬼：指保护好自己的私钥碎片），那么私钥就不会被破解。

多方自举

在实现多方自举之前，我们首先让各个计算方生成一个公有的密文$d$。

首先各方生成随机密文$d_i$，然后各方共同参与求和，得到$d=\sum d_i$。$d$被对外公布。

在这个过程中，只要计算方不是全员内鬼，那么$d_i$和$d$就是语义安全的。

基于上述这些秘密$d_i$和$d$，我们可以设计多方自举方案。

对于密文多项式对$c=(c_0,c_1)$：

首先，各方计算$c_1\cdot s{k}_i+d_i+e_i$，其中$e_i$是噪声。

求和得到$m=c_0+\sum (c_1\cdot s{k}_i+d_i+e_i)$。

然后，计算$m-d$。

于是多方自举就完成了。

本质上是对解密后的明文加上一层mask，然后再把它抹掉就完事了。

其他钥生成（费脑子版本）

课后习题：

$n$个计算方如何派生出加密公钥、重线性化钥、旋转钥blablabla一系列公钥呢？