Paper 2023/745

PSI from ring-OLE

Wutichai Chongchitmate, Chulalongkorn University
Yuval Ishai, Technion – Israel Institute of Technology
Steve Lu, Stealth Software Technologies, Inc.
Rafail Ostrovsky, University of California, Los Angeles

Private set intersection (PSI) is one of the most extensively studied instances of secure computation. PSI allows two parties to compute the intersection of their input sets without revealing anything else. Other useful variants include PSI-Payload, where the output includes payloads associated with members of the intersection, and PSI-Sum, where the output includes the sum of the payloads instead of individual ones. In this work, we make two related contributions. First, we construct simple and efficient protocols for PSI and PSI-Payload from a ring version of oblivious linear function evaluation (ring-OLE) that can be efficiently realized using recent ring-LPN based protocols. A standard OLE over a field F allows a sender with $a,b \in \mathbb{F}$ to deliver $ax+b$ to a receiver who holds $x \in \mathbb{F}$. Ring-OLE generalizes this to a ring $\mathcal{R}$, in particular, a polynomial ring over $\mathbb{F}$. Our second contribution is an efficient general reduction of a variant of PSI-Sum to PSI-Payload and secure inner product. Our protocols have better communication cost than state-of-the-art PSI protocols, especially when requiring security against malicious parties and when allowing input-independent preprocessing. Compared to previous maliciously secure PSI protocols that have a similar com- putational cost, our online communication is 2x better for small sets (28 − 212 elements) and 20% better for large sets (220 − 224). Our protocol is also simpler to describe and implement. We obtain even bigger improvements over the state of the art (4-5x better running time) for our variant of PSI-Sum.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. CCS '22
Private Set IntersectionPSI-SumRing-OLE
Contact author(s)
wutichai ch @ chula ac th
yuvali @ cs technion ac il
steve @ stealthsoftwareinc com
rafail @ cs ucla edu
2023-05-25: approved
2023-05-24: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Wutichai Chongchitmate and Yuval Ishai and Steve Lu and Rafail Ostrovsky},
      title = {PSI from ring-OLE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/745},
      year = {2023},
      doi = {10.1145/3548606.3559378},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.