Efficient Linear Multiparty PSI and Extensions to Circuit/Quorum PSI

本文主要是介绍Efficient Linear Multiparty PSI and Extensions to Circuit/Quorum PSI，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本片文章的内容和之前说的两篇文章密切相关，强烈建议回顾前两篇（必须回顾！！！）

2017--OPPRF

2019--batch OPPRF

一、基础知识：（简单说一下）

1.Cuchoo Hashing：

2.PSM

3.秘密共享

二、multiparty PSI

一、基础知识：（简单说一下）

1.Cuchoo Hashing：

生成三个(几个都行，以3个为例)hash函数，分别为 $h_1,h_2,h_3$ ，和一个table表，若 $h_1(x)$ 位置为空, 就将x放在 $h_1(x)$ 的位置上，若该位置已经存在元素y，则替换该元素，并将y放在 $h_2(y)$ 的位置上（位置为空），若该位置存在元素z，则替换元素z，并将z放在元素 $h_3(z)$ 对应的位置上（位置为空），若此位置存在元素m，在替换元素，并将m放在 $h_1(m)$ 位置上，一直循环直到找到相应位置。（对于死循环可以设置阈值，强行停止循环。）

2.PSM

可以理解为一个和Batch-OPPRF一样的一个协议，R方输入为 $q=q_1,...,q_\beta$ （查询到元素集合），S输入为数据集 $X=X_1,...,X_n$ ( $q_i$ 在 $X_i$ 中查询)。返还给R $y_i$ , 返还给S $w_i$ ,如果元素在数据集里面 $y_i =w_i$ ，否则 $y_i$ =随机数。

3.秘密共享

·加法秘密共享：这里用的是shamir秘密共享，需要知道他的特性： $< x > +< y > =< x+y >$ 其中 $< x >$ 是x的秘密共享值。

·线性秘密共享： $c[a]+[b]=[ca+b]$ ,其中 $[a]$ 是a的秘密共享值。

二、multiparty PSI

先说原理，后面自己理解。

这里参与者为P1,...,Pn。选择P1作为R方，P2,...,Pn为S方。所用参与者共同产生三个hash函数 $h_1,h_2,h_3$ 。

P1通过Cuchoo Hashing产生一个Table1，P2,...,Pn使用普通的三次hash产生Table2,...,Tablen（就是将一个数x hash三次放在表的三个位置上）。

使用PSM协议，将P1作为R方发送Table1，P2,...,Pn为S方发送Table2...Tablen。

结束时P1对于表中的每一个位置的元素查询了n-2次，计作 $y_{ij}$ ，其中ij代表在Pi的表中查询第j个元素，P2...Pn获得 $w_{ij}$ 。P1计算 $<a_j>_1=\sum_{i=2}^{n}-y_{ij}$ ,P2...Pn $<a_j>_i=w_{ij}$ ,若查询到元素，可以看出来所有<a>加起来为0。