RISC Seminar

Quantum Private Information Retrieval

Speaker: Ronald de Wolf (CWI)

Date/Time: Thursday 06.10.05, 12.05 h

Location: Room Z009, CWI Amsterdam

Abstract: Private information retrieval concerns the following problem. A user wants to retrieve the i-th bit from an n-bit database that is replicated over k servers, but he wants to do that privately: none of the servers should learn any information about i. We are interested in the amount of communication needed for this, comparing classical and quantum PIR schemes. For 1 server this amount is linear in n, classically as well as quantumly (Nayak). For 2 servers, the best known classical PIR scheme uses n^{1/3} communication. We exhibit a quantum 2-server PIR scheme that uses n^{3/10} qubits of communication. Our main tool is a certain reduction from 2 classical servers to 1 quantum server. We get similar quantum improvements for more than 2 servers. We also prove a new lower bound for classical 2-server PIR schemes in which the servers send only short answers.
This talk is based on joint work with Iordanis Kerenidis (STOC 03) and Stephanie Wehner (ICALP 05)

Speaker:	Ronald de Wolf (CWI)
Date/Time:	Thursday 06.10.05, 12.05 h
Location:	Room Z009, CWI Amsterdam
Abstract:	Private information retrieval concerns the following problem. A user wants to retrieve the i-th bit from an n-bit database that is replicated over k servers, but he wants to do that privately: none of the servers should learn any information about i. We are interested in the amount of communication needed for this, comparing classical and quantum PIR schemes. For 1 server this amount is linear in n, classically as well as quantumly (Nayak). For 2 servers, the best known classical PIR scheme uses n^{1/3} communication. We exhibit a quantum 2-server PIR scheme that uses n^{3/10} qubits of communication. Our main tool is a certain reduction from 2 classical servers to 1 quantum server. We get similar quantum improvements for more than 2 servers. We also prove a new lower bound for classical 2-server PIR schemes in which the servers send only short answers. This talk is based on joint work with Iordanis Kerenidis (STOC 03) and Stephanie Wehner (ICALP 05)