隐私集合运算中的关键数据结构研究
A Survey on Key Data Structures in Private Set Operation
张响鸰 1张聪 2刘巍然 3陈宇4
作者信息
- 1. 山东大学网络空间安全学院,青岛 266237;泉城实验室,济南 250103;密码科学技术全国重点实验室,北京 100878
- 2. 清华大学高等研究院,北京 100084
- 3. 阿里巴巴集团,北京 100120
- 4. 泉城实验室,济南 250103;山东大学网络空间安全学院,青岛 266237;密码科学技术全国重点实验室,北京 100878
- 折叠
摘要
隐私集合运算(private set operation,PSO)是安全多方计算领域的热点问题,它允许两个参与方对各自私有集合进行安全计算,同时避免额外信息泄露.常见的PSO协议包括隐私集合求交和隐私集合求并.高效的隐私集合运算协议的设计与多种高级的数据结构密切相关.然而,目前隐私集合运算中各种数据结构缺乏系统梳理且无同一平台上的效率对比结果.本文将PSO中的关键数据结构分为三类,分别是哈希表、过滤器和不经意键值存储.在明确各类数据结构的基本定义与构造方式的基础上,本文梳理各数据结构的主要功能作用、总结它们在不同协议中的典型应用、探讨它们在PSO中的研究现状与主要进展,并提供各数据结构的性能对比分析与基准测试结果.
Abstract
Private set operation(PSO)is a hot topic in the field of secure multi-party computation.It allows two parties to perform secure computations on their own private sets without information leakage.Generally,PSO protocols include private set intersection(PSI)and private set union(PSU)operations.Advanced data structures play an important role in the design of efficient PSO protocols.However,there is a lack of systematic overview of various data structures in PSO and no uniform efficiency comparison on the same platform among them is provided.This paper classifies the key data structures deployed in existing PSO protocols into three categories:hashing tables,filters,and oblivious key-value stores.After clarifying the basic definitions and constructions of each data structure,this paper compares their main features,summarizes their typical applications,discusses their current research status and main progress in PSO,and provides performance analysis and benchmark results for each data structure.
关键词
隐私集合运算/数据结构/安全多方计算Key words
private set operation/data structure/secure multi-party computation引用本文复制引用
基金项目
国家重点研发计划(2021YFA1000600)
国家自然科学基金(62272269)
山东省"泰山学者"青年专家基金()
山东省实验室项目(SYS202201)
泉城实验室重点项目(QCLZD202302)
国家社会科学基金重大项目(22&ZD147)
出版年
2024
国家科技期刊平台
NSTL
万方数据