2021年：如何测试阈值隐私集合的多方基数？

本文共计5263个文字，预计阅读时间需要22分钟。

《文本记录阅读该论文的笔记》

本文基于安全同态加密算法，提出了一个新的允许方案（N）。该方案通过检查其输入集的交集是否大于（n-t），来判断通信的复杂度是否为（O(Nt^2)）。

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

本文基于阈值加法同态加密方案提出了一个新的允许\(N\)方检查其输入集的交集是否大于\(n-t\)的PSI方案，该协议的通信复杂度为\(O(Nt^2)\)。
注意：\(N\)指的是多少个参与方、\(n\)是输入集的大小、\(t\)是预先设定的阈值，也是阈值。

该方案基于The Communication Complexity of Threshold Private Set Intersection-2019：解读进行的改进。
该协议可以用于各方知道交集很大，但不知道具体多大时，可以使用！

（1）该协议的通信复杂度不依赖于输入集的大小，而取决于阈值\(t\)的大小
（2）基于阈值的PSI协议分为两部分：

• 交集的势测试（Cardinality Testing ），即测试参与方的交集是否大于\(n-t\)
• PSI：计算交集

两方阈值PSI：

（1）双方先检测交集大小是否\(> n-t\)
（2）若满足，则求交（获取交集）；否则，什么也得不到（获取不到交集）

标准PSI和阈值PSI的对比：

• 标准的PSI更在乎交集，而不在乎交集的大小，而阈值PSI更关注交集的大小。