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

International Journal of Modern Physics B

Fault-tolerant symmetrically-private information retrieval

Tian‐Yin Wang, Xiao‐Qiu Cai, Ruiling Zhang

Published Aug 15, 2016• 0 citations
Publisher

Abstract

We propose two symmetrically-private information retrieval protocols based on quantum key distribution, which provide a good degree of database and user privacy while being flexible, loss-resistant and easily generalized to a large database similar to the precedent works. Furthermore, one protocol is robust to a collective-dephasing noise, and the other is robust to a collective-rotation noise.

DOI
10.1142/s0217979216501782

Related papers

Towards communication-efficient quantum oblivious key distribution

M. V. Panduranga Rao, Markus Jakobi

Symmetrically private information retrieval, a fundamental problem in the field of secure multiparty computation, is defined as follows: A database $D$ of $N$ bits held by Bob is queried by a user Alice who is interested in the bit ${D}_{b}$ in such a way that (1) Alice learns ${D}_{b}$ and only ${D}_{b}$ and (2) Bob does not learn anything about Alice's choice $b$. While solutions to this problem in the classical domain rely largely on unproven computational complexity theoretic assumptions, it is also known that perfect solutions that guarantee both database and user privacy are impossible in the quantum domain. Jakobi et al. [Phys. Rev. A 83, 022301 (2011)] proposed a protocol for oblivious transfer using well-known quantum key device (QKD) techniques to establish an oblivious key to solve this problem. Their solution provided a good degree of database and user privacy (using physical principles like the impossibility of perfectly distinguishing nonorthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of the Scarani-Acin-Ribordy-Gisin 2004 protocol). However, their quantum oblivious key distribution (QOKD) protocol requires a communication complexity of $O(N\mathrm{log}N)$. Since modern databases can be extremely large, it is important to reduce this communication as much as possible. In this paper, we first suggest a modification of their protocol wherein the number of qubits that need to be exchanged is reduced to $O(N)$. A subsequent generalization reduces the quantum communication complexity even further in such a way that only a few hundred qubits are needed to be transferred even for very large databases.

arXiv:1208.2501•Physical Review A•Jan 28, 2013•63 citations

Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography

Wen Yu Kon, Charles Ci Wen Lim

Private information retrieval (PIR) is a database query protocol that provides user privacy in that the user can learn a particular entry of the database of his interest but his query would be hidden from the data centre. Symmetric private information retrieval (SPIR) takes PIR further by additionally offering database privacy, where the user cannot learn any additional entries of the database. Unconditionally secure SPIR solutions with multiple databases are known classically, but are unrealistic because they require long shared secret keys between the parties for secure communication and shared randomness in the protocol. Here, we propose using quantum key distribution (QKD) instead for a practical implementation, which can realise both the secure communication and shared randomness requirements. We prove that QKD maintains the security of the SPIR protocol and that it is also secure against any external eavesdropper. We also show how such a classical-quantum system could be implemented practically, using the example of a two-database SPIR protocol with keys generated by measurement device-independent QKD. Through key rate calculations, we show that such an implementation is feasible at the metropolitan level with current QKD technology.

arXiv:2004.13921•Entropy•Dec 31, 2020•25 citations

Symmetric private information retrieval supported by quantum-secure key-exchange network

Shuang Wang

Quantum key distribution provides a provably secure way for private key distribution, which enables the practical implementation of information retrieval that preserves both the user privacy and database security.

Light Science & Applications•Oct 14, 2022•9 citations

Performing private database queries in a real-world environment using a quantum protocol

Philip Chan, I. Lucio-Martinez, Xiaofan Mo +2 more

