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

Security and Communication Networks

Towards fair mutual private set intersection with linear complexity

Sumit Kumar Debnath, Ratna Dutta

Published Mar 6, 2016• 12 citations
Publisher

Abstract

Abstract In this paper, we propose a two‐way oblivious pseudorandom function (mOPRF) secure in standard model against malicious parties under the decisional composite residuosity and decisional Diffie–Hellman assumptions. Using this two‐way OPRF, we construct an optimistic mutual private set intersection (PSI) protocol conserving fairness. In our PSI protocol, fairness is obtained by a semi‐trusted arbiter in the sense that it cannot get access to the private information of the two parties, but we believe that it will follow the protocol. To the best of our knowledge, our PSI protocol is the first fair PSI with linear communication and computation complexities and is proven to be secure in standard model against malicious adversaries under decisional q‐Diffie–Hellman inversion, decisional composite residuosity, and decisional Diffie–Hellman assumptions. Apart from that, we present a modified version of the OPRF that requires less number of communication rounds. Copyright © 2016 John Wiley & Sons, Ltd.

DOI
10.1002/sec.1450

Related papers

Optimistic Fair Secure Computation (Extended Abstract)

Christian Cachin, Jan L. Camenisch

Abstract. We present an efficient and fair protocol for secure two-party computation in the optimistic model, where a partially trusted third party T is available, but not involved in normal protocol executions. T is needed only if communication is disrupted or if one of the two parties misbehaves. The protocol guarantees that although one party may terminate the protocol at any time, the computation remains fair for the other party. Communication is over an asynchronous network. All our protocols are based on efficient proofs of knowledge and involve no general zero-knowledge tools. As intermediate steps we describe efficient verifiable oblivious transfer and verifiable secure function evaluation protocols, whose security is proved under the decisional Diffie-Hellman assumption. 1

•Jan 1, 2000•7 citations

Compact and Malicious Private Set Intersection for Small Sets

Mike Rosulek, Ni Trieu

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.

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

Post‐quantum protocol for computing set intersection cardinality with linear complexity

Sumit Kumar Debnath, Pantelimon Stănică, Tanmay Choudhury +1 more

Nowadays, the necessity of electronic information increases rapidly. As a consequence, often, that information needs to be shared among mutually distrustful parties. In this area, private set intersection (PSI) and its variants play an important role when the participants wish to do secret operations on their input sets. Unlike the most modern public key cryptosystems relying on number theoretic problems, lattice‐based cryptographic constructions provide security in the presence of a quantum computer. Consequently, developing PSI and its variants using lattice based cryptosystem becomes an interesting direction for research. This study presents the first size‐hiding post quantum PSI cardinality (PSI‐CA) protocol whose complexity is linear in the size of the sets of the participants. The authors use space‐efficient probabilistic data structure (Bloom filter) as its building block. Further, they extend the authors’ PSI‐CA to its authorised version, i.e. authorised PSI‐CA. Security for both of them is achieved in the standard model based on the hardness of the decisional learning with errors problem.

IET Information Security•Jun 11, 2020•8 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

Identity‐based optimistic fair exchange in the standard model

Lei Zhang, Qianhong Wu, Bo Qin

ABSTRACT A fair exchange protocol allows two entities to exchange digital signatures over open networks in a fair way, so that either each entity obtains the other's signature or neither entity does. Fair exchange protocol plays an important role in electronic commerce in the case of exchanging digital contracts. In this paper, we propose a fair exchange protocol based on identity‐based verifiably encrypted signatures. Our protocol involves an offline trusted third party which is only required when one entity attempts to cheat or crashes. The underlining identity‐based verifiably encrypted signature scheme is proven secure under the computational Diffie–Hellman assumption and is the first identity‐based verifiably encrypted signature scheme provably secure against existential unforgeable under adaptive chosen message and identity attacks in the standard model. Copyright © 2012 John Wiley & Sons, Ltd.

Security and Communication Networks•Nov 26, 2012•10 citations

A Signal‐Matching Approach to RLWE‐Based PSI: Achieving Optimal Online Efficiency in 3 Rounds

Yue Qin, Bei Liang, Hongyuan Cai +2 more

In this study, we propose a novel post‐quantum private set intersection (PSI) protocol based on the ring learning with errors (RLWE) assumption. Different from existing PSI protocols based on post‐quantum oblivious pseudorandom functions (EUROCRYPT’25) and fully homomorphic encryption (FHE) (CCS’21), our construction follows the Diffie–Hellman (DH)‐based PSI paradigm and uses post‐quantum key exchange to achieve PSI functionality. Our key technique is a signal matching (SigMa) mechanism, which determines whether two items match by checking the consistency of the reconciliation signals derived from their corresponding shared keys. The resulting PSI protocol completes in three rounds. In the first two rounds, the parties exchange RLWE‐based public keys associated with their items; in the third round, the sender transmits the corresponding signals. The receiver then applies SigMa to compare the received signals with its locally computed signals and thereby identify the intersection. We implement our protocol and compare it with Cong et al. (CCS’21) and Heimberger et al. (EUROCRYPT’25). Our protocol achieves the lowest online communication across all evaluated symmetric and asymmetric set‐size configurations, at the cost of additional offline communication. It also achieves the lowest online and total times among the evaluated protocols for all symmetric settings with | X | = | Y | ∈ {2 12 , 2 16 , 2 20 } and all asymmetric settings with | X | ∈ {2 12 , 2 16 , 2 20 } and | Y | ∈ {5535, 11041}. We believe that our work not only supplements existing post‐quantum PSI frameworks but also opens the opportunity for broader applications of post‐quantum PSI.

