Faster unbalanced Private Set Intersection in the semi-honest setting
- PDF / 998,803 Bytes
- 18 Pages / 595.276 x 790.866 pts Page_size
- 71 Downloads / 205 Views
REGULAR PAPER
Faster unbalanced Private Set Intersection in the semi-honest setting Amanda Cristina Davi Resende1
· Diego de Freitas Aranha2
Received: 17 May 2019 / Accepted: 26 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Protocols for Private Set Intersection (PSI) are important cryptographic techniques to perform joint operations on datasets in a privacy-preserving way. They allow two parties to compute the intersection of their private sets without revealing any additional information beyond the intersection itself, for one party (one-way) or both parties (mutual). Despite the several PSI protocols available in the literature, only recently techniques have been applied to existing PSI protocols in order to make them more efficient when one of the parties holds a set much smaller than the other. This is a realistic scenario in many cases, characterizing the unbalanced setting. Thus, this paper builds on modern cryptographic engineering techniques and proposes optimizations for a promising one-way PSI protocol based on public-key cryptography secure against semi-honest adversaries. We show that our improvements and optimizations yield a protocol that outperforms the communication complexity and the run time of previous proposals in the unbalanced setting. Keywords Quotient filter · Private Set Intersection · Unbalanced PSI · Software implementation · Rank- and Select-based Quotient Filter (RSQF)
1 Introduction Private Set Intersection (PSI) is a special case of secure multiparty computation (MPC) where two parties perform joint operations on databases while preserving privacy. They have been used in several applications, such as genetic testing of fully sequenced human genomes [2], private contact discovery [9,42], relationship path discovery in social networks [32], botnet detection [33] and proximity testing [35]. PSI protocols allow two parties to compute the intersection of their private sets, where one or both parties learn only the result without revealing any additional informaThis study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) Finance Code 1545003 and by the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) - Finance Code 140738/2017-7.
B
Amanda Cristina Davi Resende [email protected] Diego de Freitas Aranha [email protected]
1
Institute of Computing, University of Campinas (UNICAMP), Campinas, Brazil
2
Department of Engineering, Aarhus University, Århus, Denmark
tion beyond the intersection. When only one party learns the result, the protocols are so-called one-way PSI, whereas when both parties learn the intersection, they are so-called mutual PSI protocols. Moreover, these protocols can also be tailored regarding the size of the sets, being more efficient in the unbalanced case when one set is substantially smaller (usually the client set) than the other, and balanced when the sets have approximately the same size. And finally, the PSI protocols are also classi
Data Loading...
