Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness

This example protocol by Kerenidis and de Wolf (2003) performs the task of symmetric private information retrieval (SPIR) and has information-theoretic security. It is a multi-database scheme that works on top of a classical multi-database PIR scheme by Beimel et al (2002). The main feature of this protocol is that is does not require any shared randomness between servers which is the main assumptions of most SPIR protocols; however, this is achieved in the honest user model only. Moreover, it satisfies the correctness, user privacy and data privacy conditions, hence, it is a perfectly secure SPIR scheme.

Tags: Quantum Enhanced Classical Functionality, Specific Task, Multi Party Protocol, Symmetric Private Information Retrieval, Information-Theoretic Security, Multi-Database, One-Round Protocol, Entanglement.

Assumptions

• Honest user
• No communication assumption (between servers)

Outline

A user wants to privately retrieve an element from a classical database that has been replicated and distributed among $k$ servers. Servers do not want the user to get any information on the database beyond the desired database item.

• Query: First, the user hides the index of the desired database element in several classical queries (one per server) and using some randomness. Then, the user prepares one quantum register (‘query register’) per server that depends on the classical query, on some new randomness (one per server) and on some function of the index of the desired database element and the randomness of the classical queries (which will be useful in the retrieval phase). Those quantum registers are entangled with another qubit kept by the user, and then sent to the user.
• Answer: Each server applies some unitary map on the received query register and sends the resulting register (‘answer register’) back to the client. The classical answer of a given server is encoded in the corresponding answer register.
• Retrieval: From all the received answer registers, the user can retrieve the desired database element: the user disentangles the answer registers from his qubit, then applies a Hadamard transform to his qubit and measures it in the computational basis. The outcome of the measurement is the desired database element.

Notation

• $k$: number of servers involved in the protocol.
• $n$: number of database elements.
• $x$: database; this is an $n$ bit string.
• $i$: index of the desired database element, $x_{i}$.
• $r$: random string.
• $t$: length of a query bit string (sent by the user to one of the $k$ servers).
• $a$: length of an answer bit string (sent by one of the $k$ servers to the user).
• $a_{j}$: classical answer of the $j^{\text{th}}$ server in Beimel et al classical PIR scheme.
• $b_{j}$: combined with the $a_{j}$’s, the $b_{j}$’s (which are known only to the user) allow the user to reconstruct the desired database element at the end of Beimel et al protocol.

Requirements

User:

• Has a random number generator.
• Can prepare, measure, and apply quantum gates to quantum registers.

Servers:

• Can apply gates to quantum registers.

Communication:

• A quantum channel.

Properties

Security

Precise security definitions for correctness, user privacy and data privacy that are used in this protocol are the following:

• Correctness (or Recovery): For all choices of database $x$ and index $i$, the probability that the output (bit) of the protocol on the user's side is the desired database element equals $1$.
• User privacy: the density matrix of each server is independent of the index $i$ of the desired database item throughout the protocol.
• Data privacy: the concatenation of the density matrices of the user is independent of other database items than the desired one ($x_{j}\forall j\neq i$) throughout the protocol.

This protocol ensures perfect user and data privacy and satisfies the correctness condition. Hence, it is secure.

Communication Complexity

This protocol uses $n^{O(\log \log(k)/k\log(k))}$ qubits of communication.

Protocol Description

Inputs:

• User: index of the desired database element $i$.
• Each of the $k$ servers: database $x$ (an $n$ bit string).

Output:

• User: desired database element $x_{i}$ (a single bit of $x$).

Protocol:

This protocol works on top of Beimel et al classical PIR scheme, which involves the following steps:

• Query: The user generates a random string $r$ and $k$ queries $q_{1}(i,r),...,q_{k}(i,r)\in \{0,1\}^{t}$. The user sends each query to the corresponding server.
• Answer: Each server answers the user: the $j^{\text{th}}$ server answers with classical answer $a_{j}\in \{0,1\}^{a}$.
• Retrieval: The user outputs the desired database element $x_{i}=\sum _{j=1}^{k}a_{j}\cdot b_{j}$ where $b_{j}=b_{j}(i,r)\in \{0,1\}^{a}$, and all operations are modulo 2.

Kerenidis and de Wolf quantum SPIR scheme works as follows:

