Quantum Private Queries Protocol Based on Quantum Random Access Memory

This example protocol performs the task of symmetric private information retrieval (SPIR) and has information-theoretic security. It is a single-database two-round quantum SPIR protocol for a classical database, which is based on a quantum random access memory (qRAM) algorithm. Its security, and more precisely user privacy, is based on a cheat-sensitive strategy: if the malicious server tries to learn the user’s queries, then the user has a non-zero probability of detecting it. As for data privacy, a dishonest user can recover at most two database elements.

Tags: Quantum Enhanced Classical Functionality, Specific Task, Two Party Protocol, Two Round Protocol, Information-Theoretic Security, Symmetric Private Information Retrieval, Quantum Private Queries, Quantum Random Access Memory, Single-Database.

Assumptions

• Cheat-sensitive protocol: the server (Bob) will not cheat if there is a non-zero probability of being caught cheating.
• Each index in the database maps to a unique database element.
• Index $0$ in the database maps to a ‘dummy’ database element, $A_{0}$, known to the user.

Outline

A user, Alice, wants to retrieve an element from a database owned by a server, Bob, without revealing to Bob which element was retrieved (user privacy). Bob wants the amount of information that Alice can get on other database elements than the desired one to be bounded (data privacy).

• Choice of scenario:
  • Alice chooses randomly between two scenarios ❶ and ❷.
• Query:
  • Alice prepares two quantum registers: a quantum register corresponding to the index of her desired database element, as well as a superposition of a quantum register corresponding to the index of her desired database element with a quantum register corresponding to the index of a dummy database element known by Alice ('rhetoric query').
  • Scenario ❶: Alice sends the first quantum register to Bob. Scenario ❷: Alice sends the second quantum register (superposition) to Bob.
• Answer:
  • Bob interrogates the database with the received quantum register ('query register') using a qRAM algorithm. The output of the qRAM algorithm is another quantum register ('answer register').
  • Bob sends to Alice both the received query register and the answer register.
• Query:
  • Scenario ❶: Alice sends the second quantum register (superposition) to Bob. Scenario ❷: Alice sends the first quantum register to Bob.
• Answer:
  • Bob interrogates the database with the received quantum register ('query register') using a qRAM algorithm. The output of the qRAM algorithm is another quantum register ('answer register').
  • Bob sends to Alice both the received query register and the answer register.
• Retrieval & Honesty test:
  • Alice performs a test on the received quantum registers to check if the server cheated. First, she measures the answer register corresponding to the non-superposed query register to obtain the desired database element. Based on this first measurement outcome, she tailors the measurement that she performs on the other answer register (corresponding to the superposed query) in such a way that if the measurement outcome is not a certain outcome, Alice knows for sure that Bob cheated. Otherwise, Alice assumes that Bob is honest (which is not guaranteed).

Notation

• $n$: size of quantum registers.
• $N$: number of entries in the database ($N=2^{n}$).
• $j$: index of the desired database element.
• $A_{j}$: classical database entry (bit string) corresponding to index $j$.

Requirements

User (Alice):

• Can prepare $n$ qubit memory registers (for a database of $N=2^{n}$ or less elements).
• Can measure quantum registers.

Server (Bob) :

• A quantum random access memory (qRAM).

Communication:

• A quantum channel.

Properties

• User privacy:
  • A malicious server trying to learn the user’s queries has a non-zero probability of being caught cheating by the user. Hence, assuming that the server will not cheat if cheat may be detected, this protocol ensures perfect user privacy.
  • For a cheating strategy where the server performs projective measurements on the user’s queries, the server will learn with certainty the index of the desired database element, and he has probability $1/4$ of being caught cheating by the user via the honesty test.

• Data privacy: This protocol does not ensure perfect data privacy; however, a dishonest user (Alice) should be able to get at most two database entries (i.e., one extra database entry compared to a secure SPIR protocol that satisfies the data privacy condition).
• Communication complexity: $O(\log(N))$.

Protocol Description

