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

ACM SIGSAC Conference on Computer and Communications Security (CCS)

Compact and Malicious Private Set Intersection for Small Sets

Mike Rosulek, Ni Trieu

Published Nov 12, 2021• 82 citations
Publisher

Abstract

We describe a protocol for two-party private set intersection (PSI) based on Diffie-Hellman key agreement. The protocol is proven secure against malicious parties, in the ideal permutation + random oracle model.
DOI
10.1145/3460120.3484778

Related papers

Securely Computing Protocol of Set Intersection under the Malicious Model

Xin Liu, Weitong Chen, Naixue N. Xiong +3 more

Private set intersection (PSI) is a valuable technique with various practical applications, including secure matching of communication packets in the Internet of Things. However, most of the currently available two-party PSI protocols are based on the oblivious transfer (OT) protocol, which is computationally expensive and results in significant communication overhead. In this paper, we propose a new coding method to design a two-party PSI protocol under the semi-honest model. We analyze possible malicious attacks and then develop a PSI protocol under the malicious model using the Paillier cryptosystem, cut-and-choose, zero-knowledge proof, and other cryptographic tools. By adopting the real/ideal model paradigm, we prove the protocol’s security under the malicious model, which is more efficient compared to the existing related schemes.

Electronics•May 26, 2023•1 citation

Post-Quantum Private Set Intersection for Small Sets

Junxin Liu, Mike Rosulek, Ni Trieu

Are private set intersection (PSI) protocols ready for the post-quantum future? We focus on the PSI protocol of Rosulek & Trieu (''RT21'', ACM CCS 2021), which is the current state-of-the-art for PSI on small sets (less than a thousand items). The RT21 protocol presents some fundamental barriers to post-quantum security. First, although it is written in terms of an arbitrary KEM, it requires certain properties of Diffie-Hellman KEM that simply are not satisfied by any post-quantum candidates. Second, even if adapted to post-quantum KEMs, it would require an ideal permutation with blocklength larger than any known viable candidate. We show how to modify the RT21 to make it compatible with post-quantum KEM candidates like ML-KEM. We also describe a direct domain-extension construction for ideal permutations, showing how to construct a huge-block ideal permutation directly from one with smaller blocklength, such as the Keccak permutation family. Along the way, we also introduce new abstractions for oblivious key-value stores (Garimella et al., Crypto 2021) that make the analysis of these kinds of PSI protocols more modular. We implemented our protocol and evaluated its performance across different network settings and instantiations. We achieve PSI from standardized post-quantum primitives with latency as low as 0.25 ms/item and communication as low as 1.67 KiB/item. We find that the performance penalty for post-quantum security ranges from 1.25× to 5.92× in latency and is 16.7× in communication, depending on the instantiation.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2026•0 citations

Card-Based Protocols for Private Set Intersection and Union

Anastasiia Doi, Tomoki Ono, Yoshiki Abe +5 more

Abstract Card-based cryptography aims to realize secure multiparty computation with physical cards. This paper is the first to address Private Set Intersection (PSI) and Private Set Union (PSU) in card-based cryptography. PSI and PSU are well-studied secure computation protocols to compute the set intersection and the set union, respectively. We show two-party PSI and PSU protocols in each of the two operation models: one is the shuffle-based model in which parties perform all operations publicly, and the other is the private-permutation-based model that allows parties to perform some operations privately. In the shuffle-based model, we show PSI and PSU protocols can be realized with existing secure AND and OR protocols, respectively. However, these protocols have an issue of increasing the number of shuffles depending on the size of the universal set. To resolve the issue, we further propose PSI and PSU protocols with only one shuffle at the cost of increasing the number of cards. In the private-permutation-based model, we show PSI and PSU protocols can be achieved with existing secure AND and OR protocols, respectively, as in the shuffle-based protocols. These protocols have an advantage of requiring only one private permutation and one communication. We further show that the number of cards of these protocols can be reduced at the cost of increasing the number of private permutations and communications.

New Generation Computing•Jun 22, 2024•6 citations

Two-party Private Set Intersection with an Untrusted Third Party

Phi Hung Le, Samuel Ranellucci, Steven Gordon

We construct new protocols for two parties to securely compute on the items in their intersection. Our protocols make use of an untrusted third party that has no input. The use of this party allows us to construct highly efficient protocols that are secure against a single malicious corruption.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 6, 2019•41 citations

A multi-party quantum private set intersection based on greatest common divisor

Muhammad Imran

Private set intersection (PSI) is a cryptographic primitive that allows two or more parties to learn the intersection of their input sets and nothing else. In this paper, we introduce a new secure multi-party quantum computation for the greatest common divisor (GCD) and a PSI protocol based on it. The protocol extends the recent least common multiple (LCM)-based quantum private set union protocol by Liu et al. Performance analysis verifies the correctness and demonstrates the entire security of the suggested protocols in the semi-honest model. Additionally, it has been demonstrated that the complexity is efficient in terms of the input set size.

International Journal of Quantum Information•Dec 19, 2024•0 citations

Private set intersection: New generic constructions and feasibility results

Paolo D’Arco, María Isabel González Vasco, Ángel Luis Pérez del Pozo +2 more

