首页|Unbalanced private set intersection with linear communication complexity

Unbalanced private set intersection with linear communication complexity

扫码查看
原文链接
  • 万方数据
  • 维普
The private set intersection(PSI)protocol allows two parties holding a set of integers to compute the intersection of their sets without revealing any additional information to each other.The unbalanced PSI schemes consider a specific setting where a client holds a small set of the size n and a server holds a much larger set of the size m(n<<m).The communication overhead of state-of-the-art balanced PSI schemes is O(m+n)and the unbalanced PSI schemes are O(nlogm).In this paper,we propose a novel secure unbalanced PSI protocol based on a hash proof system.The communication complexity of our protocol grows only linearly with the size of the small set.In other words,our protocol achieves communication overhead of O(n).We test the performance on a personal computer(PC)machine with a local area network(LAN)setting for the network.The experimental results demonstrate that the client only takes 2.01 s of online computation,4.27 MB of round trip communication to intersect 1600 pieces of 32-bit integers with 220 pieces of 32-bit integers with the security parameter λ=512.Our protocol is efficient and can be applied to resource-constrained devices,such as cell phones.

unbalanced private set intersectionHash proof systemlinear communication complexitysmall setresource-constrained devices

Quanyu ZHAO、Bingbing JIANG、Yuan ZHANG、Heng WANG、Yunlong MAO、Sheng ZHONG

展开 >

Department of Computer Science and Technology,Nanjing University,Nanjing 210023,China

Purple Mountain Lab,Nanjing 211111,China

国家重点研发计划Natural Science Foundation on Frontier Leading Technology Basic Research Project of JiangsuLeadingedge Technology Program of Jiangsu National Science Foundation国家自然科学基金国家自然科学基金国家自然科学基金国家自然科学基金

2020YFB1005900BK20222001BK2020200161872176622722156187217962272222

2024

10.1007/s11432-022-3717-9

中国科学:信息科学(英文版)
中国科学院

中国科学:信息科学(英文版)

CSTPCDEI
影响因子：0.715
ISSN：1674-733X
年,卷(期)：2024.67(3)
  • 50