ABSTRACT Disease surveillance is vital for public health security, allowing early outbreak detection, reducing transmission, safeguarding population health, and aiding emergency response. This paper proposes a quantum disease surveillance algorithm based on private set intersection (PSI). Specifically, we use the BHT algorithm to solve the PSI problem and improve computational efficiency through candidate subset preprocessing and quantum parallel search mechanisms. It achieves a polynomial speedup over previous algorithms by reducing the communication complexity from to and optimizing the round complexity to a constant, thereby substantially reducing the data transmission overhead. Simulation experiments on the IBM quantum platform verify the correctness and feasibility of our algorithm. Security analysis shows that our algorithm effectively resists both insider and outsider attacks while satisfying privacy‐preservation requirements in disease surveillance scenarios, specifically protecting the privacy of individual clients and the server.
ABSTRACT Disease surveillance is vital for public health security, allowing early outbreak detection, reducing transmission, safeguarding population health, and aiding emergency response. This paper proposes a quantum disease surveillance algorithm based on private set intersection (PSI). Specifically, we use the BHT algorithm to solve the PSI problem and improve computational efficiency through candidate subset preprocessing and quantum parallel search mechanisms. It achieves a polynomial speedup over previous algorithms by reducing the communication complexity from to and optimizing the round complexity to a constant, thereby substantially reducing the data transmission overhead. Simulation experiments on the IBM quantum platform verify the correctness and feasibility of our algorithm. Security analysis shows that our algorithm effectively resists both insider and outsider attacks while satisfying privacy‐preservation requirements in disease surveillance scenarios, specifically protecting the privacy of individual clients and the server.
The healthcare pandemic (for instance, the recently ongoing Coronavirus disease (COVID-19) pandemic) presented a challenge for researchers to find novel techniques to limit the transmission of the virus. In this context, contact tracing has emerged as an important method to curb the spread of disease. Although it can help combat disease outbreaks, if the contact tracing is executed without careful consideration then it could jeopardize the users’ privacy. The cryptographic technique, private set intersection (PSI) appears to be a logical solution. However, many existing PSI protocols rely on the security of number theory based problems, which are vulnerable in the quantum domain. Therefore, to address this issue we present a PSI protocol (namely qPSI) based on quantum cryptography. The communication and computational costs of existing schemes depend on the universal set size N. In comparison, qPSI requires computational and communication costs, which are independent of the universal set size N. Moreover, the existing Bloom filter based quantum PSI does not provide the exact intersection due to high false positive rate of the Bloom filter of server’s private set, whereas qPSI is not affected by the false positive rate and provides the exact set intersection. In addition, quantum PSI protocols use multi-particle entangled state or N single photons, and complicated oracle operators in N-dimensional Hilbert space. On the other hand, qPSI only utilizes single-photon quantum resources and projective measurements operations over a 2-dimensional Hilbert space. Therefore, qPSI is simple and efficient when compared to other existing PSI protocols in the state-of-the-art.
Private Set Intersection Cardinality (PSI-CA) is one of the most concerned issues with the protection of privacy, in which two parties jointly compute the intersection cardinality without revealing their respective private sets. There are important applications of PSI-CA in real society, e.g., strongly privacy-preserving data statistics in contact tracing for health authorities to fight the outbreaks of highly contagious diseases. In this paper, we present a novel quantum PSI-CA protocol, in which we adopt oblivious quantum key distribution, secure quantum summation and quantum counting algorithm. The proposed PSI-CA protocol not only ensures the approximatively perfect security but also achieves the linear communication complexity, i.e.,O(N). Furthermore, we define a new privacy protection problem, i.e., Privacy-preserving Condition Query (PCQ), and provide an efficient solution to the PCQ problem based on the proposed quantum PSI-CA protocol. Finally, we verify the correctness and the feasibility of the proposed quantum PSI-CA protocol by circuit simulations in IBM Qiskit.
Abstract 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.
Recently, we proposed a quantum solution to the problem of private set intersection cardinality (PSI-CA) (Information Sciences 370–371 (2016) 147–158). Compared to classical solutions, the proposed quantum PSI-CA protocol achieves an exponential reduction in communication complexity, since it only needsO(1)communication cost. However, this protocol requires two additional assumptions about the cardinalities of the sets, which may limit its wider applications. In this paper, we successfully discard these assumptions and present a stronger quantum PSI-CA protocol without any limitation. The new protocol ensures the parties’ private security, i.e., unconditionally secure server privacy and statistically secure client privacy, and it achieves the constant computation and communication complexities, which are independent of the size of the sets. Therefore, it is more suitable for practical applications with big data sets.
Private set intersection is an important problem with implications in many areas, ranging from remote diagnostics to private contact discovery. In this work, we consider the case of two-party PSI in the honest-but-curious setting. We propose a protocol that solves the server-aided PSI problem using delegated blind quantum computing. More specifically, the proposed protocol allows Alice and Bob (who do not have any quantum computational resources or quantum memory) to interact with Steve (who has a quantum computer) in order for Alice and Bob to obtain set intersection such that privacy is preserved. In particular, Steve learns nothing about the clients' input, output, or desired computation. The proposed protocol is correct, secure and blind against a malicious server, and characterized by a quantum communication complexity that is linear in the input size.
Private Set Intersection Cardinality that enable Multi-party to privately compute the cardinality of the set intersection without disclosing their own information. It is equivalent to a secure, distributed database query and has many practical applications in privacy preserving and data sharing. In this paper, we propose a novel quantum private set intersection cardinality based on Bloom filter, which can resist the quantum attack. It is a completely novel constructive protocol for computing the intersection cardinality by using Bloom filter. The protocol uses single photons, so it only need to do some simple single-photon operations and tests. Thus it is more likely to realize through the present technologies. The validity of the protocol is verified by comparing with other protocols. The protocol implements privacy protection without increasing the computational complexity and communication complexity, which are independent with data scale. Therefore, the protocol has a good prospects in dealing with big data, privacy-protection and information-sharing, such as the patient contact for COVID-19.