Paper 2018/787

Labeled PSI from Fully Homomorphic Encryption with Malicious Security

Hao Chen, Zhicong Huang, Kim Laine, and Peter Rindal

Abstract

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 {\it 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 {\it 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 $2^{20}$ 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 $2^{28}$ 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. CCS 2018
DOI
10.1145/3243734.3243836
Keywords
private set intersectionhomomorphic encryption
Contact author(s)
kim laine @ gmail com
History
2018-09-01: received
Short URL
https://ia.cr/2018/787
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/787,
      author = {Hao Chen and Zhicong Huang and Kim Laine and Peter Rindal},
      title = {Labeled PSI from Fully Homomorphic Encryption with Malicious Security},
      howpublished = {Cryptology ePrint Archive, Paper 2018/787},
      year = {2018},
      doi = {10.1145/3243734.3243836},
      note = {\url{https://eprint.iacr.org/2018/787}},
      url = {https://eprint.iacr.org/2018/787}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.