Editing Quantum Private Queries Protocol Based on Quantum Random Access Memory

<!-- This is a comment. You can erase them or write below -->


<!-- Intro: brief description of the protocol -->
This [https://arxiv.org/pdf/0708.2992.pdf example protocol] performs the task of [[(Symmetric) Private Information Retrieval|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|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: related pages or category -->
'''Tags:''' [[:Category:Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category:Specific Task|Specific Task]], [[:Category:Two Party Protocols|Two Party Protocol]], [[Two Round Protocol]], [[Information-Theoretic Security]], [[(Symmetric) Private Information Retrieval|Symmetric Private Information Retrieval]], [[Quantum Private Queries]], [[Quantum Random Access Memory]], [[Single-Database]].

==Assumptions==
<!-- It describes the setting in which the protocol will be successful. -->
*	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 <math>0</math> in the database maps to a ‘dummy’ database element, <math>A_0</math>, known to the user.


==Outline==
<!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol -->
''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==
<!--  Connects the non-mathematical outline with further sections. -->
*	<math>n</math>: size of quantum registers.
*	<math>N</math>: number of entries in the database (<math>N=2^n</math>).
*	<math>j</math>: index of the desired database element.
*	<math>A_j</math>: classical database entry (bit string) corresponding to index <math>j</math>.

<!--==Knowledge Graph==-->
<!-- Add this part if the protocol is already in the graph -->
<!--{{graph}}-->

==Requirements==
'''User''' (Alice):
*	Can prepare <math>n</math> qubit memory registers (for a database of <math>N=2^n</math> or less elements).
*	Can measure quantum registers.
'''Server''' (Bob) :
*	A quantum random access memory (qRAM).
'''Communication''':
*	A quantum channel.


==Properties==
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->
*	'''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 <math>1/4</math> 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''': <math> O(\log(N)) </math>.



==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
'''Inputs:''' 
*	User (Alice): index <math>j</math> of the desired database element; Alice knows the <math>0^\text{th}</math> database element, <math>A_0</math>.
*	Server (Bob): classical database with <math>N</math> elements <math>A_0,...,A_{N-1}</math>.
'''Output:'''
*	User (Alice): desired database entry <math>A_j</math> (in the case of honest parties).
'''Protocol:'''
* '''Choice of scenario:''' 
**	Alice chooses randomly between two scenarios ❶ and ❷.
* '''Query:'''
**	Alice prepares two n qubit registers: <math>|j\rangle_Q</math> and <math>(|j\rangle_Q+|0\rangle_Q)/\sqrt{2}</math>.
**	Scenario ❶: Alice sends <math>|j\rangle_Q</math> to Bob. Scenario ❷: Alice sends <math>(|j\rangle_Q+|0\rangle_Q)/\sqrt{2}</math> to Bob.
* '''Answer:'''
**	Bob interrogates the database with the received quantum register ('query register') using a qRAM algorithm <math>\sum_j \alpha_j |j\rangle_Q \rightarrow  \sum_j \alpha_j |j\rangle_Q |A_j\rangle_R</math>. The output of the qRAM algorithm is another quantum register: <math>|j\rangle_Q |A_j\rangle_R</math> in scenario ❶ or <math>(|j\rangle_Q |A_j \rangle_R+|0\rangle_Q |A_0 \rangle_R)/\sqrt{2}</math> in scenario ❷.
**	Bob sends to Alice the output of the qRAM algorithm: <math>|j\rangle_Q |A_j\rangle_R</math> in scenario ❶ or <math>(|j\rangle_Q |A_j \rangle_R+|0\rangle_Q |A_0 \rangle_R)/\sqrt{2}</math> in scenario ❷
* '''Query:'''
**	Scenario ❶: Alice sends <math>(|j\rangle_Q+|0\rangle_Q)/\sqrt{2}</math> to Bob. Scenario ❷: Alice sends <math>|j\rangle_Q</math> to Bob.
* '''Answer:'''
**	Bob interrogates the database with the received quantum register ('query register') using the qRAM algorithm <math>\sum_j \alpha_j |j\rangle_Q \rightarrow  \sum_j \alpha_j |j\rangle_Q |A_j\rangle_R</math>. The output of the qRAM algorithm is another quantum register: <math>(|j\rangle_Q |A_j \rangle_R+|0\rangle_Q |A_0 \rangle_R)/\sqrt{2}</math> in scenario ❶ or <math>|j\rangle_Q |A_j\rangle_R</math> in scenario ❷.
**	Bob sends to Alice the output of the qRAM algorithm: <math>(|j\rangle_Q |A_j \rangle_R+|0\rangle_Q |A_0 \rangle_R)/\sqrt{2}</math> in scenario ❶ or <math>|j\rangle_Q |A_j\rangle_R</math> in scenario ❷.
* '''Retrieval & Honesty test:''' 
**      Alice performs a test on the received quantum registers to check if the server cheated. First, she measures <math>|j\rangle_Q |A_j\rangle_R</math> to obtain the desired database element <math>A_j</math>. Based on this first measurement outcome, she tailors the measurement that she performs on <math>(|j\rangle_Q |A_j \rangle_R+|0\rangle_Q |A_0 \rangle_R)/\sqrt{2}</math> 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==
<!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... -->
*	The authors of this protocol suggest using [https://arxiv.org/pdf/0708.1879.pdf their qRAM design] in which each call of the qRAM corresponds to <math>O(n)</math> quantum logic operations.
*	The authors published a [https://arxiv.org/pdf/0809.1934.pdf 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 [https://arxiv.org/pdf/0902.0222.pdf De Martini et al (2009)].



<!--==References==-->
<div style='text-align: right;'>''*contributed by Marine Demarty''</div>