集合交集问题的安全计算：解读

2022 年 5 月 24 日
笔记
MPC

本文记录阅读该paper的笔记。

摘要

要点：
（1）集合的势：交/并集个数
（2）该文主要讨论三点：

集合的势与阈值的大小关系
集合的交/并集与元素的包含关系
集合的交/并集的判定

（3）模拟范例：是安全性证明的方法

引言

首先给出三个场景，依次分析一下：
（1）全部领导集合Q，全部员工集合P，员工满意领导的集合X，现想确定X中的数量大于阈值t
（2）用户信用判断（多个指标），每个机构P（一个指标）都有一个信用合格的用户名单X，现想确认一个用户是否在所有名单中X，即求一个元素是否在交集中。
（3）所有员工名单A，每个机构P（一个用户的信用指标）都有一个信用合格的用户名单X，现想判断A是否都在X的交集中，即一个集合是否在交集中。
下面也是主要分为这三块介绍。

预备知识

安全性定义

模拟范例文中说参考：【Brief Report: Examining Driving Behavior in Young Adults with High Functioning Autism Spectrum Disorders:A Pilot Study Using a Driving Simulation Paradigm】，看着名字不像是安全性分析，倒是一个具体的场景实现。

这里是给出半诚实参与的安全性证明，模拟器的输入和输出与真实情况下是不可取分的，即在半诚实安全。

门限密码

门限密码体制是MPC中对抗合谋攻击的一个重要工具。

在门限密码体制中, n 个参与者联合生成公钥, 解密密钥由 n 个参与者联合持有. 公钥可以直接加密消息, 但解密需要 n 个参与者中一定数量人员参与才能正确解密，即如果至少需要 t 个人参与才能解密, 少于 t 个人时无法获取明文的任何信息,这样的密码体制称为 (t, n) 门限密码体制。

本文需要的是 (n, n) 门限密码体制。

给出ELGamal的一个变体，是门限密码：
（1）密钥生成和ElGamal类似，n个私钥$k_i$（每人一个），一个公钥$h$
（2）加密是和ElGamal一样的，密文是两部分
（3）解密，是需要所有人的私钥才能解密成功
（4）具有“加法同态性”：$E(m_1)E(m_2)=E(m_1+m_2)$，其实是密文相乘解密后相当于明文相加，当然这也算是具有同态性。
（5）这里的小素数$\rho $就是门限，有没有想到离散对数问题。

密文重随机化

主要是因为：在下面加密选择和保密替换中，用户可能会通过观察$M$，判读出上一个用户改变了什么，（透露出一些数据信息），所以需要对$M$中的密文重随机数化，即重新加密，密文改变，明文不变。

集合的势与阈值的大小关系

交集

换成标准形式是：

可以看到，目的就是判断交集的大小与阈值的大小关系。

原理

这里的阈值$t\in Q$，$t$和$Q$按说是没啥关系吧？$t$就是一个数。
还有这里的$Q$有$l$个元素，每个集合$X$也有$l$个元素，这个怎么搞？

按自己的意思举个例子理解一下：

Q=(1,2,3,4,5)
P1：X1=(1,2,3)
P2：X2=(2,3,4)
P3：X3=(3,4,5)
Alice：t=2
对于P1：M1=（1，1，1，0，0）
对于P2：M2=（0，1，1，0，0）
对于P3：M3=（0，0，1，0，0）
L=0+0+1+0+0=1
L-t<0，即输出为0

上面没有加入加密，没有安全性可言，下面加入加密：

方案

注意：
（1）Alice将$-t$加密$E(-t)$,发送给$P_n$
（2）$P_n$将$E(M_n)$中的元素逐个相乘得到$E(L)$，然后再将$E(L)$和$E(-t)$相乘得到$E(F)$，最后将$E(F)$随机化，得到$(u,v)$，并公布$u$，
（3）Alice和n个用户都是参与者，所以有$n+1$个私钥$k_i$
（4）Alice和(n-1)和用户各自计算$t_i=u^{k_i}$
（5）$P_n$解密，这里需要联合解密（n+1个参与者）
（6）注意这里$E(-t)*E(L)=E(L-t)$（别忘了加法同态性！）