Quantum Private Information Retrieval has linear communication complexity

Abstract

In Private Information Retrieval (PIR), a client queries an n-bit database in order to retrieve an entry of her choice, while maintaining privacy of her query value. Chor, Goldreich, Kushilevitz, and Sudan showed that, in the information-theoretical setting, a linear amount of communication is required for classical PIR protocols (and thus that the trivial protocol is optimal). This linear lower bound was shown by Nayak to hold also in the quantum setting. Here, we extend Nayak's result by considering approximate privacy, and requiring security only against "specious" adversaries, which are, in analogy to classical honest-but-curious adversaries, the weakest reasonable quantum adversaries. We show that, even in this weakened scenario, Quantum Private Information Retrieval (QPIR) requires n qubits of communication. From this follows that Le Gall's recent QPIR protocol with sublinear communication complexity is not information-theoretically private, against the weakest reasonable cryptographic adversary.

8 pages, minor typos fixed, affiliation of A. B. changed, acknowledgments extended

References in corpus (3)

• Quantum private queries
• Secure two-party quantum evaluation of unitaries against specious adversaries
• Quantum Private Information Retrieval with Sublinear Communication Complexity

Cited by in corpus (12)

• Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers
• Privacy in Quantum Communication Complexity
• Quantum homomorphic encryption for polynomial-sized circuits
• Security Improvements of Several Basic Quantum Private Query Protocols with O(log N) Communication Complexity
• Practical Quantum Appointment Scheduling
• Limitations on Transversal Computation through Quantum Homomorphic Encryption
• Further Limitations on Information-Theoretically Secure Quantum Homomorphic Encryption
• Prior Entanglement Exponentially Improves One-Server Quantum Private Information Retrieval for Quantum Messages
• Interactive Leakage Chain Rule for Quantum Min-entropy
• Quantum Private Information Retrieval for Quantum Messages
• Impossibility of Quantum Private Queries
• Capacity of Quantum Private Information Retrieval with Colluding Servers