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

Electronics

Securely Computing Protocol of Set Intersection under the Malicious Model

Xin Liu, Weitong Chen, Naixue N. Xiong, Dan Luo, Gang Xu, Xiu‐Bo Chen

Published May 26, 2023• 1 citation
Publisher

Abstract

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.

DOI
10.3390/electronics12112410

Related papers

Secure Judgment of Point and Line Relationship Against Malicious Adversaries and Its Applications

Xin Liu Xin Liu, Yang Xu Xin Liu, Gang Xu Yang Xu +2 more

With the rapid development of the Internet and information technology, the problem of zero-trust networks has become increasingly prominent, and secure multi-party computation has become a research hotspot to solve the problem of zero-trust networks. The secure judgment of point and line relationship is an important research branch of secure computing set geometry. However, most of resent secure computing protocols of point and line relationship are designed in the semi-honest model and cannot resist malicious attacks. Therefore, this paper analyzes the possible malicious adversary behaviors and designs a secure protocol in the malicious model. In this paper, the Paillier cryptosystem, zero- knowledge proof, and cut-choose method are used to resist malicious behavior, and the real/ideal model paradigm method is used to prove the security of the protocol. Compared with the existing solutions, the malicious model protocol is still efficient and widely used in real applications.

網際網路技術學刊•Sep 1, 2022•4 citations

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

Quantum private set intersection based on single qubits

Cai Zhang, Zhuoxuan Zhan, Zhiwei Sun

Private Set Intersection (PSI) is a crucial Secure Multi-Party Computation (SMPC) primitive which enables participants to securely obtain the intersection of their private sets without revealing their individual set information. The advent of quantum computing threatens classical PSI protocols, driving the development of Quantum PSI (QPSI) alternatives. We propose a two-party QPSI protocol based on a semi-honest third party. This protocol achieves set intersection using only single-qubit unitary operations and single-qubit states. Security analysis shows that our protocol can resist common attacks. Validation experiments conducted on the IBM Qiskit simulator confirm the protocol’s correctness and feasibility. Furthermore, we compare the proposed protocol with existing QPSI protocols in terms of quantum states, unitary operations, measurements, and fairness, demonstrating gains in quantum resource efficiency, fairness, and practical feasibility.

EPJ Quantum Technology•Oct 20, 2026•0 citations

Towards fair mutual private set intersection with linear complexity

Sumit Kumar Debnath, Ratna Dutta

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.

Security and Communication Networks•Mar 6, 2016•12 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

Efficient quantum secure multi-party greatest common divisor protocol and its applications in private set operations

Zixian Li, Wenjie Liu, Bing-Mei Su

Private set intersection (PSI) has important application value, however, current quantum PSI protocols are either unsuitable for multi-party scenarios or inefficient. Recently, Imran (arXiv: 2303.17196v3 , 2023) proposed two quantum secure multi-party greatest common divisor (GCD) protocols that can be used for PSI, but with the downside of information leakage and resource consumption. In this paper, we propose a novel quantum secure multi-party GCD protocol that has higher security and lower complexity. To hide privacy, each party randomly selects a coefficient within a range determined by his input integer, and with the assistance of a semi-honest third party TP, all parties secretly calculate the linear combination of their inputs under these coefficients. Once enough linear combinations are collected, TP calculates the GCD of these combinations, which is equal to the GCD of all input integers. To verify the honesty of participants, a quantum zero-knowledge proof sub-protocol is designed. Analysis shows that our GCD protocol is correct and has security against malicious attacks. Moreover, its complexity is polynomial level and lower than Imran’s. Furthermore, we demonstrate the scalability of our GCD protocol in private set operations, such as private set intersection, private set intersection cardinality, private multi-set intersection, etc.

EPJ Quantum Technology•Sep 9, 2024•7 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.
With the rapid development of the Internet and information technology, the problem of zero-trust networks has become increasingly prominent, and secure multi-party computation has become a research hotspot to solve the problem of zero-trust networks. The secure judgment of point and line relationship is an important research branch of secure computing set geometry. However, most of resent secure computing protocols of point and line relationship are designed in the semi-honest model and cannot resist malicious attacks. Therefore, this paper analyzes the possible malicious adversary behaviors and designs a secure protocol in the malicious model. In this paper, the Paillier cryptosystem, zero- knowledge proof, and cut-choose method are used to resist malicious behavior, and the real/ideal model paradigm method is used to prove the security of the protocol. Compared with the existing solutions, the malicious model protocol is still efficient and widely used in real applications.
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 crucial Secure Multi-Party Computation (SMPC) primitive which enables participants to securely obtain the intersection of their private sets without revealing their individual set information. The advent of quantum computing threatens classical PSI protocols, driving the development of Quantum PSI (QPSI) alternatives. We propose a two-party QPSI protocol based on a semi-honest third party. This protocol achieves set intersection using only single-qubit unitary operations and single-qubit states. Security analysis shows that our protocol can resist common attacks. Validation experiments conducted on the IBM Qiskit simulator confirm the protocol’s correctness and feasibility. Furthermore, we compare the proposed protocol with existing QPSI protocols in terms of quantum states, unitary operations, measurements, and fairness, demonstrating gains in quantum resource efficiency, fairness, and practical feasibility.
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.
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.
Private set intersection (PSI) has important application value, however, current quantum PSI protocols are either unsuitable for multi-party scenarios or inefficient. Recently, Imran (arXiv: 2303.17196v3 , 2023) proposed two quantum secure multi-party greatest common divisor (GCD) protocols that can be used for PSI, but with the downside of information leakage and resource consumption. In this paper, we propose a novel quantum secure multi-party GCD protocol that has higher security and lower complexity. To hide privacy, each party randomly selects a coefficient within a range determined by his input integer, and with the assistance of a semi-honest third party TP, all parties secretly calculate the linear combination of their inputs under these coefficients. Once enough linear combinations are collected, TP calculates the GCD of these combinations, which is equal to the GCD of all input integers. To verify the honesty of participants, a quantum zero-knowledge proof sub-protocol is designed. Analysis shows that our GCD protocol is correct and has security against malicious attacks. Moreover, its complexity is polynomial level and lower than Imran’s. Furthermore, we demonstrate the scalability of our GCD protocol in private set operations, such as private set intersection, private set intersection cardinality, private multi-set intersection, etc.