International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension

Authors:
Benny Pinkas
Mike Rosulek
Ni Trieu
Avishay Yanai
Download:
DOI: 10.1007/978-3-030-26954-8_13 (login may be required)
Search ePrint
Search Google
Abstract: We describe a novel approach for two-party private set intersection (PSI) with semi-honest security. Compared to existing PSI protocols, ours has a more favorable balance between communication and computation. Specifically, our protocol has the lowest monetary cost of any known PSI protocol, when run over the Internet using cloud-based computing services (taking into account current rates for CPU + data). On slow networks (e.g., 10 Mbps) our protocol is actually the fastest.Our novel underlying technique is a variant of oblivious transfer (OT) extension that we call sparse OT extension. Conceptually it can be thought of as a communication-efficient multipoint oblivious PRF evaluation. Our sparse OT technique relies heavily on manipulating high-degree polynomials over large finite fields (i.e. elements whose representation requires hundreds of bits). We introduce extensive algorithmic and engineering improvements for interpolation and multi-point evaluation of such polynomials, which we believe will be of independent interest.Finally, we present an extensive empirical comparison of state-of-the-art PSI protocols in several application scenarios and along several dimensions of measurement: running time, communication, peak memory consumption, and—arguably the most relevant metric for practice—monetary cost.
Video from CRYPTO 2019
BibTeX
@article{crypto-2019-29920,
  title={SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11694},
  pages={401-431},
  doi={10.1007/978-3-030-26954-8_13},
  author={Benny Pinkas and Mike Rosulek and Ni Trieu and Avishay Yanai},
  year=2019
}