Flash: Fast, Lightweight Private Set Intersection with Malicious Security Almost for Free
Private set intersection (PSI) allows two parties to learn the intersection of their input sets without revealing any non-matching elements, and underlies applications such as private contact discovery, password-breach detection, and illegal-content detection. Recent state-of-the-art PSI protocols follow a vector oblivious linear evaluation (VOLE) and oblivious key-value store (OKVS) paradigm. While highly efficient, this approach inherits the algorithmic and implementation complexity of OKVS. In this work, we propose a lightweight paradigm based solely on VOLE. Our protocol separates a VOLE phase, which generates all required correlations, from a simple PSI phase that consumes these correlations directly, avoiding any OKVS encoding or decoding. We formally prove its security in both semi-honest and malicious models. Experimental results show that our construction achieves up to 3.7× speedup over state-of-the-art PSI in the LAN setting and up to 2.3× in the WAN setting. The malicious extension adds an average running-time overhead of 15.40% and an average communication overhead of 22.84% across the evaluated settings.
Authors
- Ze Jiang (ORCID: https://orcid.org/0009-0005-5471-7124)
- Xiangyi Fang
Institutions
- Commercial Aircraft Corporation of China (China) (CN)
- Chongqing University (CN)
- Shanghai Civil Aviation College (CN)
Publication Details
- Journal
- Journal of Machine Learning and Information Security
- Published
- 2026-11-17
- DOI
- https://doi.org/10.53941/jmlis.2026.100022
- Primary Topic
- Cryptography and Data Security
- Type
- article
- Field-Weighted Citation Impact
- 0.00