Abstract

隐私集合求交（Private Set-Intersection，PSI）是目前的安全多方计算应用场景的主要解决方案之一，本文提出了一种新的PSI协议：Laconic，仅包含两轮交互，且第一条消息与集合的大小无关

Laconic适用于算力和存储受限的客户端与算力与存储能力强大服务器进行交互的场景

本文有两个主要贡献：1.提出了基于配对的简洁PSI协议，2.对协议进行优化，并与之前的协议进行比较

1 Introduction

PSI的主要任务如下：对于交互的双方$A,B$，分别持有集合$X,Y$，他们希望在不透露各自的集合的前提下，计算两个集合的交集$X\cap Y$​

PSI常用于检测僵尸网络、发现私人联系人等场景，此类场景中通常有一个算力和存储能力强大的服务器，其需要与多个不同的算力和存储较弱的客户端提供服务

问题在于目前的PSI方案需要服务端和客户端之间进行复杂的计算，这对算力较弱的客户端很不友好，因为不可能要求其下载并保存巨量的数据，并基于这些数据完成复杂的计算

总结一下，上述问题可以归结为：参与方的开销到底可以减小至多小？

2017年，$[CDG+17]$等人提出了Laconic的概念，后续也有多种优化与不同的变体，这一概念旨在解决上述场景中复杂度过大的问题

Laconic是一个在具有大输入的接收方$\mathcal R$和具有小输入的发送方$\mathcal S$之间的交互式协议，协议通常需要满足下列几个性质

  1. 协议应当仅包含两条消息（也即Laconic）
  2. 发送方的总通信开销与接收方的输入大小无关
  3. 接收方的第一条消息应该可以被多个不同的发送方$\mathcal S_i$复用

之前的一些方案$[ADT11,ABD+21]$基于RSA累加器，可以实现上述第二个性质，但是仍存在效率等其他方面的问题

本文的工作主要如下：提出了一个新的两方Laconic PSI，旨在从理论和时间角度最大限度的减少发送方的开销，协议基于双线性配对构造累加器，提供基于半诚实安全

本文的方案非常的精简而优雅，接收方的消息为单个群元素，发送方的消息大小与其输入集合呈线性关系，发送方的计算开销与接收方的输入无关，下表给出了本文的方案与$[ADT11,ABD+21]$两个方案的一些比较

$[ADT11]$原始协议包含三轮交互，但是如果Setup是可信的，则只需要两轮交互，但是该方案中要求发送方知道Setup中的陷门，因此该方案中无法将接收方的同一消息复用（不满足上述的性质3），不过该方案基于随机预言机模型，且Setup过程为私有的，因此该方案的通信开销是最优的

从表1中可以看出，本文方案的主要缺点为：CSRS的大小与接收方的集合大小呈线性关系，不过这一缺点提供了一个额外的安全保证：发送方可以知道接收方的输入集合的大小不会超过CRS的大小，基于RSA构造的方案没有这样的限制，此时恶意的接收方可以从集合中挑选出一部分来完成协议

2 Preliminaries

  • $a\larr A$：从集合$A$中随机选择元素$a$
  • $[n]$：表示正整数集合$\{1,\dots,n\}$
  • $\mathcal R$：接收方，也即协议中的服务端
  • $\mathcal S$：发送方，也即协议中的客户端
  • $X=\{x_1,\dots,x_m\}$：表示接收方集合，大小为$m$​，其中$x_i\in \Z_q$
  • $X_{-i}$：表示$X\backslash \{x_i\}$
  • $Y=\{y_1,\dots,y_n\}$：表示发送方集合，大小为$n$，其中$y_i\in \Z_q$
  • $Z=X\cap Y$：协议最终需要的计算的集合
  • $P(X,s)$：表示多项式$\prod_{x\in X}(x-s)$，多项式的阶为$|X|=m$，不难看出，有等式$P(X,s)=P(X_{-i},s)\cdot (x_i-s)$
  • $p(X,i)$：多项式$P(X,s)$的系数，满足$P(X,s)=\sum^m_{i=0}p(X,i)\cdot s^i$
  • $(\mathbb G_1,\mathbb G_2,\mathbb G_T,g_1,g_2,e)$：双线性配对，$g_1,g_2$分别为$\mathbb G_1,\mathbb G_2$的生成元，本文采用III型配对

本文的方案基于$(B_1,B_2)$-SBDDH假设，在该假设中，对于敌手选择的随机值$s\in \Z^*_q$，构造下列大小为$B_1+B_2+2$的元组

