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

Advances in Mathematics of Communications

Private set intersection: New generic constructions and feasibility results

Paolo D’Arco, María Isabel González Vasco, Ángel Luis Pérez del Pozo, Claudio Soriente, Rainer Steinwandt

Published Jan 1, 2017• 3 citations
Publisher

Abstract

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.

DOI
10.3934/amc.2017040

Related papers

Amortizing Circuit-PSI in the Multiple Sender/Receiver Setting

Aron van Baarsen, Marc Stevens

Private set intersection (PSI) is a cryptographic functionality for two parties to learn the intersection of their input sets, without leaking any other information. Circuit-PSI is a stronger PSI functionality where the parties learn only a secret-shared form of the desired intersection, thus without revealing the intersection directly. These secret shares can subsequently serve as input to a secure multiparty computation of any function on this intersection. In this paper we consider several settings in which parties take part in multiple Circuit-PSI executions with the same input set, and aim to amortize communications and computations. To that end, we build up a new framework for Circuit-PSI around generalizations of oblivious (programmable) PRFs that are extended with offline setup phases. We present several efficient instantiations of this framework with new security proofs for this setting. As a side result, we obtain a slight improvement in communication and computation complexity over the state-of-the-art semi-honest Circuit-PSI protocol by Bienstock et al. (USENIX '23). Additionally, we present a novel Circuit-PSI protocol from a PRF with secret-shared outputs, which has linear communication and computation complexity in the parties' input set sizes, and is able to realize a stronger security notion. Lastly, we derive the potential amortizations over multiple protocol executions, and observe that each of the presented instantiations is favorable in at least one of the multiple-execution settings.

IACR Communications in Cryptology•Oct 7, 2024•5 citations

Private Set Intersection Using a Binary Erasure Channel

Amirhossein Shekofteh, Rémi A. Chou

We consider a Private Set Intersection (PSI) problem, where a server holds an arbitrary number of private subsets and a client holds a private subset of size K over a universe of size N. The client wants to compute the intersection of its set with each private subset of the server, learning only these intersections, while the server learns nothing about the client’s private set. The server controls the input of a binary erasure channel (BEC) with parameter ϵ, whose output is observed by the client, and both client and server can communicate over a noiseless channel. We define the PSI rate as the ratio of the number of server subsets to the number of BEC uses and characterize the information-theoretic PSI capacity as ${C_{{\text{PSI}}}} = \min \left( {\frac{\varepsilon }{{N - K}},\frac{{1 - \varepsilon }}{K}} \right)$. Our result is obtained by reducing the PSI problem to a K-out-of-N oblivious transfer problem and proving that this reduction is optimal.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

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

Updatable Private Set Intersection with Low Communication Overhead

Chao Qi, Mingmei Zheng, Aoxiang Xu +3 more

Private set intersection (PSI) is a fundamental cryptographic task that allows two mutually distrusting parties, each holding a private set of elements, to jointly compute the intersection of their sets. It ensures a symmetric information structure where neither party gains any knowledge about the other’s elements beyond those in the shared intersection. Traditional PSI protocols are primarily designed for static settings, which limits their applicability and efficiency in dynamic scenarios where input sets continuously evolve. To address this challenge, the notion of updatable PSI (UPSI) was introduced, enabling repeated PSI computations over changing inputs while preserving the symmetric privacy guarantees between participants. Despite the numerous recent advancements in UPSI research, it still suffers from significant communication overhead. In this paper, we address this challenge by introducing LcUPSI (low-communication UPSI), a new updatable PSI protocol that achieves remarkably low communication overhead. We formally prove that LcUPSI is secure in the semi-honest model. Furthermore, we compare the LcUPSI protocol with the state-of-the-art UPSI protocol BMSTZ24 (ASIACRYPT). The results demonstrate that LcUPSI significantly reduces communication overhead, highlighting its advantages in low-bandwidth conditions.

Symmetry•Apr 12, 2026•0 citations

Efficient post-quantum private set-intersection protocol

Nibedita Kundu, Tanmay Choudhury, Sumit Kumar Debnath

Private set intersection (PSI) is a cryptographic protocol that enables two parties to securely determine the intersection of their private datasets without revealing anything except the intersection. Most of the existing PSI protocols are based on traditional number theoretic problems, such as discrete logarithm problem and factorisation problem. Unfortunately, these protocols would be broken if efficient quantum computer emerges. The post-quantum PSI is an important alternative to traditional PSI protocols for its potential to resist future attacks of quantum computers. In this work, we present first post-quantum PSI protocol that achieves size-hiding property. Space-efficient probabilistic data structure Bloom filter along with lattice-based public key encryption are used as building blocks of our construction. It attains linear complexity and security in standard model under the decisional learning with errors (DLWE) assumption. Moreover, we extend our post-quantum PSI to its authorised variant APSI retaining all the properties.

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

Hiding the Input-Size in Secure Two-Party Computation.

Yehuda Lindell, Kobbi Nissim B, Claudio Orlandi

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their inputs, while preserving properties like privacy, correctness, and independence of inputs. One security property that has typically not been considered in the past relates to the length or size of the parties inputs. This is despite the fact that in many cases the size of a party’s input can be confidential. The reason for this omission seems to have been the folklore belief that, as with encryption, it is impossible to carry out non-trivial secure computation while hiding the size of parties ’ inputs. However some recent results (e.g., Ishai and Paskin at TCC 2007, Ateniese, De Cristofaro and Tsudik at PKC 2011) showed that it is possible to hide the input size of one of the parties for some limited class of functions, including secure two-party set intersection. This suggests that the folklore belief may not be fully accurate. In this work, we initiate a theoretical study of input-size hiding secure computation, and focus on the two-party case. We present definitions for this task, and deal with the subtleties that arise in the setting where there is no a priori polynomial bound on the parties ’ input sizes. Our definitional study yields a multitude of classes of input-size hiding computation, depending

•Jan 1, 2012•2 citations
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.
Private set intersection (PSI) is a cryptographic functionality for two parties to learn the intersection of their input sets, without leaking any other information. Circuit-PSI is a stronger PSI functionality where the parties learn only a secret-shared form of the desired intersection, thus without revealing the intersection directly. These secret shares can subsequently serve as input to a secure multiparty computation of any function on this intersection. In this paper we consider several settings in which parties take part in multiple Circuit-PSI executions with the same input set, and aim to amortize communications and computations. To that end, we build up a new framework for Circuit-PSI around generalizations of oblivious (programmable) PRFs that are extended with offline setup phases. We present several efficient instantiations of this framework with new security proofs for this setting. As a side result, we obtain a slight improvement in communication and computation complexity over the state-of-the-art semi-honest Circuit-PSI protocol by Bienstock et al. (USENIX '23). Additionally, we present a novel Circuit-PSI protocol from a PRF with secret-shared outputs, which has linear communication and computation complexity in the parties' input set sizes, and is able to realize a stronger security notion. Lastly, we derive the potential amortizations over multiple protocol executions, and observe that each of the presented instantiations is favorable in at least one of the multiple-execution settings.
We consider a Private Set Intersection (PSI) problem, where a server holds an arbitrary number of private subsets and a client holds a private subset of size K over a universe of size N. The client wants to compute the intersection of its set with each private subset of the server, learning only these intersections, while the server learns nothing about the client’s private set. The server controls the input of a binary erasure channel (BEC) with parameter ϵ, whose output is observed by the client, and both client and server can communicate over a noiseless channel. We define the PSI rate as the ratio of the number of server subsets to the number of BEC uses and characterize the information-theoretic PSI capacity as CPSI=min⁡(εN−K,1−εK){C_{{\text{PSI}}}} = \min \left( {\frac{\varepsilon }{{N - K}},\frac{{1 - \varepsilon }}{K}} \right)CPSI​=min(N−Kε​,K1−ε​). Our result is obtained by reducing the PSI problem to a K-out-of-N oblivious transfer problem and proving that this reduction is optimal.
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.
Private set intersection (PSI) is a fundamental cryptographic task that allows two mutually distrusting parties, each holding a private set of elements, to jointly compute the intersection of their sets. It ensures a symmetric information structure where neither party gains any knowledge about the other’s elements beyond those in the shared intersection. Traditional PSI protocols are primarily designed for static settings, which limits their applicability and efficiency in dynamic scenarios where input sets continuously evolve. To address this challenge, the notion of updatable PSI (UPSI) was introduced, enabling repeated PSI computations over changing inputs while preserving the symmetric privacy guarantees between participants. Despite the numerous recent advancements in UPSI research, it still suffers from significant communication overhead. In this paper, we address this challenge by introducing LcUPSI (low-communication UPSI), a new updatable PSI protocol that achieves remarkably low communication overhead. We formally prove that LcUPSI is secure in the semi-honest model. Furthermore, we compare the LcUPSI protocol with the state-of-the-art UPSI protocol BMSTZ24 (ASIACRYPT). The results demonstrate that LcUPSI significantly reduces communication overhead, highlighting its advantages in low-bandwidth conditions.
Private set intersection (PSI) is a cryptographic protocol that enables two parties to securely determine the intersection of their private datasets without revealing anything except the intersection. Most of the existing PSI protocols are based on traditional number theoretic problems, such as discrete logarithm problem and factorisation problem. Unfortunately, these protocols would be broken if efficient quantum computer emerges. The post-quantum PSI is an important alternative to traditional PSI protocols for its potential to resist future attacks of quantum computers. In this work, we present first post-quantum PSI protocol that achieves size-hiding property. Space-efficient probabilistic data structure Bloom filter along with lattice-based public key encryption are used as building blocks of our construction. It attains linear complexity and security in standard model under the decisional learning with errors (DLWE) assumption. Moreover, we extend our post-quantum PSI to its authorised variant APSI retaining all the properties.
In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their inputs, while preserving properties like privacy, correctness, and independence of inputs. One security property that has typically not been considered in the past relates to the length or size of the parties inputs. This is despite the fact that in many cases the size of a party’s input can be confidential. The reason for this omission seems to have been the folklore belief that, as with encryption, it is impossible to carry out non-trivial secure computation while hiding the size of parties ’ inputs. However some recent results (e.g., Ishai and Paskin at TCC 2007, Ateniese, De Cristofaro and Tsudik at PKC 2011) showed that it is possible to hide the input size of one of the parties for some limited class of functions, including secure two-party set intersection. This suggests that the folklore belief may not be fully accurate. In this work, we initiate a theoretical study of input-size hiding secure computation, and focus on the two-party case. We present definitions for this task, and deal with the subtleties that arise in the setting where there is no a priori polynomial bound on the parties ’ input sizes. Our definitional study yields a multitude of classes of input-size hiding computation, depending