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

arXiv:1208.2501 · Physical Review A

Towards communication-efficient quantum oblivious key distribution

M. V. Panduranga Rao, Markus Jakobi

Published Jan 28, 2013• 63 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.87.012331

Related papers

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

A practical scheme for quantum oblivious transfer and private database sampling

David A. Fattal, Marco Fiorentino B, Raymond G. Beausoleil

We present an unconditionally secure Oblivious Transfer protocol relying on two rounds of entanglement-free quantum communication. When played honestly, the protocol only requires the ability to measure a single qubit in a fixed basis, and to perform a coherent bit-flip (Pauli X) operation. We present a generalization to a "Private Data Sampling" protocol, where a player (Bob) can obtain a random sample of fixed size from a classical database of size N, while the database owner (Alice) remains oblivious as to which bits were accessed. The protocol is efficient in the sense that the communication complexity per query scales at most linearly with the size of the database. It does not violate Lo's "no-go" theorem for one-sided two-party secure computation, since a given joint input by Alice and Bob can result in randomly different protocol outcomes. Finally it could be used to implement a practical bit string commitment protocol, among other applications.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 28, 2008•1 citation

Fault-tolerant symmetrically-private information retrieval

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

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.

International Journal of Modern Physics B•Aug 15, 2016•0 citations

A Quantum Private Query Protocol for Enhancing both User and Database Privacy*

Yi‐Hua Zhou, Xuewei Bai, Lei-Lei Li +2 more

Abstract In order to protect the privacy of query user and database, some QKD-based quantum private query (QPQ) protocols were proposed. Unfortunately some of them cannot resist internal attack from database perfectly; some others can ensure better user privacy but require a reduction of database privacy. In this paper, a novel two-way QPQ protocol is proposed to ensure the privacy of both sides of communication. In our protocol, user makes initial quantum states and derives the key bit by comparing initial quantum state and outcome state returned from database by ctrl or shift mode instead of announcing two non-orthogonal qubits as others which may leak part secret information. In this way, not only the privacy of database be ensured but also user privacy is strengthened. Furthermore, our protocol can also realize the security of loss-tolerance, cheat-sensitive, and resisting JM attack etc.

Communications in Theoretical Physics•Jan 1, 2018•8 citations

Security of Quantum Key Distribution Protocols

Rotem Liss

The counter-intuitive features of quantum mechanics make it possible to solve problems and perform tasks that are beyond the abilities of non-quantum (classical) computers and communication devices. The field of quantum information processing studies how we can achieve such improvements by representing information as quantum states.One of the early achievements of quantum information processing is the development of quantum key distribution (QKD). QKD protocols allow two participants (Alice and Bob) to achieve the classically-impossible task of generating a secret shared key even if their adversary is computationally unlimited.Unfortunately, the security promises of QKD are true only in theory; practical implementations of QKD deviate from the theoretical protocols, and many of these deviations give rise to practical attacks. In this research thesis, we study the security properties of various QKD protocols in many practical settings:First, we study practical security of semiquantum key distribution (SQKD) protocols, where either Alice or Bob is non-quantum (classical). Following practical security problems in previous SQKD protocols, we suggest a new SQKD protocol (the "Mirror protocol") which can be securely implemented, and we prove it robust and secure against a wide range of attacks (the "uniform collective attacks").Then, we study "composable security" of the first QKD protocol created by Bennett and Brassard (BB84). BB84 has its unconditional security proved against adversaries performing the most general attacks in a theoretical (idealized) setting; however, some security approaches do not prove "composable security", which requires the secret key to remain secret even when Alice and Bob actually use it for cryptographic purposes. We generalize an algebraic security approach for BB84, making it prove composable security of BB84 (and many variants of BB84) against the most general attacks.Finally, we analyze an important practical attack (named "Bright Illumination"), showing how it can be modeled as a theoretical "Reversed-Space" attack.Overall, all results aim to enhance our understanding on how to bridge the gap between theory and practice in various sub-fields of QKD, and they may help solve a major open problem in the field of QKD: constructing a realistic QKD implementation that can be proved truly and unconditionally secure against any possible attack.

•Aug 31, 2022•0 citations

Postprocessing of the Oblivious Key in Quantum Private Query

Fei Gao, Bin Liu, Wei Huang +1 more

Private query is a kind of cryptographic protocols to protect both users' privacies in their communication. For instance, Alice wants to buy one item from Bob's database. The aim of private query is to ensure that Alice can get only one item from Bob, and simultaneously, Bob cannot know which one was taken by Alice. In pursuing high security and efficiency, some quantum private query protocols were proposed. As a practical model, Quantum-Oblivious-Key-Transfer (QOKT)-based private query, which utilizes a QOKT protocol to distribute oblivious key between Alice and Bob and then applies the key to achieve the aim of private query, has drawn much attention. Here, we focus on postprocessing of the oblivious key, and the following two contributions are achieved. 1) We analyze three recently proposed dilution methods and find two of them have serious security loophole. That is, Alice can illegally obtain much additional information about Bob's database by multiple queries. For example, Alice can obtain the whole database, which contains 104items, by only 53.4 queries averagely. 2) We present an effective error-correction method for the oblivious key, which can address the realistic scenario with channel noises and make QOKT-based private query more practical.