Private query protocols [1-3] use uncertainty in quantum mechanics to offer functionality similar to 1-out-of-N oblivious transfer (where a user, Ursula, retrieves a single element from a database provider, Dave, who learns nothing about which of the N elements was retrieved). The difference in functionality varies for each private query protocol, but in all cases is motivated by the fact that perfect 1-out-of-N oblivious transfer has been shown to be impossible if the attacker possess an arbitrarily powerful quantum computer [4]. Nonetheless, quantum protocols can offer security against stronger adversaries than protocols relying only on classical information, and it remains an interesting question as to what level of security can be achieved using quantum information. We present a proof-of-principle demonstration of a novel private query protocol that is loss- and fault-tolerant, making it suitable for implementation in a real-world environment, and show that it offers excellent privacy against several quantum attacks [5]. This demonstration is performed over a deployed fibre link between the University of Calgary and SAIT Polytechnic using a slightly modified quantum key distribution (QKD) system [6]. Oblivious transfer (OT) is a well studied primitive in classical information theory, and protocols

•Jan 8, 2014•43 citations

Secure quantum private information retrieval using phase-encoded queries

Łukasz Olejnik

We propose a quantum solution to the classical private information retrieval (PIR) problem, which allows one to query a database in a private manner. The protocol offers privacy thresholds and allows the user to obtain information from a database in a way that offers the potential adversary, in this model the database owner, no possibility of deterministically establishing the query contents. This protocol may also be viewed as a solution to the symmetrically private information retrieval problem in that it can offer database security (inability for a querying user to steal its contents). Compared to classical solutions, the protocol offers substantial improvement in terms of communication complexity. In comparison with the recent quantum private queries [Phys. Rev. Lett. 100, 230502 (2008)] protocol, it is more efficient in terms of communication complexity and the number of rounds, while offering a clear privacy parameter. We discuss the security of the protocol and analyze its strengths and conclude that using this technique makes it challenging to obtain the unconditional (in the information-theoretic sense) privacy degree; nevertheless, in addition to being simple, the protocol still offers a privacy level. The oracle used in the protocol is inspired both by the classical computational PIR solutions as well as the Deutsch-Jozsa oracle.

Physical Review A•Aug 8, 2011•125 citations

Symmetrically Private Information Retrieval (Extended Abstract)

Sanjeev Kumar Mishra, Palash Sarkar

Abstract. In this paper we present a single-round, single-server symmetrically private information retrieval scheme, in which privacy of user follows from intractability of the quadratic residuacity problem and the privacy of the database follows from the XOR assumption for quadratic residues introduced in this paper. The communication complexity of the proposed scheme for retrieving one bit can be made O(n ɛ), for any ɛ>0, where n is the number of bits in the database. We extend the protocol to a block retrieval scheme which is specially efficient when the number of records in the database is equal to the size of each record.

