2611005637
  • Open Access
  • Article

Flash: Fast, Lightweight Private Set Intersection with Malicious Security Almost for Free

  • Ze Jiang 1 and 
  • Xiangyi Fang 2,*

Received: 25 June 2026 | Revised: 20 October 2026 | Accepted: 10 November 2026 | Published: 17 November 2026

Abstract

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.

References 

  • 1.

    Freedman, M.J.; Nissim, K.; Pinkas, B. Efficient Private Matching and Set Intersection. In Advances in Cryptology—EUROCRYPT 2004, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2–6 May 2004; Springer: Berlin/Heidelberg, Germany, 2004; pp. 1–19. https://doi.org/10.1007/978-3-540-24676-3_1.

  • 2.

    Huang, Y.; Evans, D.; Katz, J. Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? In Proceedings of the 19th Annual Network and Distributed System Security Symposium (NDSS 2012), San Diego, CA, USA, 5–8 February 2012.

  • 3.

    Hetz, L.; Schneider, T.; Weinert, C. Scaling Mobile Private Contact Discovery to Billions of Users. In Computer Security—ESORICS 2023, Proceedings of the 28th European Symposium on Research in Computer Security, the Hague, the Netherlands, 25–29 September 2023; Springer: Cham, Switzerland, 2024; pp. 455–476. https://doi.org/10.1007/978-3-031-50594-2_23.

  • 4.

    Lauter, K.; Kannepalli, S.; Laine, K.; et al. Password Monitor: Safeguarding Passwords in Microsoft Edge. Available online: https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/ (accessed on 13 January 2026).

  • 5.

    Scheffler, S.; Mayer, J. SoK: Content Moderation for End-to-End Encryption. Proc. Priv. Enhancing Technol. 2023, 2023, 403–429. https://doi.org/10.56553/popets-2023-0060.

  • 6.

    Pinkas, B.; Rosulek, M.; Trieu, N.; et al. PSI from PaXoS: Fast, Malicious Private Set Intersection. In Advances in Cryptology—EUROCRYPT 2020, Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 10–14 May 2020; Springer: Cham, Switzerland, 2020; pp. 739–767. https://doi.org/10.1007/978-3-030-45724-2_25.

  • 7.

    Garimella, G.; Pinkas, B.; Rosulek, M.; et al. Oblivious Key-Value Stores and Amplification for Private Set Intersection. In Advances in Cryptology—CRYPTO 2021, Proceedings of the 41st Annual International Cryptology Conference, CRYPTO 2021, Online, 16–20 August 2021; Springer: Cham, Switzerland, 2021; pp. 395–425. https://doi.org/10.1007/978-3-030-84245-1_14.

  • 8.

    Rindal, P.; Schoppmann, P. VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE. In Advances in Cryptology—EUROCRYPT 2021, Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 17–21 October 2021; Springer: Cham, Switzerland, 2021; pp. 901–930. https://doi.org/10.1007/978-3-030-77886-6_31.

  • 9.

    Raghuraman, S.; Rindal, P. Blazing Fast PSI from Improved OKVS and Subfield VOLE. In Proceedings of the CCS’22: 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, CA, USA, 7–11 November 2022; pp. 2505–2517. https://doi.org/10.1145/3548606.3560658.

  • 10.

    Bienstock, A.; Patel, S.; Seo, J.Y.; et al. Near-Optimal Oblivious Key-Value Stores for Efficient PSI, PSU and Volume-Hiding Multi-Maps. In Proceedings of the USENIX Security Symposium (USENIX Security), Anaheim, CA, USA, 9–11 August 2023; pp. 301–318.

  • 11.

    Meadows, C. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In Proceedings of the 1986 IEEE Symposium on Security and Privacy, Oakland, CA, USA, 7–9 April 1986; pp. 134–137. https://doi.org/10.1109/sp.1986.10022.

  • 12.

    Chen, H.; Laine, K.; Rindal, P. Fast Private Set Intersection from Homomorphic Encryption. In Proceedings of the CCS’17: 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA, 30 October–3 November 2017; pp. 1243–1255. https://doi.org/10.1145/3133956.3134061.

  • 13.

    Ghosh, S.; Simkin, M. The Communication Complexity of Threshold Private Set Intersection. In Proceedings of the 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2019; pp. 3–29. https://doi.org/10.1007/978-3-030-26951-7_1.

  • 14.

    Hazay, C.; Lindell, Y. Efficient Protocols for Set Intersection and Pattern Matching with Security against Malicious and Covert Adversaries. In Theory of Cryptography, Proceedings of the Fifth Theory of Cryptography Conference, TCC 2008, New York, NY, USA, 19–21 March 2008; Springer: Berlin/Heidelberg, Germany, 2008; pp. 155–175. https://doi.org/10.1007/978-3-540-78524-8_10.

  • 15.

    Dong, C.; Chen, L.; Wen, Z. When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol. In Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, Berlin, Germany, 4–8 November 2013; pp. 789–800. https://doi.org/10.1145/2508859.2516701.

  • 16.

    Pinkas, B.; Schneider, T.; Zohner, M. Faster Private Set Intersection Based on OT Extension. In Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, 20–22 August 2014; pp. 797–812.

  • 17.

    Pinkas, B.; Schneider, T.; Segev, G.; et al. Phasing: Private Set Intersection Using Permutation-Based Hashing. In Proceedings of the USENIX Security Symposium (USENIX Security), Washington, DC, USA, 12–14 August 2015; pp. 515–530.

  • 18.

    Kolesnikov, V.; Kumaresan, R.; Rosulek, M.; et al. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. In Proceedings of the CCS’16: 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016; pp. 818–829. https://doi.org/10.1145/2976749.2978381.

  • 19.

    Pinkas, B.; Schneider, T.; Zohner, M. Scalable Private Set Intersection Based on OT Extension. ACM Trans. Priv. Secur. 2018, 21, 7. https://doi.org/10.1145/3154794.

  • 20.

    Pinkas, B.; Rosulek, M.; Trieu, N.; et al. SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension. In Proceedings of the Annual International Cryptology Conference (CRYPTO), Santa Barbara, CA, USA, 18–22 August 2019; pp. 401–431. https://doi.org/10.1007/978-3-030-26954-8_13.

  • 21.

    Chase, M.; Miao, P. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF. In Advances in Cryptology—CRYPTO 2020, Proceedings of the 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, 17–21 August 2020; Springer: Cham, Switzerland, 2020; pp. 34–63. https://doi.org/10.1007/978-3-030-56877-1_2.

  • 22.

    Mahdavi, R.A.; Lukas, N.; Ebrahimianghazani, F.; et al. PEPSI: Practically Efficient Private Set Intersection in the Unbalanced Setting. In Proceedings of the 33rd USENIX Security Symposium, Philadelphia, PA, USA, 14–16 August 2024; pp. 6453–6470.

  • 23.

    Chielle, E.; Maniatakos, M. Recurrent Private Set Intersection for Unbalanced Databases with Cuckoo Hashing and Leveled FHE. In Proceedings of the Network and Distributed System Security Symposium, San Diego, CA, USA, 24–28 February 2025. https://doi.org/10.14722/ndss.2025.240365.

  • 24.

    Uzun, E.; Chung, S.P.; Kolesnikov, V.; et al. Fuzzy Labeled Private Set Intersection with Applications to Private Real-Time Biometric Search. In Proceedings of the 30th USENIX Security Symposium, Online, 11–13 August 2021; pp. 911–928.

  • 25.

    Liu, Q.; Guo, X.; Yang, K.; et al. Labeled Private Set Intersection from Distributed Point Function. IEEE Trans. Inf. Forensics Secur. 2025, 20, 2970–2983. https://doi.org/10.1109/tifs.2025.3550059.

  • 26.

    Gao, Y.; Luo, Y.; Wang, L.; et al. Efficient Scalable Multi-Party Private Set Intersection(-Variants) from Bicentric Zero-Sharing. In Proceedings of the CCS’24: ACM SIGSAC Conference on Computer and Communications Security, Salt Lake City, UT, USA, 14–18 October 2024; pp. 4137–4151. https://doi.org/10.1145/3658644.3690245.

  • 27.

    Dong, M.; Chen, Y.; Zhang, C.; et al. Multi-Party Private Set Operations from Predicative Zero-Sharing. In Proceedings of the CCS’25: ACM SIGSAC Conference on Computer and Communications Security, Taipei, Taiwan, 13–17 October 2025; pp. 4079–4093. https://doi.org/10.1145/3719027.3765234.

  • 28.

    Wu, M.; Yuen, T.H. Efficient Unbalanced Private Set Intersection Cardinality and User-Friendly Privacy-Preserving Contact Tracing. In Proceedings of the 32nd USENIX Security Symposium, Anaheim, CA, USA, 9–11 August 2023; pp. 283–300. https://dl.acm.org/doi/10.5555/3620237.3620254.

  • 29.

    Yang, Y.; Yang, Y.; Chen, X.; et al. DMPSI: Efficient Scalable Delegated Multiparty PSI and PSI-CA with Oblivious PRF. IEEE Trans. Serv. Comput. 2024, 17, 497–508. https://doi.org/10.1109/tsc.2024.3356667.

  • 30.

    Raghuraman, S.; Rindal, P.; Tanguy, T. Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN. In Advances in Cryptology—CRYPTO 2023, Proceedings of the 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, 20–24 August 2023; Springer: Cham, Switzerland, 2023; pp. 602–632. https://doi.org/10.1007/978-3-031-38551-3_19.

  • 31.

    Demmler, D.; Rindal, P.; Rosulek, M.; et al. PIR-PSI: Scaling Private Contact Discovery. Proc. Priv. Enhancing Technol. 2018, 2018, 159–178. https://doi.org/10.1515/popets-2018-0037.

  • 32.

    Rindal, P.; Rosulek, M. Improved Private Set Intersection against Malicious Adversaries. In Advances in Cryptology—EUROCRYPT 2017, Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, 30 April– 4 May 2017; Springer: Cham, Switzerland, 2017; pp. 235–259. https://doi.org/10.1007/978-3-319-56620-7_9.

  • 33.

    Rindal, P.; Rosulek, M. Malicious-Secure Private Set Intersection via Dual Execution. In Proceedings of the CCS’17: 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA, 30 October–3 November 2017; pp. 1229–1242. https://doi.org/10.1145/3133956.3134044.

Share this article:
How to Cite
Jiang, Z.; Fang, X. Flash: Fast, Lightweight Private Set Intersection with Malicious Security Almost for Free. Journal of Machine Learning and Information Security 2026, 2 (4), 22. https://doi.org/10.53941/jmlis.2026.100022.
RIS
BibTex
Copyright & License
article copyright Image
Copyright (c) 2026 by the authors.
Article Metrics
64
Article Views
0
Citations