arXiv:1406.0589•IEEE Journal of Selected Topics in Quantum Electronics•Sep 16, 2014•125 citations
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 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 present an unconditionally secure Oblivious Transfer protocol relying on two rounds of entanglement-free quantum communication. When played honestly, the protocol only requires the ability to measure a single qubit in a fixed basis, and to perform a coherent bit-flip (Pauli X) operation. We present a generalization to a "Private Data Sampling" protocol, where a player (Bob) can obtain a random sample of fixed size from a classical database of size N, while the database owner (Alice) remains oblivious as to which bits were accessed. The protocol is efficient in the sense that the communication complexity per query scales at most linearly with the size of the database. It does not violate Lo's "no-go" theorem for one-sided two-party secure computation, since a given joint input by Alice and Bob can result in randomly different protocol outcomes. Finally it could be used to implement a practical bit string commitment protocol, among other applications.
Abstract In order to protect the privacy of query user and database, some QKD-based quantum private query (QPQ) protocols were proposed. Unfortunately some of them cannot resist internal attack from database perfectly; some others can ensure better user privacy but require a reduction of database privacy. In this paper, a novel two-way QPQ protocol is proposed to ensure the privacy of both sides of communication. In our protocol, user makes initial quantum states and derives the key bit by comparing initial quantum state and outcome state returned from database by ctrl or shift mode instead of announcing two non-orthogonal qubits as others which may leak part secret information. In this way, not only the privacy of database be ensured but also user privacy is strengthened. Furthermore, our protocol can also realize the security of loss-tolerance, cheat-sensitive, and resisting JM attack etc.
The counter-intuitive features of quantum mechanics make it possible to solve problems and perform tasks that are beyond the abilities of non-quantum (classical) computers and communication devices. The field of quantum information processing studies how we can achieve such improvements by representing information as quantum states.One of the early achievements of quantum information processing is the development of quantum key distribution (QKD). QKD protocols allow two participants (Alice and Bob) to achieve the classically-impossible task of generating a secret shared key even if their adversary is computationally unlimited.Unfortunately, the security promises of QKD are true only in theory; practical implementations of QKD deviate from the theoretical protocols, and many of these deviations give rise to practical attacks. In this research thesis, we study the security properties of various QKD protocols in many practical settings:First, we study practical security of semiquantum key distribution (SQKD) protocols, where either Alice or Bob is non-quantum (classical). Following practical security problems in previous SQKD protocols, we suggest a new SQKD protocol (the "Mirror protocol") which can be securely implemented, and we prove it robust and secure against a wide range of attacks (the "uniform collective attacks").Then, we study "composable security" of the first QKD protocol created by Bennett and Brassard (BB84). BB84 has its unconditional security proved against adversaries performing the most general attacks in a theoretical (idealized) setting; however, some security approaches do not prove "composable security", which requires the secret key to remain secret even when Alice and Bob actually use it for cryptographic purposes. We generalize an algebraic security approach for BB84, making it prove composable security of BB84 (and many variants of BB84) against the most general attacks.Finally, we analyze an important practical attack (named "Bright Illumination"), showing how it can be modeled as a theoretical "Reversed-Space" attack.Overall, all results aim to enhance our understanding on how to bridge the gap between theory and practice in various sub-fields of QKD, and they may help solve a major open problem in the field of QKD: constructing a realistic QKD implementation that can be proved truly and unconditionally secure against any possible attack.
Private query is a kind of cryptographic protocols to protect both users' privacies in their communication. For instance, Alice wants to buy one item from Bob's database. The aim of private query is to ensure that Alice can get only one item from Bob, and simultaneously, Bob cannot know which one was taken by Alice. In pursuing high security and efficiency, some quantum private query protocols were proposed. As a practical model, Quantum-Oblivious-Key-Transfer (QOKT)-based private query, which utilizes a QOKT protocol to distribute oblivious key between Alice and Bob and then applies the key to achieve the aim of private query, has drawn much attention. Here, we focus on postprocessing of the oblivious key, and the following two contributions are achieved. 1) We analyze three recently proposed dilution methods and find two of them have serious security loophole. That is, Alice can illegally obtain much additional information about Bob's database by multiple queries. For example, Alice can obtain the whole database, which contains 104items, by only 53.4 queries averagely. 2) We present an effective error-correction method for the oblivious key, which can address the realistic scenario with channel noises and make QOKT-based private query more practical.