Source-linked AI summary
Quantum private queries
Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone
TL;DR
The paper addresses private information retrieval while protecting both the user’s query and the database. It introduces a cheat-sensitive quantum protocol using superposed queries, achieving exponential reductions in communication and computational complexity while allowing Alice to detect query snooping.
Problem
Private information retrieval must protect Alice’s query without requiring Bob to disclose his database, while conventional approaches face conflicting user- and data-privacy goals.
Method
QPQ uses quantum superpositions of database queries and returned query registers so Alice can test whether Bob’s interaction disturbed the superposition.
Results
The protocol provides perfect data privacy, lets Alice detect cheating with nonzero probability, and reduces communication and computational complexity exponentially relative to known strategies.
Takeaways & Limitations
Alice can retrieve a database item while testing whether Bob retained information about her query, without requiring disclosure of the whole database.
Takeaways & Limitations
The basic protocol assumes that each queried index has a uniquely determined answer.
Abstract
from arXiv · showhide
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.