$$ (g_1,g_1^s,\dots,g_1^{s^{B_1}},g_2,g_2^s,\dots,g_2^{s^{B_2}})\in \mathbb G_1^{B_1+1}\times \mathbb G_2^{B_2+1} $$

敌手基于上述元组，输出一个元素$y\in \Z_q$，该假设表明，对于元素$T_0=e(g_1,g_2)^{1/(y+s)}$和$\mathbb G_T$中的随机元素$T_1$，任意概率多项式敌手区分$T_0,T_1$的优势可忽略，具体的安全游戏如下图所示

这个假设简单来说就是对于给定的CRS，敌手难以计算参数$(y,h)$，满足等式$h=g^{1/(y+s)}$

本文的方案令$B_1=1,B_2=B$，其中$B$表示接收方集合的大小

3 Our Laconic PSI Protocol

首先需要注意的是，本文的Laconic PSI协议在半诚实模型中满足安全性，本节先从I型配对简单介绍一下协议

协议开始时，首先由某个可信第三方选择随机性$s$，并计算参考串$CRS=\{g^{s^i}\}_{i\in [m]}$，之后接收方基于其输入集合$X$，构造一个累加器，并对该累加器进行随机化处理（目的是隐藏其输入集合）

具体而言，接收方计算$R=g^{r\cdot P(X,s)}$，并将该元素发给发送方，假设发送方的集合中包含元素$y$，然后发送方可以计算自己集合的累加器元素$U=g^{t(s-y)}$，并用随机性$t$进行随机化处理

这里接收方可以以同样的方式计算集合$X_{-k}$对应的累加器元素$R_{-k}=g^{r\cdot P(X_{-k},s)}$

之后发送方向接收方发送累加器元素$U$和一个目标元素$T=e(R,g)^t$，接收方通过适当的配对来检查元素$y$是否在集合内

这里有一点需要注意：发送方在两个元素$U,T$中使用了相同的随机性$t$，可能会影响协议的安全性，但是注意到元素$T$是基于接收方的元素$R$计算的，此时的安全性假设可以为SBDDH，而非DDH（原文的Thm 1给出了相关的证明）

图3正式描述了本文的协议，只不过把上面的I型配对换成了III型配对

这里看一下协议的流程，记安全参数为$\lambda$，假设Hash函数$H:\{0,1\}^*\rarr \{0,1\}^\lambda$满足抗碰撞性，双方采用III型椭圆曲线配对，协议分为两轮，记会话id为$sid$

首先看一下协议需要完成的工作：接收方$\mathcal R$拥有一个大小为$m$的集合$X=\{x_1,\dots,x_m\}$，发送方$\mathcal S$有一个小得多的集合$Y=\{y_1,\dots,y_n\}$，假设这些集合中的元素均可以编码为$\Z_q$中的元素，协议结束时，接收方需要知道这两个集合的交集$Z= X\cap Y$，且不会泄露发送方集合中的其他信息

在协议开始前，先由一个可信第三方执行Setup算法，该第三方选择一个随机数$s\in \Z_q^*$，并为协议双方计算$setup_R,setup_S$如下

$$ \begin{aligned} setup_R&=\{S_i\}_{i\in\{0,\dots, m\}}=\{g_2^{s^i}\}_{i\in\{0,\dots, m\}} \\ setup_S&=S'=g_1^s \end{aligned} $$

在协议的第一轮中，接收方选择$r\larr \Z_q$，并计算元素$R$如下

