如何解读可扩展的多方隐私集合交集技术？

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

原文摘要：本文字记录了阅读某篇论文的笔记。论文概述了两类MPSI协议，采用的星型拓扑结构，存在一个leader，需要与其他参与者交互。优点是所有各方都必须同时在线：能抗半诚实攻击。

改写内容：笔记摘要：阅读了某论文，记录了其要点。论文介绍了两种MPSI协议，采用星型拓扑，一个中心节点（leader）与其它参与者互动。此协议优点在于各方需同时在线，能抵御半诚实攻击。

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

摘要

本文给出两种MPSI协议，采用的是星型拓扑结构，即有一个leader，需要和其他参与者交互。优点是并非所有各方都必须同时在线：

（1）能抗半诚实攻击

• 通信复杂度与输入数据集大小呈线性关系；
• 计算复杂度是leader方输入数据的二次关系，其他参与者的输入集大小呈线性关系，后面可以使用两种hash可以消除此消耗。

（2）能抗恶意攻击
通信复杂度降为\(O((n^2+nm_{MAX}+nm_{MIN}logm_{MAX})k)\)bit，其中\(m_{MAX}\)和\(m_{MIN}\)分别为\(n\)个参与者的输入最大量和输入最小量

另外上面提到本文的半诚实方案是基于文章改进的，是最早提出MPSI的，两方协议是：

画成图表示就是：

和下面介绍基于不经意多项式计算（OPE）的图是一样的。

介绍 MPSI

MPC的安全性通常是通过两种对抗模型来证明的：
（1）半诚实模型
敌手遵循协议执行，但会试图从协议中获取更多信息。