Quantum Protocol Zoo - User contributions [en]

Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness

2021-07-28T09:03:17Z

Marine: Created a new page for Multi-Database QSPIR without Shared Randomness

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:'''
[[: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==

* 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 <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==

* <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].





==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 <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==

'''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==

* 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.



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

(Symmetric) Private Information Retrieval

2021-07-27T14:01:57Z

Marine: Added a "Optimal communication complexity of the (Q)(S)PIR problem" subsection in "Further Information" section + some minor edit on OT

==Description==

Private information retrieval (PIR) is a classical cryptographic functionality that allows one party (user) to privately retrieve an element from a classical database owned by another party (server), i.e., without revealing to the other party which element is being retrieved (user privacy).<br></br>
Symmetric private information (SPIR) retrieval is PIR with the additional requirement that throughout and after the protocol, the user remains oblivious to other database elements, i.e., apart from the queried one (data privacy).<br></br>
In the quantum setting, the use of quantum systems is allowed to achieve (S)PIR: this may imply the use of a quantum channel between the user and the server, and the capability to prepare quantum states, apply quantum gates or measure quantum systems by one or both parties. (S)PIR in this setting is known as quantum (symmetric) private information retrieval (Q(S)PIR).<br></br>
In the classical or quantum setting, (Q)SPIR and one-out-of-n (quantum) [[Oblivious Transfer|oblivious transfer]] (OT) are similar cryptographic tasks; the only minor difference between those functionalities is that protocols for OT are two-party protocols, while attempts at achieving SPIR have considered both two-party and multi-party protocols where the user communicates with several servers, each holding a copy of the database.<br></br>
Apart from using quantum techniques to enhance the classical (S)PIR functionality (i.e., design better protocols than their classical counterparts in terms of different metrics like e.g., communication complexity), there has also been a recent interest in a ‘fully’ quantum (S)PIR where a user wants to query a quantum database (items are quantum states)[[#References|[1]]].<br></br>

'''Tags:'''
[[:Category:Two Party Protocols|Two Party Protocol]],[[Category:Two Party Protocols]]
[[:Category:Specific Task|Specific Task]], [[Category:Specific Task]]
[[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]].[[Category:Quantum Enhanced Classical Functionality]]



==Properties==


===Security definitions===
(Quantum) private information retrieval protocols are said to be secure if they satisfy the following conditions:
*'''Correctness''': assuming that all the parties in the protocol are honest, then the output of the protocol on the user’s side must be the queried database element.
*'''User privacy''': assuming that the user is honest, then, throughout the protocol, any query of the user to a server leaks no information about the desired database item.
In addition to the above requirements, symmetric (quantum) private information retrieval protocols must also satisfy the following condition:
*'''Data(base) privacy''': assuming that the server(s) is (are) honest(s), then, throughout the protocol, the user is unable to obtain any information beyond a single database element.

===Cost parameters===
The most common cost parameter used to characterise a given (Q)(S)PIR protocol is:
*'''Communication complexity''': total number of (qu)bits exchanged between the user and the server(s) throughout the protocol.
For (Q)(S)PIR protocols in general:
*'''(Q)(S)PIR capacity''': maximal achievable ratio of the retrieved database element size to the total download size.
Some less common cost parameters include:
*'''Storage overhead''' (for multi-database (Q)(S)PIR protocols): ratio between the total number of (qu)bits stored on all servers and the number of (qu)bits in the (resp. quantum) classical database.
*'''Access complexity''': total amount of data to be accessed by the server(s) for answering queries throughout a (Q)(S)PIR protocol.

==Protocols==


===Classical database===
In the quantum setting, protocols aiming at achieving (S)PIR for a ''classical'' database fall into two main categories:
====Single-database protocols====
As in the classical setting, in the case of the database being owned by a ''single'' server, the trivial solution (downloading the whole database) is the only way to achieve information-theoretically secure PIR – even in the case of a specious (may deviate from the protocol if its malicious operations are unknown to the user) server [[#References|[2]]]. <br>
As for (quantum or classical) SPIR, it is impossible to achieve information-theoretic security with a single-server; this result was proved in the quantum setting by Lo [[#References|[3]]]. Intuitively, this comes from the fact that the (unique) trivial solution of information-theoretically secure PIR is the worst in terms of data privacy. Therefore, to design efficient PIR protocols or to achieve SPIR, several assumptions have been considered; they include:
* Hardness assumptions: PIR protocols with computational security.
* Assumptions on the adversarial model:
** to achieve SPIR: cheat-sensitive protocols (also known as quantum private queries (QPQ) protocols) where it is assumed that the server will not cheat if there is a non-zero probability that he will be caught cheating.
***[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution|QPQ protocols based on quantum oblivious key distribution]]
***[[Quantum Private Queries Protocol Based on Quantum Random Access Memory|QPQ protocols based on quantum random access memory]]
** to achieve efficient PIR: assuming an honest server.
***[[Single-Database Quantum Private Information Retrieval in the Honest Server Model|QPIR protocols in the honest server model]]
* Prior shared entanglement between server and user: in the honest server model, efficient PIR protocols exist, however for a specious or malicious server, the trivial solution is optimal for PIR[[#References|[4]]].
**[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model|QPIR protocols with prior shared entanglement in the honest server model]]
* Relativistic assumptions: quantum SPIR protocols whose security uses properties from special relativity.
**[[Relativistic Quantum Oblivious Transfer|Relativistic QOT protocols]]

====Multi-database protocols====
It is possible to achieve information-theoretic (S)PIR with reduced communication complexity (i.e., compared to this of the trivial solution) by considering several servers instead of one, each holding a copy of the database, and with the help of extra assumptions. Usually, to achieve (S)PIR, it is assumed that the servers cannot communicate with each other during and after the protocol ended (no-communication assumption), and that servers share randomness (in the symmetric case only). Examples of such protocols are:

* [[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness|Quantum multi-database SPIR protocols without shared randomness]] (replaced by prior shared entanglement between servers)
* [[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution|Classical multi-database SPIR protocols with QKD secured classical channels]]
* [[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers|Multi-database quantum (S)PIR protocols for communicating and colluding servers]] – to do without the no-communication assumption
* [[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers|Multi-database quantum (S)PIR protocols for coded servers]]

===Quantum database===
For the case of a ''quantum'' database, the trivial solution of downloading the whole database is proved to be optimal for one-round QPIR, and for multi-round QPIR in the blind setting (i.e., the servers do not have a classical description of the quantum states of the database) and for the honest server model (and any other attack model)[[#References|[1]]].<br>

Prior shared entanglement between the user and the server allows for efficient one-server QPIR protocols in the honest server model and in the blind setting. Multi-database QSPIR protocols for a quantum database with pure states, in the visible setting (servers know a classical description of the quantum database elements) exist as shown by Song and Hayashi [[#References|[1]]].

* [[Single-Database Quantum Private Information Retrieval for a Quantum Database|Single-database quantum PIR protocols in the honest server model and in the blind setting for a quantum database]]
* [[Multi-Database Quantum Symmetric Private Information Retrieval for a Quantum Database|Multi-database quantum SPIR protocols in the visible setting for a quantum database]]

==Use-cases==

===Classical database===
*Location-based services (to protect user location privacy).
*Queries of electronic medical records (these require decades of information confidentiality; hence security against quantum computing based attacks is necessary) or medical test reports.
*Music and film streaming (user does not want his/her tastes to be revealed to the server).
*Pay-per-view services, where the user should pay a fee to access every single database element.

Quantum (S)PIR protocols may be preferred to their classical counterparts to:
*Achieve (S)PIR with better communication complexity: this is convenient in the case of large databases.
*Achieve (S)PIR with better security: for instance, to secure classical channels as in [[#References|[5]]].

==Further Information==

===Optimal communication complexity of the (Q)(S)PIR problem===
Below are summarised known bounds for the communication complexity of information-theoretically secure (S)PIR protocols in the classical and quantum settings, for a quantum or classical database.

*<math>f</math> : number of database elements (quantum states in the 'fully' quantum setting)
*<math>m</math> : total size of database elements (i.e., the sum of the sizes, in bits, of each database element)
*<math>d</math> : dimension of the quantum states stored in the quantum database (<math>d=2</math> if they are qubits)
*<math>k</math> : number of servers (or equivalently of replicated databases)

====Single-database case====
{| class="wikitable plainrowheaders"
! scope="col" | Problem
! scope="col" | Additional assumptions
! scope="col" | Optimal communication complexity
! scope="col" | Reference
|-
! scope="row" | Classical PIR
| || <math>\Theta(m)</math> || [http://www.wisdom.weizmann.ac.il/~oded/PSX/pir2.pdf Chor et al (1995)]
|-
! scope="row" | Classical SPIR
| || NA (impossible) ||
|-
! scope="row" rowspan="4" | Quantum PIR (Classical database)
| Specious server || <math>\Theta(m)</math> || [https://arxiv.org/pdf/1304.5490.pdf Baumeler and Broadbent (2015)]
|-
| Specious server & prior entanglement || <math>\Theta(m)</math> || [https://arxiv.org/pdf/1902.09768.pdf Aharonov et al (2019)]
|-
| Honest server || <math>O(poly \log (m))</math> || [https://repository.ubn.ru.nl/bitstream/handle/2066/155747/155747.pdf Kerenidis et al (2016)]
|-
| Honest server & prior entanglement || <math>O(\log (m))</math> || [https://repository.ubn.ru.nl/bitstream/handle/2066/155747/155747.pdf Kerenidis et al (2016)]
|-
! scope="row" rowspan="2" | Quantum SPIR (Classical database)
| || NA (impossible) || [https://arxiv.org/pdf/quant-ph/9611031.pdf Lo (1997)]
|-
| The server will not cheat if there is a non-zero probability of being caught cheating & imperfect data privacy (the user should get at most two database items) || <math>O(\log (m))</math> || [https://arxiv.org/pdf/0708.2992.pdf Giovannetti et al (2008)]
|-
! scope="row" rowspan="3" | Quantum PIR (Quantum database)
| Honest server & blind setting || <math>\Theta(m)</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
|-
| Honest server & visible setting || <math>\Theta(m)</math> (for one-round) || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
|-
| Honest server & prior entanglement || <math>O(\log (m))</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
|-
! scope="row" | Quantum SPIR (Quantum database)
| || ||
|}

====Multi-database case====
{| class="wikitable plainrowheaders"
! scope="col" | Problem
! scope="col" | Additional assumptions
! scope="col" | Optimal communication complexity
! scope="col" | Reference
|-
! scope="row" | Classical PIR
| || ||
|-
! scope="row" | Classical SPIR
| Servers do not communicate with each other & secure classical channels || <math>O(m^{\frac{1}{2k-1}}) \text{ bits}</math> || [https://dl.acm.org/doi/abs/10.1145/276698.276723 Gertner et al (2000)]
|-
! scope="row" | Quantum PIR (Classical database)
| || ||
|-
! scope="row" rowspan="2" | Quantum SPIR (Classical database)
| Servers do not communicate with each other || <math>O(m^{\frac{1}{2k-1}}) \text{ bits}+ \text{ comm. complexity of QKD}</math> || [https://www.mdpi.com/1099-4300/23/1/54/htm Kon and Lim (2021)]
|-
| Servers do not communicate with each other & honest user & prior entanglement || <math>m^{O(\log \log (k)/k \log(k))}</math> || [https://arxiv.org/pdf/quant-ph/0307076.pdf Kerenidis and de Wolf (2004)]
|-
! scope="row" | Quantum PIR (Quantum database)
| || ||
|-
! scope="row" rowspan="3" | Quantum SPIR (Quantum database)
| Servers do not communicate with each other & prior entanglement & visible setting & database contains pure qubit states || <math>O(f) \text{ bits} + O(1) \text{ qubits} + O(1) \text{ ebits}</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
|-
| Servers do not communicate with each other & prior entanglement & visible setting & database contains pure qudit states || <math>O(f) \text{ bits} + O(d^d \log (d)) \text{ qubits} + O(d^d \log (d)) \text{ ebits}</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
|-
| Servers do not communicate with each other & prior entanglement & visible setting & database contains commutative unitaries || <math>O(f) \text{ bits} + O(\log (d)) \text{ qubits} + O(\log (d)) \text{ ebits}</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
|}

==References==
#[https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
#[https://arxiv.org/pdf/1304.5490.pdf Baumeler and Broadbent (2015)]
#[https://arxiv.org/pdf/quant-ph/9611031.pdf Lo (1997)]
#[https://arxiv.org/pdf/1902.09768.pdf Aharonov et al (2019)]
#[https://www.mdpi.com/1099-4300/23/1/54/htm Kon and Lim (2021)]

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

Protocol Library

2021-07-27T12:09:51Z

Marine: Added links to pages related to (Symmetric) Private Information Retrieval

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="2"|[[Authentication of Classical Messages]]||[[]]
|-
|[[Uncloneable Encryption]]
|-
|rowspan="2"|[[Authentication of Quantum Messages]]||[[]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|[[Verification of Universal Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of Sub-Universal Quantum Computation]]||[[-]]
|-
|[[Verification of NP-complete problems]]||[[-]]
|-
|[[Classical Verification of Universal Quantum Computation]]||[[-]]
|-
|rowspan="4"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
||-||[[Weak String Erasure]]

Quantum Private Queries Protocol Based on Quantum Random Access Memory

2021-07-26T15:49:15Z

Marine: Created a new page for QPQ Based on Quantum Random Access Memory

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:''' [[: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==

* 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 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==

* <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>.





==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==

* '''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==

'''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==

* 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)].


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

Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution

2021-07-26T13:53:07Z

Marine: Creating a new page for QPQ Based on Quantum Oblivious Key Distribution

This [https://arxiv.org/pdf/1002.4360.pdf example protocol] performs the task of [[(Symmetric) Private Information Retrieval|symmetric private information retrieval]] (SPIR) and has information-theoretic security. It is based on a [[Quantum Oblivious Key Distribution|quantum oblivious key distribution]] scheme. Like any quantum private queries protocol, it is cheat-sensitive, in the sense that user privacy relies on the non-zero probability for a cheating server to be detected. As for data privacy, the amount of information accessed by the user about the database is bounded.


'''Tags:''' [[:Category:Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category:Specific Task|Specific Task]], [[:Category:Two Party Protocols|Two Party Protocol]], [[Information-Theoretic Security]], [[(Symmetric) Private Information Retrieval|Symmetric Private Information Retrieval]], [[Quantum Private Queries]], [[Quantum Key Distribution]], [[Quantum Oblivious Key Distribution]], [[Single-Database]].

==Assumptions==

The security of this protocol relies on fundamental physics principles:
* Impossibility of superluminal communication (for user privacy).
* Impossibility to deterministically discriminate non-orthogonal states (for database privacy).
To achieve ''perfect'' user privacy, one must make the following assumption:
* The server (Bob) will not cheat if he has a non-zero probability of being caught cheating.

==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).''<br></br>
*'''Quantum oblivious key distribution:''' Alice and Bob perform a [[Quantum Key Distribution|quantum key distribution]] (QKD) protocol in such a way that at the end of the protocol, Alice and Bob share a bit string known entirely to Bob and in a quarter to Alice: such a protocol is referred to as [[Quantum Oblivious Key Distribution|quantum ''oblivious'' key distribution]]. Then the key length is reduced to match the size of the database, while ensuring that Alice knows approximately one bit of the new key (the position of the known bit is unknown to Bob).<br></br>
*'''Query:''' Alice announces to Bob a (classical) shift corresponding to the difference between the index of the known bit of the key and the index of the desired database element.<br></br>
*'''Answer:''' Bob encodes the database by bitwise adding the key, shifted by Alice’s shift. Then Bob announces the encoded database.<br></br>
*'''Retrieval:''' By adding bitwise the shifted key to the encoded database, Alice can recover each database element for which she knew the corresponding (shifted) bit of the key.

==Notation==

* <math>N</math>: number of elements in the database.
* <math>X</math>: database; <math>X_n</math>: <math>n^\text{th}</math> database element.
* <math>i</math>: index of the desired database element
* <math>j</math>: index of a bit of the QKD key known to Alice.
* <math>k</math>: a security parameter for the QKD key.
* <math>|\uparrow\rangle,|\downarrow\rangle,|\leftarrow\rangle,|\rightarrow\rangle</math>: [[BB84 Quantum Key Distribution|BB84]] states.
* <math>\updownarrow</math>: <math>\{|\uparrow\rangle,|\downarrow\rangle\}</math> basis.
* <math>\leftrightarrow</math>: <math>\{|\leftarrow\rangle,|\rightarrow\rangle\}</math> basis.
* <math>K^f</math>: key used to encode the database; it is a random bit string of length <math>N</math>.
* <math>C</math>: encoded database (by bitwise adding the shifted QKD key).




==Requirements==
'''User''' (Alice):
* Can measure single qubits.
'''Server''' (Bob):
* Can prepare single qubits.
'''Communication''':
* A quantum channel.
* A classical authenticated channel.

==Properties==

* '''User privacy''': In the case of an honest server (Bob), there is perfect user privacy as Alice never communicates about the index of her known bit of the key. However, there are strategies that allow a malicious server to infer which bit of the key is known to Alice; but any such strategy implies a loss of knowledge on the bit value of this specific key element, and so Bob may introduce errors in the encoding of the database that would automatically be detected by Alice. Hence, assuming that the server will not cheat if there is a non-zero probability of being caught cheating, this protocol ensures perfect user privacy.<br></br>
* '''Data privacy''': An honest Alice may know more than one bit of the final QKD key as the number of bits known to her is probabilistic; this means she could access as many extra database elements with certainty as the number of extra bits of the key that she knows. Moreover, for any other database elements whose encoding is unknown to an honest Alice, she has a 50% chance of guessing correctly the corresponding key element. There are some cheating strategies that increase this probability; however, its increase is constrained by the choice of the security parameter <math>k</math>. Lastly, it is important to note that a cheating Alice cannot be detected by Bob.

==Protocol Description==

'''Inputs:'''
* User (Alice): index <math>i</math> of the desired database element.
* Server (Bob): classical database <math>X</math> with <math>N</math> elements: <math>X_1,...,X_N</math>.
* Both (Alice & Bob): a security parameter <math>k</math>.
'''Output:'''
* User (Alice): desired database element <math>X_i</math>.
'''Protocol:'''
* '''Quantum oblivious key distribution:'''
# Bob generates a random bit string of length <math>k\times N</math>.
# Bob encodes each bit of the string in the state of a qubit belonging to one of two bases <math>\updownarrow := \{|\uparrow\rangle ,|\downarrow \rangle \}</math> or <math>\leftrightarrow :=\{|\leftarrow\rangle,|\rightarrow\rangle\}</math>: for each bit, if it is <math>0</math>, Bob chooses between <math>|\uparrow\rangle</math> and <math>|\downarrow\rangle</math>, if it is <math>1</math>, Bob chooses between <math>|\leftarrow\rangle</math> and <math>|\rightarrow\rangle</math>.
# Bob sends the prepared qubits to Alice.
# Alice measures each state in the <math>\updownarrow </math> basis or <math>\leftrightarrow </math> basis at random.
# Alice announces to Bob in which instances she detected the sent qubit.
# For each qubit that Alice successfully detected, Bob announces a pair of two states including the state that was sent. The other state is chosen at random in the other basis.
# Partial reconstruction of the key: Using her measurement outcomes and Bob’s announced pairs of qubits, Alice can deduce the bit value of part of the key (<math>1/4</math> of conclusive results).

''At this stage, Alice and Bob share a secret key of length <math>k\times N</math> which is known partially (<math>{1/4}^\text{th}</math>) to Alice and entirely to Bob. Bob does not know which bits of the key are known to Alice.''

# Reduction of the key length: The key is cut into <math>k</math> substrings of length <math>N</math>. Then pieces of the key are added bitwise to create a new key of length <math>N</math>, <math>K^f</math>. This reduces the number of bits of the new key that Alice knows to roughly one bit (ideally, Alice should know exactly one bit of the new key).
*'''Query:''' Alice announces to Bob a shift <math>s=j-i</math> where <math>i</math> is the index of the desired database element and <math>j</math> is the index of a bit of the key known to Alice.
*'''Answer:''' Bob announces to Alice <math>N</math> bits <math>C_n=X_n\oplus K_{n+s}^f</math> corresponding to the encoded database.
*'''Retrieval:''' Alice recovers the desired database element <math>X_i</math> by adding her known bit of the key, <math>K_j^f</math> to the <math>i^\text{th}</math> received bit <math>C_i</math>: <math>C_i\oplus K_j^f=X_i\oplus K_{i+s}^f\oplus K_j^f=X_i\oplus K_{i+j-i}^f\oplus K_j^f=X_i</math>.

==Further Information==

* The QKD part of this quantum private queries protocol is based on the [https://arxiv.org/pdf/quant-ph/0211131.pdf SARG04 QKD scheme]. However, any QKD protocol that is compatible with the SARG04 scheme would work.
* This protocol is loss resistant and scalable to large databases.



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

Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution

2021-07-26T10:31:46Z

Marine: Minor edit

This [https://www.mdpi.com/1099-4300/23/1/54/htm example protocol] performs the task of [[(Symmetric) Private Information Retrieval|symmetric private information retrieval]] (SPIR) and has unconditional security (a.k.a. information-theoretic security). It is a quantum multi-database one-round protocol, based on a classical multi-database SPIR protocol, that uses [[Quantum Key Distribution|quantum key distribution]] (QKD) to share randomness between servers and to secure classical channels between the user and the servers, and thus do without the assumption of perfectly secured channels of classical multi-database SPIR protocols.


'''Tags:''' [[:Category:Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category:Specific Task|Specific Task]], [[Quantum Key Distribution]], [[Information-Theoretic Security]], [[(Symmetric) Private Information Retrieval|Symmetric Private Information Retrieval]], [[Multi-Database]], [[One-Round Protocol]].

==Assumptions==

*'''All parties:''' All parties have a trusted random number generator and all QKD devices are honest. All messages sent through the classical channels are encrypted with a classical one-time pad.
*'''Data centres:''' Data centres are not allowed to communicate after the key exchange step. They do not leak QKD keys intentionally to other parties.

==Outline==

Outline for a generic one-round two-database SPIR protocol with QKD:<br></br>
''There are three parties, a user and two data centres. Each data centre has a copy of the database. In symmetric private information retrieval, the user wants to retrieve an element from a database owned by another party (here, two other parties: data centres 1 and 2) without revealing which element is retrieved; the user should not have access to other database elements.''
* '''Sharing secret keys between parties:''' At the beginning of the protocol, for each pair of parties (i.e., user and data centre 1, data centre 1 and data centre 2, user and data centre 2), shared secret keys are established via a single round of [[Quantum Key Distribution|quantum key distribution]]. If any of the key distribution protocols abort, then the whole SPIR protocol aborts.

The next steps are the same as these of a generic one-round two-database classical SPIR protocol.

* '''Query:''' Then, the user generates two queries; one for each data centre. Queries are some encryptions of the index of the desired database element using some local randomness.
* '''Answer:''' From the queries received, their copy of the database, and their secret key shared with the user, each data centre generates an answer and sends it to the user.
* '''Retrieval:''' Lastly, the user can reconstruct the desired database element from the answers of each datacentre and his own inputs.

==Notation==

* <math>U</math>: user.
* <math>D_i</math>: <math>i^{\text{th}}</math> data centre.
* <math>E</math>: Eve, an eavesdropper.
* <math>R</math>: user’s local randomness (random variable); <math>r</math>: given randomness (<math>R=r</math>).
* <math>X</math>: input random variable; <math>x</math>: given input (<math>X=x</math>).
* <math>W</math>: database random variable; <math>w</math>: given database (<math>W=w</math>).
* <math>W_X</math>: random variable which represents the database entry that the user wants to retrieve; <math>w_x</math>: given desired database entry (<math>W_X=w_x</math>).
* <math>f_{\text{query},i}</math>: query function, used by the user to generate his query to the <math>i^{\text{th}}</math> data centre. Input and output are random variables.
* <math>f_{\text{ans},i}</math>: answer function, used by the <math>i^{\text{th}}</math> data centre to generate his answer to the user’s query. Input and output are random variables.
* <math>f_{\text{dec}}</math>: decoding function, used by the user to decode the desired database element. Input and output are random variables.
* <math>S_i</math>: QKD key random variable (the user has <math>S_2</math> and <math>S_4</math> to communicate with data centres 1 and 2 respectively; data centre 1 has <math>S_1</math> and <math>S_5</math> to communicate with the user and data centre 2 respectively; data centre 2 has <math>S_3</math> and <math>S_6</math> to communicate with the user and data centre 1 respectively); <math>s_i</math>: given QKD key (<math>S_i=s_i</math>).
* <math>S_i^\text{enc}</math>: half of the key <math>S_i</math> used for encryption (random variable); <math>s_i^\text{enc}</math>: given key (<math>S_i^\text{enc}=s_i^\text{enc}</math>).
* <math>S_i^\text{dec}</math>: half of the key <math>S_i</math> used for decryption (random variable); <math>s_i^\text{dec}</math>: given key (<math>S_i^\text{dec}=s_i^\text{dec}</math>).
* <math>Q_i</math>: query generated by the user for the <math>i^{\text{th}}</math> data centre.
* <math>\tilde{Q}_i</math>: query received by the <math>i^{\text{th}}</math> data centre (may be different from <math>Q_i</math>).
* <math>C_{Ui}</math>: secure channel connecting the user with the <math>i^{\text{th}}</math> data centre.
* <math>A_i</math>: reply generated by the <math>i^{\text{th}}</math> data centre for the user after receiving <math>\tilde{Q}_i</math>.
* <math>\tilde{A}_i</math>: reply from the <math>i^{\text{th}}</math> data centre received by the client (may be different from <math>A_i</math>).
* <math>\hat{w}_x</math>: database element retrieved by the user at the end of the protocol.
* <math>p_\text{fail}</math>: probability that at least one of the three QKD protocols aborted (<math>p_\text{fail}=1-(1-p_{\perp,U1})(1-p_{\perp,U2})(1-p_{\perp,12})</math>).
* <math>p_{\perp,AB}</math>: probability that the QKD protocol between parties <math>A</math> and <math>B</math> aborts, where <math>A,B\in\{U,1,2\}</math> (<math>U</math>: user; <math>1</math>: data centre 1; <math>2</math>: data centre 2).
* <math>\text{pass}</math>: this is the event “none of the three QKD protocols aborted”.
* <math>\Delta(.,.)</math>: trace distance between two quantum systems (<math>\Delta(\rho,\sigma)=\frac{1}{2} ||\rho-\sigma||_1</math> where <math>||.||_1</math> is the trace norm).
* <math>\rho_{UE}^w</math>: total view of the user <math>U</math> and the eavesdropper <math>E</math> conditioned by <math>w</math>.
* <math>\rho_{D_j E}^x</math>: total view of data centre <math>D_j</math> and the eavesdropper <math>E</math> conditioned by <math>x</math>.
* <math>\rho_E^{x,w}</math>: total view of the eavesdropper <math>E</math> conditioned by <math>x</math> and <math>w</math>.




==Requirements==
* Quantum channels to perform QKD between parties.
* Classical authenticated channels.
* QKD devices to prepare and measure qubits.

==Properties==

For this protocol, SPIR security definitions (see [[(Symmetric) Private Information Retrieval]]) are extended as follow:
* <math>\eta_\text{cor}</math>-'''correctness''': If the user and the data centres are honest, then for any index <math>x</math> and database <math>w</math>, <math>(1-p_\text{fail})Pr[\hat{w}_x \neq w_x|\text{pass}]\leq\eta_\text{cor}</math>.
* <math>\eta_{UP}</math>-'''user privacy''': If the user is honest, then for any database <math>w</math> and shared secret keys between the data centres <math>(s_5,s_6)</math>, and for any data centre <math>D_j</math>, <math>\Delta(\rho_{D_{j} E}^x,\rho_{D_{j} E}^{x'}) \leq \eta_{UP}</math> for all indexes <math>x</math> and <math>x'</math>.
* <math>\eta_{DP}</math>-'''database privacy''': If the data centres are honest, then for any index <math>x</math>, randomness <math>r</math> and keys <math>(s_1^\text{dec},s_2^\text{enc},s_3^\text{dec},s_4^\text{enc})</math>, then there exists an index <math>x'</math> such that for all databases <math>w</math> and <math>w'</math> with <math>w_{x'}={w'}_{x'}</math>, <math>\Delta(\rho_{UE}^w,\rho_{UE}^{w'}) \leq \eta_{DP}</math>.
In addition to the above extended SPIR security definitions, the notion of protocol secrecy is added which allows to bound the amount of information that an external eavesdropper may obtain on the database <math>w</math> or the index of the desired database element <math>x</math>. This extra definition is required for this protocol as it relies on practical QKD protocols, which means that there is a non-zero probability that an eavesdropper may learn part of the QKD keys.
* <math>\eta_{PS}</math>-'''protocol secrecy''': If the user and the data centres are honest, then for all index-database pairs <math>(x,w)</math> and <math>(x',w')</math>, <math>\Delta(\rho_{E}^{x,w},\rho_{E}^{x',w'}) \leq \eta_{PS}</math>.
Those extended security definitions result from the possibility of unperfect QKD keys and the non-zero probability that one of the three QKD protocols may abort.

A SPIR protocol that satisfies the four above conditions is said to be <math>(\eta_\text{cor},\eta_{UP},\eta_{DP},\eta_{PS})</math>-'''secure'''.<br></br>
A two-database one-round <math>(0,0,0,0)</math>-secure SPIR protocol with ideal keys replaced by <math>\epsilon</math>-secure QKD keys, where <math>\epsilon=\epsilon_\text{corr}+\epsilon_\text{sec}</math> (see [[Quantum Key Distribution#Properties|QKD security definitions]]), can be shown to be <math>(3\epsilon_\text{corr},2\epsilon,2\epsilon,4\epsilon)</math>-secure (see [https://www.mdpi.com/1099-4300/23/1/54/htm Kon and Lim (2021)] for a proof).

==Protocol Description==

'''Inputs:'''
* User <math>U</math>: index of desired database item, <math>X=x</math>; randomness <math>R</math>; <math>f_{\text{query},1}</math>,<math>f_{\text{query},2}</math>,<math>f_\text{dec}</math>.
* Data centre <math>D_1</math>: database <math>W=w</math>.
* Data centre <math>D_2</math>: database <math>W=w</math>.
'''Output:'''
* User <math>U</math>: retrieved database element <math>\hat{w}_x</math> (it may be different from the desired database element <math>w_x</math> in the case of malicious parties).
'''Protocol:'''
* '''Sharing secret keys between parties:''' each pair of parties perform a single-round [[Quantum Key Distribution|quantum key distribution]] protocol (see e.g., [[Measurement Device Independent Quantum Key Distribution (MDI-QKD)|MDI-QKD]] and [https://www.nature.com/articles/ncomms4732 this] specific protocol), so that at the end of the secret sharing phase, data centre <math>D_1</math> and the user <math>U</math> share secret key pair <math>(S_1,S_2)</math>; data centre <math>D_2</math> and the user <math>U</math> share secret key pair <math>(S_3,S_4)</math>; and data centres <math>D_1</math> and <math>D_2</math> share secret key pair <math>(S_5,S_6)</math>. If any of the key distribution protocols abort, then the whole SPIR protocol aborts.

''The next steps are the same as for a generic one-round two-database classical SPIR protocol like this of [https://dl.acm.org/doi/abs/10.1145/276698.276723 Gertner et al (2000)].''

* '''Query:''' Query <math>Q_1=f_{\text{query},1} (x,R)</math> (resp. <math>Q_2=f_{\text{query},2} (x,R)</math>) is generated by the user and sent via QKD-secured (one-time pad encryption with QKD shared secret keys) classical channel <math>C_{U1}</math> (resp. <math>C_{U2}</math>) to data centre <math>D_1</math> (resp. <math>D_2</math>).
* '''Answer:''' After receiving query <math>\tilde{Q}_1</math> (resp. <math>\tilde{Q}_2</math>), data centre <math>D_1</math> (resp. <math>D_2</math>) generates answer <math>A_1=f_{\text{ans},1} (\tilde{Q}_1,w,S_5)</math> (resp. <math>A_2=f_{\text{ans},2} (\tilde{Q}_2,w,S_6)</math>) and sends it to the user via <math>C_{U1}</math> (resp. <math>C_{U2}</math>).
* '''Retrieval:''' The user decodes the received database element <math>\hat{w}_x</math> using <math>f_{\text{dec}}</math>: <math>\hat{w}_x=f_\text{dec} (\tilde{A}_1,\tilde{A}_2,Q_1,Q_2,x,R)</math>.

==Further Information==

* This protocol is a one-round protocol where there is a single round of query from the user to the data centres and a single round of answer from the data centres to the user. It can be extended to multi-round protocols by simply allowing several successive rounds of queries and answers.
* Classical multi-database SPIR protocols require pre-shared secret keys between parties: to secure communication between user and data centres, and between data centres to achieve data privacy (private shared randomness between data centres is a key element to accomplish the task of conditional disclosure of secrets (CDS) as introduced by [https://dl.acm.org/doi/abs/10.1145/276698.276723 Gertner et al (2000)]).
* With current QKD technology, this SPIR protocol is feasible, as shown by [https://www.mdpi.com/1099-4300/23/1/54/htm Kon and Lim (2021)].



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

Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution

2021-07-26T10:27:43Z

Marine: Creating a new page for Multi-Database Classical SPIR with QKD

(Symmetric) Private Information Retrieval

2021-07-25T15:26:54Z

Marine: Adding some use-cases

(Symmetric) Private Information Retrieval

2021-07-13T12:42:28Z

Marine: Creating a new page for Private Information Retrieval