$$ \left\{\begin{aligned} R&=(\prod_{i=0}^mS_i^{p(X,i)})^r,&X\neq \empty\\ R&=S_0^r,&X=\empty \end{aligned}\right. $$

协议第一轮中仅包含接收方向发送方发送的消息$msg_1=(sid,R)$

协议第二轮中，发送方首先选择一个置换$\pi:[n]\rarr[n]$，之后对于所有的$j\in [n]$，选择随机数$t_j\larr \Z_q$，计算二元组$(T_j,U_j)$如下

$$ (T_j,U_j)=\Big ( H\big( e(g_1^{t_j},R) \big) , (S'\cdot g_1^{-y_{\pi(j)}})^{t_j} \Big ) $$

协议第二轮的消息由发送方发送至接收方，消息为$msg_2=(sid,T_1,U_1,\dots,T_j,U_j)$

接收方在接收到消息$msg_2$后，接收方先令目标集合$Z=\empty$，之后对于所有的$j\in [n],k\in [m]$，计算$R_{-k}$如下

$$ R_{-k}=\Big( \prod^{m-1}_{i=0} S_i^{p(X_{-k},i)} \Big)^r $$

之后接收方验证等式$H(e(U_j,R_{-k}))=T_j$，若等式成立，则令$Z\larr Z\cap x_k$，直至处理完所有的$x_i$

‍

这里给出一个定理

Thm 1：若$(1,B)$-SBDDH假设成立，且哈希函数$H$满足抗碰撞性，则上述协议在敌手为被动腐败的情况下是$\mathcal F_{PSI}$的安全实施

$\mathcal F_{PSI}$参见原文附录4，这里看一下证明

Proof：

首先看一下协议的完备性

这里可以看一下式1中计算元素$R$的方式，若$X\neq \empty$，则对应的$R,R_{-k}$如下

$$ R = (\prod_{i=0}^mS_i^{p(X,i)})^r=(g_2)^{r\cdot P(X,s)}\\ R_{-k} = (\prod_{i=0}^{m-1} S_i^{p(X_{-k},i)})^r=(g_2)^{r\cdot P(X_{-k},s)} $$

然后看一下$(T_j,U_j)$

$$ T_j=H[e(g_1^{t_j},R)]\\ U_j = (S'\cdot g_1^{-y_{\pi(j)}})^{t_j} $$

如果把$T_j$中的Hash函数去掉，我们可以得到下面这个

$$ e(g_1^{t_j},R)= e(g_1^{t_j},g_2^{r\cdot P(X,s)})= e(g_1,g_2)^{t_j\cdot r\cdot P(X,s)} $$

然后看一下验证等式$H(e(U_j,R_{-k}))=T_j$左侧，同样把Hash函数去掉，得到

$$ e(U_j,R_{-k})=e(g_1^{t_j[s-y_{\pi(j)}]},g_2^{r\cdot P(X_{-k},s)})=e(g_1,g_2)^{t_j\cdot r\cdot P(X_{-k},s)\cdot [s-y_{\pi(j)}]} $$

根据验证等式，当且仅当有$y_{\pi(j)}=x_k$时，有等式成立，因此完备性成立

之后看一下协议的安全性，这里定义一个模拟器$Sim$辅助分析

首先分析一下发送方为恶意的情况，其输入集合$Y=\empty$，此时选择随机性$r\in \Z_q$，输出消息$m_1=(sid,R),R=g_2^r$

此时如果接收方的集合$X=\empty$，则模拟没什么问题，如果集合$X$非空，则当多项式$P(X,s)\neq 0$时，真实协议执行中的消息与模拟消息同分布，但是根据SL引理，多项式$P(X,s)\neq 0$成立的概率为$|X|/q=m/q$，当素数$q$很大时此概率可忽略

然后分析一下接收方为恶意的情况，具体分为下列几个步骤

  1. 由诚实方执行Setup，得到$CRS=(Setup_S,Setup_R)=(g_1^s,\{g_2^{s^i}\}_{i\in [m]})$
  2. 构造集合$Z=\{z_1,\dots,z_\zeta\}$​
  3. 计算$R$
  4. 选择一个随机子集$\Gamma \sube [n]$，满足$|\Gamma| = |Z|=\zeta$​
  5. 记补集$\Delta = [n]\backslash \Gamma$
  6. 记集合$\Gamma = \{\gamma_1,\dots,\gamma_\zeta\}$，对于任意的$j\in [\zeta]$，按照协议第二轮步骤2中构造$(T_{\gamma_j},U_{\gamma_j})$（随机性$t_j\in \Z_q$）
  7. 记$\Delta = \{\delta_1,\dots,\delta_\omega\}$，其中$\omega = m-\zeta$，对于任意的$j\in [\omega]$，按照协议第二轮步骤2中构造$(T_{\delta_j},U_{\delta_j})$（随机性$t_j,u_j\in Z_q$）
  8. 最终消息$m_2=(sid,T_1,U_1,\dots,T_n,U_n)$

看不懂， 留个坑

‍

4 Active Security and Extensions

本节主要介绍一下本文协议的一些安全性，以及协议的一些扩展和变体

真看不懂，后面让大佬给讲讲，留个坑

‍

References

$[1]$ Diego F. Aranha, Chuanwei Lin, Claudio Orlandi, Mark Simkin:Laconic Private Set-Intersection From Pairings. CCS 2022: 111-124

‍