Editing Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness

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


<!-- Intro: brief description of the protocol -->
This [https://arxiv.org/pdf/quant-ph/0307076.pdf example protocol] by Kerenidis and de Wolf (2003) performs the task of [[(Symmetric) Private Information Retrieval|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 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf 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: related pages or category -->
'''Tags:''' 
[[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]],
[[:Category:Specific Task|Specific Task]],
[[:Category:Multi Party Protocols|Multi Party Protocol]],
[[(Symmetric) Private Information Retrieval|Symmetric Private Information Retrieval]],
[[Information-Theoretic Security]],
[[Multi-Database]],
[[One-Round Protocol]],
[[Entanglement]].




==Assumptions==
<!-- It describes the setting in which the protocol will be successful. -->
*	Honest user
*	No communication assumption (between servers)


==Outline==
<!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol -->
''A user wants to privately retrieve an element from a classical database that has been replicated and distributed among <math>k</math> 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==
<!--  Connects the non-mathematical outline with further sections. -->
*	<math>k</math>: number of servers involved in the protocol.
*	<math>n</math>: number of database elements.
*	<math>x</math>: database; this is an <math>n</math> bit string.
*	<math>i</math>: index of the desired database element, <math>x_i</math>.
*	<math>r</math>: random string.
*	<math>t</math>: length of a query bit string (sent by the user to one of the <math>k</math> servers).
*	<math>a</math>: length of an answer bit string (sent by one of the <math>k</math> servers to the user).
*	<math>a_j</math>: classical answer of the <math>j^\text{th}</math> server in [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf Beimel et al classical PIR scheme].
*	<math>b_j</math>: combined with the <math>a_j</math>’s, the <math>b_j</math>’s (which are known only to the user) allow the user to reconstruct the desired database element at the end of [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf Beimel et al protocol].



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

==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==
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->
===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 <math>x</math> and index <math>i</math>, the probability that the output (bit) of the protocol on the user's side is the desired database element equals <math>1</math>.
*'''User privacy''': the density matrix of each server is independent of the index <math>i</math> 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 (<math>x_j \forall j \neq i</math>) 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 <math>n^{O(\log \log (k) / k \log (k))}</math> qubits of communication.



==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
'''Inputs:'''
*	User: index of the desired database element <math>i</math>.
*	Each of the <math>k</math> servers: database <math>x</math> (an <math>n</math> bit string).
'''Output:'''
*	User: desired database element <math>x_i</math> (a single bit of <math>x</math>).
'''Protocol:'''

''This protocol works on top of [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf Beimel et al classical PIR scheme], which involves the following steps:''
*	'''Query:''' The user generates a random string <math>r</math> and <math>k</math> queries <math>q_1 (i,r),...,q_k (i,r)\in 
 \{0,1\}^t</math>. The user sends each query to the corresponding server.
*	'''Answer:''' Each server answers the user: the <math>j^\text{th}</math> server answers with classical answer <math>a_j \in \{0,1\}^{a}</math>. 
*	'''Retrieval:''' The user outputs the desired database element <math>x_i = \sum_{j=1}^k a_j \cdot b_j</math> where <math>b_j=b_j(i,r) \in \{0,1\}^{a}</math>, and all operations are modulo 2.
''Kerenidis and de Wolf quantum SPIR scheme works as follows:''
*	'''Query:'''
**	The user generates a random string <math>r</math>, <math>k</math> queries <math>q_1 (i,r),...,q_k (i,r)\in 
 \{0,1\}^t</math> and <math>k</math> random strings <math>r_1,...,r_k\in \{0,1\}^a</math>.
**	The user prepares a <math>(k+1)</math>-register state: <math>\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</math> where <math>r'_j := r_j+b_j</math> and <math>b_j=b_j (i,r)\in \{0,1\}^a</math> 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 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf Beimel et al PIR protocol]: <math>\sum_{j=1}^k a_j \cdot b_j = x_i</math>.
**	The user keeps the first <math>1</math>-qubit register and sends the other <math>k</math> registers to the corresponding server.
*	'''Answer:'''
**	Each server applies a unitary map to the received quantum register: <math>|q_j,r \rangle \rightarrow (-1)^{a_j \cdot r} |q_j,r\rangle</math> where <math>a_j=a_j (q_j,x)\in \{0,1 \}^a</math> is the classical answer of the <math>j^\text{th}</math> server to the user in [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf 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: <math>\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</math> <math>= \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</math> <math>= \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</math> <math>= (-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)</math> Hence, up to a global phase <math>(-1)^{\sum_{j=1}^k a_j \cdot r_j} </math>, this state is: <math>\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 </math>.
** To retrieve the desired database element <math>x_i</math>, the user then maps the <math>k</math> quantum registers to the ground state – this way, entanglement is destroyed, and the first qubit is in state <math>\frac{1}{\sqrt{2}}(|0\rangle+(-1)^{x_i} |1\rangle)</math>.
**Lastly, the user applies a Hadamard transform to the first qubit, which is now in state <math>|x_i\rangle</math>. Measuring in the computational basis <math>\{|0\rangle,|1\rangle\}</math> has classical outcome the desired bit <math>x_i</math>.


==Further Information==
<!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... -->
*	This quantum protocol can be based on other classical PIR schemes with the same structure as this of [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.549&rep=rep1&type=pdf 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.

<!--==References==-->

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