International Conference on Cryptology in India•Jan 1, 2000•0 citations
We propose two symmetrically-private information retrieval protocols based on quantum key distribution, which provide a good degree of database and user privacy while being flexible, loss-resistant and easily generalized to a large database similar to the precedent works. Furthermore, one protocol is robust to a collective-dephasing noise, and the other is robust to a collective-rotation noise.
Symmetrically private information retrieval, a fundamental problem in the field of secure multiparty computation, is defined as follows: A database DDD of NNN bits held by Bob is queried by a user Alice who is interested in the bit Db{D}_{b}Db​ in such a way that (1) Alice learns Db{D}_{b}Db​ and only Db{D}_{b}Db​ and (2) Bob does not learn anything about Alice's choice bbb. While solutions to this problem in the classical domain rely largely on unproven computational complexity theoretic assumptions, it is also known that perfect solutions that guarantee both database and user privacy are impossible in the quantum domain. Jakobi et al. [Phys. Rev. A 83, 022301 (2011)] proposed a protocol for oblivious transfer using well-known quantum key device (QKD) techniques to establish an oblivious key to solve this problem. Their solution provided a good degree of database and user privacy (using physical principles like the impossibility of perfectly distinguishing nonorthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of the Scarani-Acin-Ribordy-Gisin 2004 protocol). However, their quantum oblivious key distribution (QOKD) protocol requires a communication complexity of O(NlogN)O(N\mathrm{log}N)O(NlogN). Since modern databases can be extremely large, it is important to reduce this communication as much as possible. In this paper, we first suggest a modification of their protocol wherein the number of qubits that need to be exchanged is reduced to O(N)O(N)O(N). A subsequent generalization reduces the quantum communication complexity even further in such a way that only a few hundred qubits are needed to be transferred even for very large databases.
Private information retrieval (PIR) is a database query protocol that provides user privacy in that the user can learn a particular entry of the database of his interest but his query would be hidden from the data centre. Symmetric private information retrieval (SPIR) takes PIR further by additionally offering database privacy, where the user cannot learn any additional entries of the database. Unconditionally secure SPIR solutions with multiple databases are known classically, but are unrealistic because they require long shared secret keys between the parties for secure communication and shared randomness in the protocol. Here, we propose using quantum key distribution (QKD) instead for a practical implementation, which can realise both the secure communication and shared randomness requirements. We prove that QKD maintains the security of the SPIR protocol and that it is also secure against any external eavesdropper. We also show how such a classical-quantum system could be implemented practically, using the example of a two-database SPIR protocol with keys generated by measurement device-independent QKD. Through key rate calculations, we show that such an implementation is feasible at the metropolitan level with current QKD technology.
Private query protocols [1-3] use uncertainty in quantum mechanics to offer functionality similar to 1-out-of-N oblivious transfer (where a user, Ursula, retrieves a single element from a database provider, Dave, who learns nothing about which of the N elements was retrieved). The difference in functionality varies for each private query protocol, but in all cases is motivated by the fact that perfect 1-out-of-N oblivious transfer has been shown to be impossible if the attacker possess an arbitrarily powerful quantum computer [4]. Nonetheless, quantum protocols can offer security against stronger adversaries than protocols relying only on classical information, and it remains an interesting question as to what level of security can be achieved using quantum information. We present a proof-of-principle demonstration of a novel private query protocol that is loss- and fault-tolerant, making it suitable for implementation in a real-world environment, and show that it offers excellent privacy against several quantum attacks [5]. This demonstration is performed over a deployed fibre link between the University of Calgary and SAIT Polytechnic using a slightly modified quantum key distribution (QKD) system [6]. Oblivious transfer (OT) is a well studied primitive in classical information theory, and protocols
We propose a quantum solution to the classical private information retrieval (PIR) problem, which allows one to query a database in a private manner. The protocol offers privacy thresholds and allows the user to obtain information from a database in a way that offers the potential adversary, in this model the database owner, no possibility of deterministically establishing the query contents. This protocol may also be viewed as a solution to the symmetrically private information retrieval problem in that it can offer database security (inability for a querying user to steal its contents). Compared to classical solutions, the protocol offers substantial improvement in terms of communication complexity. In comparison with the recent quantum private queries [Phys. Rev. Lett. 100, 230502 (2008)] protocol, it is more efficient in terms of communication complexity and the number of rounds, while offering a clear privacy parameter. We discuss the security of the protocol and analyze its strengths and conclude that using this technique makes it challenging to obtain the unconditional (in the information-theoretic sense) privacy degree; nevertheless, in addition to being simple, the protocol still offers a privacy level. The oracle used in the protocol is inspired both by the classical computational PIR solutions as well as the Deutsch-Jozsa oracle.
Abstract. In this paper we present a single-round, single-server symmetrically private information retrieval scheme, in which privacy of user follows from intractability of the quadratic residuacity problem and the privacy of the database follows from the XOR assumption for quadratic residues introduced in this paper. The communication complexity of the proposed scheme for retrieving one bit can be made O(n ɛ), for any ɛ>0, where n is the number of bits in the database. We extend the protocol to a block retrieval scheme which is specially efficient when the number of records in the database is equal to the size of each record.