Labeled PSI from Fully Homomorphic Encryption with Malicious Security

By Hao Chen, Zhicong Huang, Kim Laine, Peter Rindal. 2018

250 citations recorded by the source corpus.

Private Set Intersection (PSI) allows two parties, the sender and the receiver, to compute the intersection of their private sets without revealing extra information to each other. We are interested in the unbalanced PSI setting, where (1) the receiver's set is significantly smaller than the sender's, and (2) the receiver (with the smaller set) has a low-power device. Also, in a Labeled PSI setting, the sender holds a label per each item in its set, and the receiver obtains the labels from the items in the intersection. We build upon the unbalanced PSI protocol of Chen, Laine, and Rindal (CCS~2017) in several ways: we add efficient support for arbitrary length items, we construct and implement an unbalanced Labeled PSI protocol with small communication complexity, and also strengthen the security model using Oblivious Pseudo-Random Function (OPRF) in a pre-processing phase. Our protocols outperform previous ones: for an intersection of 220 and $512$ size sets of arbitrary length items our protocol has a total online running time of just $1$~second (single thread), and a total communication cost of 4 MB. For a larger example, an intersection of 228 and 1024 size sets of arbitrary length items has an online running time of $12$ seconds (multi-threaded), with less than 18 MB of total communication.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Secure Federated Submodel Learning (2019, methodology): “The stateof-the-art constructions of private information retrieval include Microsoft’s SealPIR [13] and Labeled PSI [14] and Goolge’s PSIR [15], where two Microsoft protocols have been deployed in its Pung private communication system [16].”
Private Join and Compute from PIR with Default (2020, methodology): “Or - Default protocol, which will be shared by both PIR - with - Default constructions.”
Communication-Computation Trade-offs in PIR (2019, methodology): “Our construction leverages Cuckoo hashing [52] in a new way inspired by ideas from private set intersection [13, 24, 58, 60] and oblivious RAM [37, 55, 57].”