• Query:
  • The user generates a random string $r$, $k$ queries $q_{1}(i,r),...,q_{k}(i,r)\in \{0,1\}^{t}$ and $k$ random strings $r_{1},...,r_{k}\in \{0,1\}^{a}$.
  • The user prepares a $(k+1)$-register state: ${\frac {1}{\sqrt {2}}}|0\rangle |q_{1},r_{1}\rangle ...|q_{k},r_{k}\rangle +{\frac {1}{\sqrt {2}}}|1\rangle |q_{1},r'_{1}\rangle ...|q_{k},r'_{k}\rangle$ where $r'_{j}:=r_{j}+b_{j}$ and $b_{j}=b_{j}(i,r)\in \{0,1\}^{a}$ is the part known only to the user that, together with the answers of the server, allows the user to reconstruct the desired database element at the end of Beimel et al PIR protocol: $\sum _{j=1}^{k}a_{j}\cdot b_{j}=x_{i}$.
  • The user keeps the first $1$-qubit register and sends the other $k$ registers to the corresponding server.
• Answer:
  • Each server applies a unitary map to the received quantum register: $|q_{j},r\rangle \rightarrow (-1)^{a_{j}\cdot r}|q_{j},r\rangle$ where $a_{j}=a_{j}(q_{j},x)\in \{0,1\}^{a}$ is the classical answer of the $j^{\text{th}}$ server to the user in Beimel et al PIR protocol. The transformed quantum register is then sent back to the user.
• Retrieval:
  • The complete state owned by the user is now of the form: ${\frac {1}{\sqrt {2}}}|0\rangle (-1)^{a_{1}\cdot r_{1}}|q_{1},r_{1}\rangle ...(-1)^{a_{k}\cdot r_{k}}|q_{k},r_{k}\rangle +{\frac {1}{\sqrt {2}}}|1\rangle (-1)^{a_{1}\cdot r'_{1}}|q_{1},r'_{1}\rangle ...(-1)^{a_{k}\cdot r'_{k}}|q_{k},r'_{k}\rangle$ $={\frac {1}{\sqrt {2}}}|0\rangle (-1)^{\sum _{j=1}^{k}a_{j}\cdot r_{j}}|q_{1},r_{1}\rangle ...|q_{k},r_{k}\rangle +{\frac {1}{\sqrt {2}}}|1\rangle (-1)^{\sum _{j=1}^{k}a_{j}\cdot r'_{j}}|q_{1},r'_{1}\rangle ...|q_{k},r'_{k}\rangle$ $={\frac {1}{\sqrt {2}}}|0\rangle (-1)^{\sum _{j=1}^{k}a_{j}\cdot r_{j}}|q_{1},r_{1}\rangle ...|q_{k},r_{k}\rangle +{\frac {1}{\sqrt {2}}}|1\rangle (-1)^{\sum _{j=1}^{k}a_{j}\cdot (r_{j}+b_{j})}|q_{1},r'_{1}\rangle ...|q_{k},r'_{k}\rangle$ $=(-1)^{\sum _{j=1}^{k}a_{j}\cdot r_{j}}\left({\frac {1}{\sqrt {2}}}|0\rangle |q_{1},r_{1}\rangle ...|q_{k},r_{k}\rangle +{\frac {1}{\sqrt {2}}}|1\rangle (-1)^{\sum _{j=1}^{k}a_{j}\cdot b_{j}}|q_{1},r'_{1}\rangle ...|q_{k},r'_{k}\rangle \right)$ Hence, up to a global phase $(-1)^{\sum _{j=1}^{k}a_{j}\cdot r_{j}}$, this state is: ${\frac {1}{\sqrt {2}}}|0\rangle |q_{1},r_{1}\rangle ...|q_{k},r_{k}\rangle +{\frac {1}{\sqrt {2}}}|1\rangle (-1)^{x_{i}}|q_{1},r'_{1}\rangle ...|q_{k},r'_{k}\rangle$.
  • To retrieve the desired database element $x_{i}$, the user then maps the $k$ quantum registers to the ground state – this way, entanglement is destroyed, and the first qubit is in state ${\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{x_{i}}|1\rangle )$.
  • Lastly, the user applies a Hadamard transform to the first qubit, which is now in state $|x_{i}\rangle$. Measuring in the computational basis $\{|0\rangle ,|1\rangle \}$ has classical outcome the desired bit $x_{i}$.

Further Information

• This quantum protocol can be based on other classical PIR schemes with the same structure as this of Beimel et al. The authors chose this specific PIR protocol as this was the best available information theoretically secure PIR scheme in terms of communication complexity at the time of publication.

*contributed by Marine Demarty