IET Information Security•Jan 1, 2026•0 citations
Abstract In this paper, we propose a two‐way oblivious pseudorandom function (mOPRF) secure in standard model against malicious parties under the decisional composite residuosity and decisional Diffie–Hellman assumptions. Using this two‐way OPRF, we construct an optimistic mutual private set intersection (PSI) protocol conserving fairness. In our PSI protocol, fairness is obtained by a semi‐trusted arbiter in the sense that it cannot get access to the private information of the two parties, but we believe that it will follow the protocol. To the best of our knowledge, our PSI protocol is the first fair PSI with linear communication and computation complexities and is proven to be secure in standard model against malicious adversaries under decisional q‐Diffie–Hellman inversion, decisional composite residuosity, and decisional Diffie–Hellman assumptions. Apart from that, we present a modified version of the OPRF that requires less number of communication rounds. Copyright © 2016 John Wiley & Sons, Ltd.
Abstract. We present an efficient and fair protocol for secure two-party computation in the optimistic model, where a partially trusted third party T is available, but not involved in normal protocol executions. T is needed only if communication is disrupted or if one of the two parties misbehaves. The protocol guarantees that although one party may terminate the protocol at any time, the computation remains fair for the other party. Communication is over an asynchronous network. All our protocols are based on efficient proofs of knowledge and involve no general zero-knowledge tools. As intermediate steps we describe efficient verifiable oblivious transfer and verifiable secure function evaluation protocols, whose security is proved under the decisional Diffie-Hellman assumption. 1
Nowadays, the necessity of electronic information increases rapidly. As a consequence, often, that information needs to be shared among mutually distrustful parties. In this area, private set intersection (PSI) and its variants play an important role when the participants wish to do secret operations on their input sets. Unlike the most modern public key cryptosystems relying on number theoretic problems, lattice‐based cryptographic constructions provide security in the presence of a quantum computer. Consequently, developing PSI and its variants using lattice based cryptosystem becomes an interesting direction for research. This study presents the first size‐hiding post quantum PSI cardinality (PSI‐CA) protocol whose complexity is linear in the size of the sets of the participants. The authors use space‐efficient probabilistic data structure (Bloom filter) as its building block. Further, they extend the authors’ PSI‐CA to its authorised version, i.e. authorised PSI‐CA. Security for both of them is achieved in the standard model based on the hardness of the decisional learning with errors problem.
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.
ABSTRACT A fair exchange protocol allows two entities to exchange digital signatures over open networks in a fair way, so that either each entity obtains the other's signature or neither entity does. Fair exchange protocol plays an important role in electronic commerce in the case of exchanging digital contracts. In this paper, we propose a fair exchange protocol based on identity‐based verifiably encrypted signatures. Our protocol involves an offline trusted third party which is only required when one entity attempts to cheat or crashes. The underlining identity‐based verifiably encrypted signature scheme is proven secure under the computational Diffie–Hellman assumption and is the first identity‐based verifiably encrypted signature scheme provably secure against existential unforgeable under adaptive chosen message and identity attacks in the standard model. Copyright © 2012 John Wiley & Sons, Ltd.
In this study, we propose a novel post‐quantum private set intersection (PSI) protocol based on the ring learning with errors (RLWE) assumption. Different from existing PSI protocols based on post‐quantum oblivious pseudorandom functions (EUROCRYPT’25) and fully homomorphic encryption (FHE) (CCS’21), our construction follows the Diffie–Hellman (DH)‐based PSI paradigm and uses post‐quantum key exchange to achieve PSI functionality. Our key technique is a signal matching (SigMa) mechanism, which determines whether two items match by checking the consistency of the reconciliation signals derived from their corresponding shared keys. The resulting PSI protocol completes in three rounds. In the first two rounds, the parties exchange RLWE‐based public keys associated with their items; in the third round, the sender transmits the corresponding signals. The receiver then applies SigMa to compare the received signals with its locally computed signals and thereby identify the intersection. We implement our protocol and compare it with Cong et al. (CCS’21) and Heimberger et al. (EUROCRYPT’25). Our protocol achieves the lowest online communication across all evaluated symmetric and asymmetric set‐size configurations, at the cost of additional offline communication. It also achieves the lowest online and total times among the evaluated protocols for all symmetric settings with | X | = | Y | ∈ {2 12 , 2 16 , 2 20 } and all asymmetric settings with | X | ∈ {2 12 , 2 16 , 2 20 } and | Y | ∈ {5535, 11041}. We believe that our work not only supplements existing post‐quantum PSI frameworks but also opens the opportunity for broader applications of post‐quantum PSI.