.png){kind=icon}
.png){kind=icon}
Return
Unbalanced private set intersection with linear communication complexity
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-022-3717-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 MUCH LESS-THAN 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 lambda = 512. Our protocol is efficient and can be applied to resource-constrained devices, such as cell phones.
Keywords:
unbalanced private set intersection
Hash proof system
linear communication complexity
small set
resource-constrained devices
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K