Abstract
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.
基金项目
国家重点研发计划(2020YFB1005900)
Natural Science Foundation on Frontier Leading Technology Basic Research Project of Jiangsu(BK20222001)
Leadingedge Technology Program of Jiangsu National Science Foundation(BK20202001)
国家自然科学基金(61872176)
国家自然科学基金(62272215)
国家自然科学基金(61872179)
国家自然科学基金(62272222)
维普
万方数据