Quantum private queries

Abstract

We propose a cheat sensitive quantum protocol to perform a private search on a classical database which is efficient in terms of communication complexity. It allows a user to retrieve an item from the server in possession of the database without revealing which item she retrieved: if the server tries to obtain information on the query, the person querying the database can find it out. Furthermore our protocol ensures perfect data privacy of the database, i.e. the information that the user can retrieve in a single queries is bounded and does not depend on the size of the database. With respect to the known (quantum and classical) strategies for private information retrieval, our protocol displays an exponential reduction both in communication complexity and in running-time computational complexity.

4 pages, 1 figure

References in corpus (3)

• Quantum random access memory
• Cheat Sensitive Quantum Bit Commitment
• Uncertainty, Monogamy, and Locking of Quantum Correlations

Cited by in corpus (39)

• Experimental Demonstration of Blind Quantum Computing
• Architectures for a quantum random access memory
• Quantum Cryptography Beyond Quantum Key Distribution
• Practical private database queries based on a quantum key distribution protocol
• Flexible quantum private queries based on quantum key distribution
• Post-processing of the oblivious key in quantum private queries
• QKD-based quantum private query without a failure probability
• Efficient universal blind computation
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Quantum Private Queries: security analysis
• Symmetric quantum fully homomorphic encryption with perfect security
• Limitations on information theoretically secure quantum homomorphic encryption
• Quantum cryptography: key distribution and beyond
• Resilience of quantum random access memory to generic noise
• Performing private database queries in a real-world environment using a quantum protocol
• Device Independent Quantum Private Query
• Quantum algorithms for anomaly detection using amplitude estimation
• Quantum Private Information Retrieval has linear communication complexity
• Cryptographic quantum metrology
• Towards highly efficient broadband superconducting quantum memory
• Data centers with quantum random access memory and quantum networks
• Communication Efficient Quantum Secret Sharing
• Provably-secure symmetric private information retrieval with quantum cryptography
• Quantum Data Center: Perspectives
• Quantum Private Information Retrieval with Sublinear Communication Complexity
• Quantum cryptography beyond key distribution: theory and experiment
• Quantum Algorithm for Unsupervised Anomaly Detection
• Multi-qubit time-bin quantum RAM
• A Quantum-based Database Query Scheme for Privacy Preservation in Cloud Environment
• Quantum contract signing with entangled pairs
• Device-independent quantum private comparison protocol without a third party
• Security Improvements of Several Basic Quantum Private Query Protocols with O(log N) Communication Complexity
• Improved and Formal Proposal for Device Independent Quantum Private Query
• Satellites promise global-scale quantum networks
• Prior Entanglement Exponentially Improves One-Server Quantum Private Information Retrieval for Quantum Messages
• Teleportation fidelity of quantum repeater networks
• Quantum oblivious transfer: a short review
• Impossibility of Quantum Private Queries
• Teleportation Fidelity of Binary Tree Quantum Repeater Networks