Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Private Set IntersectionVector Oblivious Linear EvaluationChinese Remainder Theorem
- Contact author(s)
-
jingweizhan @ iie ac cn
chenxiaojun @ iie ac cn
chenxudong @ iie ac cn
dongye @ nus edu cn
yxyangjnu @ gmail com
liuqiang2022 @ iie ac cn - History
- 2025-06-16: approved
- 2025-06-13: received
- See all versions
- Short URL
- https://ia.cr/2025/1114
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1114,
author = {Weizhan Jing and Xiaojun Chen and Xudong Chen and Ye Dong and Yaxi Yang and Qiang Liu},
title = {{VCR}: Fast Private Set Intersection with Improved {VOLE} and {CRT}-Batching},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1114},
year = {2025},
url = {https://eprint.iacr.org/2025/1114}
}