Inputs:

• User (Alice): index $j$ of the desired database element; Alice knows the $0^{\text{th}}$ database element, $A_{0}$.
• Server (Bob): classical database with $N$ elements $A_{0},...,A_{N-1}$.

Output:

• User (Alice): desired database entry $A_{j}$ (in the case of honest parties).

Protocol:

• Choice of scenario:
  • Alice chooses randomly between two scenarios ❶ and ❷.
• Query:
  • Alice prepares two n qubit registers: $|j\rangle _{Q}$ and $(|j\rangle _{Q}+|0\rangle _{Q})/{\sqrt {2}}$.
  • Scenario ❶: Alice sends $|j\rangle _{Q}$ to Bob. Scenario ❷: Alice sends $(|j\rangle _{Q}+|0\rangle _{Q})/{\sqrt {2}}$ to Bob.
• Answer:
  • Bob interrogates the database with the received quantum register ('query register') using a qRAM algorithm $\sum _{j}\alpha _{j}|j\rangle _{Q}\rightarrow \sum _{j}\alpha _{j}|j\rangle _{Q}|A_{j}\rangle _{R}$. The output of the qRAM algorithm is another quantum register: $|j\rangle _{Q}|A_{j}\rangle _{R}$ in scenario ❶ or $(|j\rangle _{Q}|A_{j}\rangle _{R}+|0\rangle _{Q}|A_{0}\rangle _{R})/{\sqrt {2}}$ in scenario ❷.
  • Bob sends to Alice the output of the qRAM algorithm: $|j\rangle _{Q}|A_{j}\rangle _{R}$ in scenario ❶ or $(|j\rangle _{Q}|A_{j}\rangle _{R}+|0\rangle _{Q}|A_{0}\rangle _{R})/{\sqrt {2}}$ in scenario ❷
• Query:
  • Scenario ❶: Alice sends $(|j\rangle _{Q}+|0\rangle _{Q})/{\sqrt {2}}$ to Bob. Scenario ❷: Alice sends $|j\rangle _{Q}$ to Bob.
• Answer:
  • Bob interrogates the database with the received quantum register ('query register') using the qRAM algorithm $\sum _{j}\alpha _{j}|j\rangle _{Q}\rightarrow \sum _{j}\alpha _{j}|j\rangle _{Q}|A_{j}\rangle _{R}$. The output of the qRAM algorithm is another quantum register: $(|j\rangle _{Q}|A_{j}\rangle _{R}+|0\rangle _{Q}|A_{0}\rangle _{R})/{\sqrt {2}}$ in scenario ❶ or $|j\rangle _{Q}|A_{j}\rangle _{R}$ in scenario ❷.
  • Bob sends to Alice the output of the qRAM algorithm: $(|j\rangle _{Q}|A_{j}\rangle _{R}+|0\rangle _{Q}|A_{0}\rangle _{R})/{\sqrt {2}}$ in scenario ❶ or $|j\rangle _{Q}|A_{j}\rangle _{R}$ in scenario ❷.
• Retrieval & Honesty test:
  • Alice performs a test on the received quantum registers to check if the server cheated. First, she measures $|j\rangle _{Q}|A_{j}\rangle _{R}$ to obtain the desired database element $A_{j}$. Based on this first measurement outcome, she tailors the measurement that she performs on $(|j\rangle _{Q}|A_{j}\rangle _{R}+|0\rangle _{Q}|A_{0}\rangle _{R})/{\sqrt {2}}$ in such a way that if the measurement outcome is not a certain outcome, Alice knows for sure that Bob cheated. Otherwise, Alice assumes that Bob is honest (which is not guaranteed).

Further Information

• The authors of this protocol suggest using their qRAM design in which each call of the qRAM corresponds to $O(n)$ quantum logic operations.
• The authors published a security analysis of their protocol in 2010. This paper also discusses variants of the protocol to improve its security.
• A practical implementation of this protocol using linear optics was published by De Martini et al (2009).

*contributed by Marine Demarty