Unbalanced private set intersection with linear communication complexity  

作　　者：Quanyu ZHAO Bingbing JIANG Yuan ZHANG Heng WANG Yunlong MAO Sheng ZHONG 

机构地区：[1]Department of Computer Science and Technology,Nanjing University,Nanjing 210023,China [2]Purple Mountain Lab,Nanjing 211111,China

出　　处：《Science China(Information Sciences)》2024年第3期75-89,共15页中国科学（信息科学）（英文版）

基　　金：supported by National Key Research and Development Program of China (Grant No.2020YFB1005900);Natural Science Foundation on Frontier Leading Technology Basic Research Project of Jiangsu (Grant No.BK20222001);Leading-edge Technology Program of Jiangsu National Science Foundation (Grant No.BK20202001);National Natural Science Foundation of China (Grant Nos.61872176,62272215,61872179,62272222)。

摘　　要：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 220pieces 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 intersection Hash proof system linear communication complexity small set resource-constrained devices 

分 类 号：TN915.04[电子电信—通信与信息系统]