Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Systems Architecture

Fast post-quantum private set intersection from oblivious pseudorandom function for mobile social networks

Zhuang Shan, Leyou Zhang, Qing Wu, Qiqi Lai, Fuchun Guo

Published Jan 25, 2025• 2 citations
Publisher
DOI
10.1016/j.sysarc.2025.103346

Related papers

A Fair and Efficient Mutual Private Set Intersection Protocol from a Two-Way Oblivious Pseudorandom Function

Sumit Kumar Debnath, Ratna Dutta

Lecture notes in computer science•Jan 1, 2015•4 citations

Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection

Stanisław Jarecki, Xiaomin Liu

Lecture notes in computer science•Jan 1, 2009•305 citations

Efficient post-quantum private set-intersection protocol

Nibedita Kundu, Tanmay Choudhury, Sumit Kumar Debnath

International Journal of Information and Computer Security•Jan 1, 2022•0 citations

Post-quantum secure multi-party private set-intersection in star network topology

Sumit Kumar Debnath, Tanmay Choudhury, Nibedita Kundu +1 more

Journal of Information Security and Applications•Jan 28, 2021•6 citations

Fast Private Set Intersection from Polynomial Multiplication Triples

K.-C. Chen, Yongqiang Li, Ya Han +1 more

Lecture notes in computer science•Jan 1, 2025•0 citations

Post-Quantum Private Set Intersection with Ultra-Efficient Online Performance

Yue Qin, Bei Liang, Hongyuan Cai +1 more

While tremendous progress has been made towards achieving highly efficient and practical Private Set Intersection (PSI) protocols during the last decade, the development of post-quantum PSI is still far from satisfactory. Existing post-quantum PSI protocols encounter a dilemma: while those based on fully homomorphic encryption (FHE) achieve low online communication, they suffer from significant online computation; conversely, protocols based on post-quantum Oblivious Pseudorandom Functions (OPRFs) exhibit excellent online computational performance but incur substantially high online communication. To overcome this dilemma, we present a lattice-based PSI protocol that achieves optimal online performance in both communication and computation. Our solution introduces two core innovations: a robust signal comparison algorithm based on RLWE key exchange, which determines the intersection through signal consistency rather than direct shared key comparison, and an optimized Oblivious Key–Value Stores (OKVS) implementation featuring a composite key–value mapping for efficient handling of high-dimensional RLWE polynomials. We implement the protocol and conduct extensive benchmarks in both symmetric and asymmetric set-size settings. The results show that our construction achieves the lowest online overhead in both computation and communication among all tests. For example, with asymmetric set sizes (212,11041), the online phase requires only 0.132 s, yielding 19× and 282× improvements over FHE-based (CCS’21) and OPRF-based (EUROCRYPT’25) protocols, respectively. Even at (224,11041), our online communication time is only 0.201 s, which is 226× and 184× that of FHE-based and OPRF-based PSI, respectively. Additionally, our online communication overhead is the lowest in all tests; however, this comes at the cost of heavy offline communication overhead for very large set sizes, revealing a clear trade-off between pre-computation and online efficiency. This work addresses a critical gap in post-quantum PSI by delivering a protocol that achieves balanced online communication and computational overhead, thereby enabling broader practical deployment.

Electronics•Dec 19, 2025•0 citations
While tremendous progress has been made towards achieving highly efficient and practical Private Set Intersection (PSI) protocols during the last decade, the development of post-quantum PSI is still far from satisfactory. Existing post-quantum PSI protocols encounter a dilemma: while those based on fully homomorphic encryption (FHE) achieve low online communication, they suffer from significant online computation; conversely, protocols based on post-quantum Oblivious Pseudorandom Functions (OPRFs) exhibit excellent online computational performance but incur substantially high online communication. To overcome this dilemma, we present a lattice-based PSI protocol that achieves optimal online performance in both communication and computation. Our solution introduces two core innovations: a robust signal comparison algorithm based on RLWE key exchange, which determines the intersection through signal consistency rather than direct shared key comparison, and an optimized Oblivious Key–Value Stores (OKVS) implementation featuring a composite key–value mapping for efficient handling of high-dimensional RLWE polynomials. We implement the protocol and conduct extensive benchmarks in both symmetric and asymmetric set-size settings. The results show that our construction achieves the lowest online overhead in both computation and communication among all tests. For example, with asymmetric set sizes (212,11041), the online phase requires only 0.132 s, yielding 19× and 282× improvements over FHE-based (CCS’21) and OPRF-based (EUROCRYPT’25) protocols, respectively. Even at (224,11041), our online communication time is only 0.201 s, which is 226× and 184× that of FHE-based and OPRF-based PSI, respectively. Additionally, our online communication overhead is the lowest in all tests; however, this comes at the cost of heavy offline communication overhead for very large set sizes, revealing a clear trade-off between pre-computation and online efficiency. This work addresses a critical gap in post-quantum PSI by delivering a protocol that achieves balanced online communication and computational overhead, thereby enabling broader practical deployment.