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

Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai

##### 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., 10Mbps) 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

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2019
Keywords
private set intersectionOT extension
Contact author(s)
rosulekm @ eecs oregonstate edu
History
Short URL
https://ia.cr/2019/634

CC BY

BibTeX

@misc{cryptoeprint:2019/634,
author = {Benny Pinkas and Mike Rosulek and Ni Trieu and Avishay Yanai},
title = {SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension},
howpublished = {Cryptology ePrint Archive, Paper 2019/634},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/634}},
url = {https://eprint.iacr.org/2019/634}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.