Paper 2021/266

VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE

Peter Rindal, Visa (United States)
Phillipp Schoppmann, Google (United States)
Abstract

In this work we present a new construction for a batched Oblivious Pseudorandom Function (OPRF) based on Vector-OLE and the PaXoS data structure. We then use it in the standard transformation for achieving Private Set Intersection (PSI) from an OPRF. Our overall construction is highly efficient with $O(n)$ communication and computation. We demonstrate that our protocol can achieve malicious security at only a very small overhead compared to the semi-honest variant. For input sizes $n = 2^{20}$, our malicious protocol needs 6.2 seconds and less than 59 MB communication. This corresponds to under 450 bits per element, which is the lowest number for any published PSI protocol (semi-honest or malicious) to date. Moreover, in theory our semi-honest (resp. malicious) protocol can achieve as low as 219 (resp. 260) bits per element for $n=2^{20}$ at the added cost of interpolating a polynomial over $n$ elements. As a second contribution, we present an extension where the output of the PSI is secret-shared between the two parties. This functionality is generally referred to as Circuit-PSI. It allows the parties to perform a subsequent MPC protocol on the secret-shared outputs, e.g., train a machine learning model. Our circuit PSI protocol builds on our OPRF construction along with another application of the PaXoS data structure. It achieves semi-honest security and allows for a highly efficient implementation, up to 3x faster than previous work.

Note: Update to more accurately reflect the bound on the size of the malicious receiver set. We thank Seongkwang Kim and Yongha Son for bringing this to our attention.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2021
Keywords
Private Set IntersectionSecure ComputationVector OLE
Contact author(s)
peterrindal @ gmail com
schoppmann @ google com
History
2024-08-08: last of 3 revisions
2021-03-03: received
See all versions
Short URL
https://ia.cr/2021/266
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/266,
      author = {Peter Rindal and Phillipp Schoppmann},
      title = {{VOLE}-{PSI}: Fast {OPRF} and Circuit-{PSI} from Vector-{OLE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/266},
      year = {2021},
      url = {https://eprint.iacr.org/2021/266}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.