Towards Communication-Efficient Quantum Oblivious Key Distribution

Abstract

Oblivious Transfer, a fundamental problem in the field of secure multi-party computation is defined as follows: A database DB of N bits held by Bob is queried by a user Alice who is interested in the bit DB_b in such a way that (1) Alice learns DB_b and only DB_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(2), 022301, Feb 2011] proposed a protocol for Oblivious Transfer using well known 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 impossibility of perfectly distinguishing non-orthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of SARG04). However, their Quantum Oblivious Key Distribution (QOKD) protocol requires a communication complexity of O(N 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.

7 pages

References in corpus (3)

• Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulses implementations
• Practical private database queries based on a quantum key distribution protocol
• Quantum Private Queries: security analysis

Cited by in corpus (8)

• Post-processing of the oblivious key in quantum private queries
• QKD-based quantum private query without a failure probability
• Performing private database queries in a real-world environment using a quantum protocol
• Device Independent Quantum Private Query
• Provably-secure symmetric private information retrieval with quantum cryptography
• A Quantum-based Database Query Scheme for Privacy Preservation in Cloud Environment
• Improved and Formal Proposal for Device Independent Quantum Private Query
• A generic construction of quantum-oblivious-key-transfer-based private query with ideal database security and zero failure