论文分享｜基于Ring-OLE构造的隐私求交（PSI）协议（CCS 2022)

论文来源：CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications SecurityNovember 2022

论文名称：PSI from Ring-OLE

论文链接：https://doi.org/10.1145/3548606.3559378

本文来源:  SecurityLabUJN

整理人：济南大学信息科学与工程学院2022级硕士研究生卢世猛

1

引言

隐私集合求交（PSI）是安全计算研究最广泛的实例之一。PSI允许两方计算其输入集的交集，而无需透露任何其他信息。其他有用的变体包括PSI-Payload（其中输出包括与交集成员相关的有效负载）和PSI-Sum（其中输出包括有效负载的总和而不是各个有效负载）。

本文主要做出了两项相关的贡献。首先，我们从不经意线性函数评估（ring-OLE）的环版本构建简单高效的PSI和PSI-Payload协议，该协议可以使用最新的基于环LPN的协议有效实现。域F上的标准OLE允许具有 的发送方将传递给持有的接收方。Ring-OLE 将其推广到环 R，特别是  上的多项式环。第二个贡献是将 PSI-Sum 的变体有效地普遍简化为 PSI-Payload和安全内积。我们的协议比最先进的PSI协议具有更好的通信成本，特别是在需要针对恶意方的安全性以及允许独立于输入的预处理时。与之前具有类似计算成本的恶意安全 PSI 协议相比，我们的在线通信对于小型集合（ 个元素）来说要好 2 倍，对于大型集合（）要好 20%。我们的协议也更容易描述和实现。我们的 PSI-Sum 变体比现有技术取得了更大的改进（运行时间缩短了 4-5 倍）。

2

关键技术介绍

1. Oblivious Linear Function Evaluation（OLE）

  不经意线性计算（Oblivious Linear Function Evaluation，OLE）是一种密码学协议，用于在保护数据隐私的前提下执行线性函数的计算。它允许两个参与者（通常称为发送方和接收方）合作进行计算，而无需彼此了解对方的输入。

1. Ring-OLE

  我们的主要PSI协议基于OLE的通用版本，我们称之为𝑟𝑖𝑛𝑔-𝑂𝐿𝐸。在 协议中，输入位于（有限）环中。在这项工作中，我们考虑一个商环，其中每个元素都可以由有界次数的多项式表示。 上的标准可以被视为度数界限为0的特殊情况。

  当环𝑅有限时，双方输入均被环𝑅的均匀采样元素替换的 𝑟𝑂𝐿𝐸 变体称为随机 𝑟𝑂𝐿𝐸 (𝑟𝑟𝑂𝐿𝐸)。

  使用实现:

推导：

  本文考虑一个多项式环 𝑅 = 𝐹[𝑋]。由于多项式环不是有限的，先前依赖于𝑟𝑟𝑂𝐿𝐸的构造不能直接应用。本文考虑 𝑅 = 𝐹[𝑋] 的特殊用途 𝑟𝑂𝐿𝐸，并对每个多项式的次数和首项系数进行一些附加限制。

推导同上，只要确定即可

1. Secure Inner Product

  Secure Inner Product（安全内积）是一种密码学协议或技术，旨在允许两个参与者在不相互泄露私有输入的情况下计算他们的输入向量的内积。

3

本文PSI协议

• PSI from Ring-OLE
  

注：当元素属于交集元素，那么多项式的值为0。

• PSI payload from Ring-OLE

  PSI payload：发送方Sender集合中的每个元素都有一个关联值，称为负载。接收方Receiver不仅可以获取交集元素还能获取每个交集元素的负载值。

• PSI+Sum

  PSI+Sum：交集元素负载和秘密分享给Sender和Receiver，同时Receiver获得集合交集元素。

4

实验结果

本文提出的PSI协议与其他PSI协议通信量上的对比：

本文提出的PSI协议与其他PSI协议运行时间上的对比：

本文提出的PSI+Sum协议与其他PSI-Sum协议在运行时间上的对比：

分享仅供学习参考，若有不当，请联系我们处理。

END
热文推荐