In this paper we focus on protocols for private set intersection (PSI), through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage.In the unconditional setting we evidence that PSI is impossible to realize and that unconditionally secure size-hiding PSI is possible assuming a set-up authority is present in an set up phase. In the computational setting we give a generic construction using smooth projective hash functions for languages derived from perfectly-binding commitments. Further, we give two size-hiding constructions: the first one is theoretical and evidences the equivalence between PSI, oblivious transfer and the secure computation of the AND function. The second one is a twist on the oblivious polynomial evaluation construction of Freedman et al. from EUROCRYPT 2004. We further sketch a generalization of the latter using algebraic-geometric techniques. Finally, assuming again there is a set-up authority (yet not necessarily trusted) we present very simple and efficient constructions that only hide the size of the client's set.

Advances in Mathematics of Communications•Jan 1, 2017•3 citations
Private set intersection (PSI) is a valuable technique with various practical applications, including secure matching of communication packets in the Internet of Things. However, most of the currently available two-party PSI protocols are based on the oblivious transfer (OT) protocol, which is computationally expensive and results in significant communication overhead. In this paper, we propose a new coding method to design a two-party PSI protocol under the semi-honest model. We analyze possible malicious attacks and then develop a PSI protocol under the malicious model using the Paillier cryptosystem, cut-and-choose, zero-knowledge proof, and other cryptographic tools. By adopting the real/ideal model paradigm, we prove the protocol’s security under the malicious model, which is more efficient compared to the existing related schemes.
Are private set intersection (PSI) protocols ready for the post-quantum future? We focus on the PSI protocol of Rosulek & Trieu (''RT21'', ACM CCS 2021), which is the current state-of-the-art for PSI on small sets (less than a thousand items). The RT21 protocol presents some fundamental barriers to post-quantum security. First, although it is written in terms of an arbitrary KEM, it requires certain properties of Diffie-Hellman KEM that simply are not satisfied by any post-quantum candidates. Second, even if adapted to post-quantum KEMs, it would require an ideal permutation with blocklength larger than any known viable candidate. We show how to modify the RT21 to make it compatible with post-quantum KEM candidates like ML-KEM. We also describe a direct domain-extension construction for ideal permutations, showing how to construct a huge-block ideal permutation directly from one with smaller blocklength, such as the Keccak permutation family. Along the way, we also introduce new abstractions for oblivious key-value stores (Garimella et al., Crypto 2021) that make the analysis of these kinds of PSI protocols more modular. We implemented our protocol and evaluated its performance across different network settings and instantiations. We achieve PSI from standardized post-quantum primitives with latency as low as 0.25 ms/item and communication as low as 1.67 KiB/item. We find that the performance penalty for post-quantum security ranges from 1.25× to 5.92× in latency and is 16.7× in communication, depending on the instantiation.
Abstract Card-based cryptography aims to realize secure multiparty computation with physical cards. This paper is the first to address Private Set Intersection (PSI) and Private Set Union (PSU) in card-based cryptography. PSI and PSU are well-studied secure computation protocols to compute the set intersection and the set union, respectively. We show two-party PSI and PSU protocols in each of the two operation models: one is the shuffle-based model in which parties perform all operations publicly, and the other is the private-permutation-based model that allows parties to perform some operations privately. In the shuffle-based model, we show PSI and PSU protocols can be realized with existing secure AND and OR protocols, respectively. However, these protocols have an issue of increasing the number of shuffles depending on the size of the universal set. To resolve the issue, we further propose PSI and PSU protocols with only one shuffle at the cost of increasing the number of cards. In the private-permutation-based model, we show PSI and PSU protocols can be achieved with existing secure AND and OR protocols, respectively, as in the shuffle-based protocols. These protocols have an advantage of requiring only one private permutation and one communication. We further show that the number of cards of these protocols can be reduced at the cost of increasing the number of private permutations and communications.
Private set intersection (PSI) is a cryptographic primitive that allows two or more parties to learn the intersection of their input sets and nothing else. In this paper, we introduce a new secure multi-party quantum computation for the greatest common divisor (GCD) and a PSI protocol based on it. The protocol extends the recent least common multiple (LCM)-based quantum private set union protocol by Liu et al. Performance analysis verifies the correctness and demonstrates the entire security of the suggested protocols in the semi-honest model. Additionally, it has been demonstrated that the complexity is efficient in terms of the input set size.
In this paper we focus on protocols for private set intersection (PSI), through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage.In the unconditional setting we evidence that PSI is impossible to realize and that unconditionally secure size-hiding PSI is possible assuming a set-up authority is present in an set up phase. In the computational setting we give a generic construction using smooth projective hash functions for languages derived from perfectly-binding commitments. Further, we give two size-hiding constructions: the first one is theoretical and evidences the equivalence between PSI, oblivious transfer and the secure computation of the AND function. The second one is a twist on the oblivious polynomial evaluation construction of Freedman et al. from EUROCRYPT 2004. We further sketch a generalization of the latter using algebraic-geometric techniques. Finally, assuming again there is a set-up authority (yet not necessarily trusted) we present very simple and efficient constructions that only hide the size of the client's set.