读paper-"云环境下集合隐私计算"的笔记
基础#
哥德尔编码#
可以将非负整数序列（向量）与自然数建立起对应关系
具体来说，就是无穷序列(a1,x2,...,xm)
[a1,x2,...,xm]
原理#
根据算数基本定理，任何自然数可以唯一分解为多个素数的乘积，而构成哥德尔数的素数序列(p1,p2,...,pm)
同态加密算法#
该方案只用到了加法或者乘法同态性，下面分别介绍两种同态加密算法：
ElGamal#
具有乘法同态性，相比于RSA，能抵抗重放攻击（加密时加入了随机数）
1、加密结构：
2、乘法计算：
Paillier#
具有加法同态性和一次"乘法"同态性，主要用到的还是加法同态
1、加密结构
2、加法计算
保密计算求集合并集方案#
原理#
1-r编码#
假设有n
如果向量U′中的某个分量u′j≠1，说明这n个向量的第j个分量不全为1，即n个集合中至少有一个集合含有元素uj，根据集合U;中不为1的分量，可以得到并集X1∪X2∪...∪Xn，所以求集合的并集问题可以规约到计算向量U′
举例#
下面给出三个集合X1,X2,X3∈U，保密的计算集合的并集：
最后σ为集合的并集。
具体方案1#
在云计算下，数据是需要加密来保证安全的，这里选用ElGamal加密算法。假设有n台服务器P1,...,Pn，每台服务器中有一个集合Xi，假设第n台服务器Pn作为leader，生成加密的公私钥和参数，并将公钥和参数公开
（1）云服务器Pn将自己的公钥pk与参数params公开，并保留私钥sk
（2）每个云服务器Pi(i=1,...,n)计算：
-
将自己的秘密集合Xi编码为向量Ui
将Xi使用1-r编码方法编码为向量Ui=(ui,1,...,ui,m) -
将Pn的公钥pk与参数params加密Ui为E(Ui)
将向量Ui中的每个分量分别加密，即E(Ui)=(E(ui,1),...,E(ui,m)) -
将密文向量E(Ui)随机分成ki份并发送给n个云服务器中的ki个
为了将数据混淆来保证Ui的安全，每台服务器需要将E(ui,j),j=1,...,m分为ki(ki⩽n)份E(ui,j)1,...,E(ui,j)ki，（ki其他服务器是不知道的），需要满足:E(ui,j)1...E(ui,j)ki=E(ui,j)
Pi每次从每个密文分量E(ui,j)1,...,E(ui,j)ki中选取一个，共选取ki次，构成Ui的ki份密文E(Ui)1,...,E(Ui)ki，每份（向量）里面m个元素。
如果直接对E(ui,j),j=1,...,m进行分解因子，计算量大，所以这里使用模运算进行分解因子，具体如下：
选取ki个随机数ri,1,..,ri,ki∈Z∗p，需要满足ri,1....ri,ki=1modp，从ki个随机数中随机选择一个，如ri,1，和E(ui,j)相乘，即E(ui,j)1=E(ui,j).ri,1，然后将E(ui,j)2,...,E(ui,j)ki用ri,2,...,ri,ki表示，进而就能将E(Ui)"拆分"为ki份，且满足：E(ui,j)1...E(ui,j)ki=ri,1.E(ui,j).ri,2...ri,ki=E(ui,j)
最后将这个ki个密文向量E(Ui)1,...,E(Ui)ki发送给k个云服务器（可以包括自己）。 -
把收到的所有密文向量对应的分量相乘得到新的密文向量E(U′i)，并发送给Pn
每个云服务器Pi将密文发送后，也有可能收到其他云服务器发来的密文向量，Pi将收到的密文向量的每个相应分量分别相乘，构成新的密文向量E(U∗i)=(E(u′i,1),...,E(u∗i,m))，并发送给leader云服务器Pn，从而将发送的密文和自身密文混淆。
（3）云服务器Pn计算： -
所有收到的密文向量对应的分量相乘，得到E(U′)
由于每个服务器都是半诚实的，不会加入额外的信息，所以Pn构造的密文向量E(U′)是所有参与者密文向量各个分量的乘积，即:
-
用自己的私钥sk解密E(U′)得到U′
- 根据U′中不为1的分量得到(σ1,...,σh)
- 公布(σ1,...,σh)
举例#
现在要求四个云服务器中的秘密数据的并集，假设P4为leader服务器，k=3
（1）每台服务器Pi编码各自的集合数据Xi为Ui；然后再使用公钥pk加密，即E(U1),E(U2),E(U3),E(U4)；再将其拆分为k份，分别发送给其他两个服务器（自己留一份）
（2）在发送完后，Pi就有可能收到其他服务器发来的密文向量，然后将每份的密文向量对应的元素相乘得到E(U′i)，发送给P4
（3）P4得到：
（4）P4将E(U′)解密，根据U′中不为1的元素得到并集(σ1,...,σh)
上云优化#
上面Pi将向量Ui加密，仅相当于加密1和随机数r≠1，E(1)和E(r)是公开的，只需要保密1和r所在的位置即可，因此可将加密运算外包给半可信的云服务器S。
以上改造，半可信云服务器得到的信息只有E(1),r,E(U′i)，并不影响安全性。每个用户Pi仅需要计算少量的模乘，Pn只需要做m次解密，加密运算全部都由S完成，大大降低用户的计算量。
保密计算求集合并集优化方案#
上面的方案计算复杂性和集合U中元素的个数m线性相关，若m较大，加密、解密的次数和通信量将会较大，不便于计算。若想要m不太大，可以在上面的基础上，利用哥德尔编码将向量对应成一个自然数的方法设计了一种高效的编码方法，使得协议的计算复杂性不再于集合的大小m相关，降低了计算复杂性。
基本思想#
0-r编码+哥德尔编码#
（1）总集合U=(u1,...,um),(u1<....<um)对应集合P=(p1,...,pm),(p1,...,pm)是不等的互素数
（2）对于集合Xi∈U，将其按照0-r编码方式编码为向量Ui=(ui,1,...,ui,m)，具体是，若uj∈Xi，则ui,j=ri,j，其中ri,j∈[1,m]是一个随机数且ri,j≠0，否则ui,j=0，然后借助集合P利用哥德尔编码将Ui编码为一个自然数xi，即：
假设有n个集合X1,...,Xn∈U，将每个集合Xi按照上面的编码方式编码为一个自然数xi，将这n个自然数相乘得到x，即：
然后根据算数基本定理将x展开，得到集合U′=u′1,...,u′m。若u′j=u1,j+...+un,j≠0，则说明n个集合中至少有一个集合中有uj。所以就可以根据向量U′中不为0的分量，得到并集。
故计算并集的问题可以规约到计算x。
举例#
具体方案2#
U集合是公开的，或者是Pn已知的；Pn作为leader。
输入：P1,...,Pn各自的秘密集合X1,..,Xn∈U
输出：交集(σ1,...,σh)
（1）云服务器Pn保留私钥sk，公布公钥pk和系统参数params
（2）每个云服务器Pi计算如下：
-
根据上面改造的编码方法将自己的秘密集合Xi编码为自然数xi
-
用公钥pk加密xi为E(xi)
直接发送E(xi)是不安全的，因为Pn可以直接解密，所以需要混淆密文与云服务器的对应关系！ -
将E(xi)随机分为ki份并发送给ki个服务器
-
将收到的所有密文相乘得到新的密文E(x′i)，并发送给Pn
（3）云服务器Pn计算如下：
- 把所有收到的密文相乘，得到E(x)
- 用私钥sk解密E(x)得到x
- 将x用算术基本定理展开得到向量U′
- 根据U′中不为0的分量得到集合(σ1,...,σh)
云计算下的改造方案#
（1）用户自己编码，然后拆分混淆，发给服务器
（2）服务器计算（混淆后的明文），再加密，发送给leader服务器
（3）leader服务器计算（密文），解密，得到并集，并分发
云服务器没有任何一个云用户秘密向量的全部信息，因此得到不到云用户的信息
方案分析#
安全性证明
保密计算求集合交集方案#
上面介绍的是求集合的并集，现在求交集，变动不大！
协议#
举例#
（1）集合U=(101,102,103,104,105,106,107,108,109,110)对应集合P=(2,3,5,7,11,13,17,19,23,31)，假设要计算3个集合X1=(101,105,107),X2=(103,105,108),X3=(105,106,109)的交集，根据0-r编码将其编码为向量U1,U2,U3，即：
（2）将向量U1,U2,U3借助集合P利用哥德尔编码编码为自然数x1,x2,x3，即：
（3）将这三个自然数相乘得到：
（4）即得到向量U′=(2,5,5,11,0,9,13,13,13,24)，根据向量U′中为0的分量得到交集：
以上为了方便演示，省去了拆分的步骤。