Paper 2025/1114 Original: eprint.iacr.org/2025/1114 ↗

VCR: Fast Private Set Intersection with Improved VOLE and CRT-Batching

Abstract

Private set intersection (PSI) allows two participants to compute the intersection of their private sets without revealing any additional information beyond the intersection itself. It is known that oblivious linear evaluation (OLE) can be used to construct the online efficient PSI protocol (Kerschbaum \textit{et al.}, NDSS'23). However, oblivious transfer (OT) and fully homomorphic encryption (FHE)-based offline OLE generation are expensive, and the online computational complexity is super-linear and still a heavy burden for large-scale sets. In this paper, we propose VCR, an efficient PSI protocol from vector OLE (VOLE) with the offline-online paradigm. Concretely, we first propose the batched short VOLE protocol to reduce offline overhead for generating VOLE tuples. Experiments demonstrate that VCR outperforms prior art. Then, we design a batched private membership test protocol from pre-computed VOLE to accelerate the online computation. Compared to the previous work of Kerschbaum \textit{et al.} (NDSS'23), we reduce the total communication costs (resp. running time) by $341\times$ and $9.1\times$ (resp. $6.5\times$ and $2.5\times$) on average for OT- and FHE-based protocols.