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

This example protocol performs the task of 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 (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.

## 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:

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

• ${\displaystyle U}$: user.
• ${\displaystyle D_{i}}$: ${\displaystyle i^{\text{th}}}$ data centre.
• ${\displaystyle E}$: Eve, an eavesdropper.
• ${\displaystyle R}$: user’s local randomness (random variable); ${\displaystyle r}$: given randomness (${\displaystyle R=r}$).
• ${\displaystyle X}$: input random variable; ${\displaystyle x}$: given input (${\displaystyle X=x}$).
• ${\displaystyle W}$: database random variable; ${\displaystyle w}$: given database (${\displaystyle W=w}$).
• ${\displaystyle W_{X}}$: random variable which represents the database entry that the user wants to retrieve; ${\displaystyle w_{x}}$: given desired database entry (${\displaystyle W_{X}=w_{x}}$).
• ${\displaystyle f_{{\text{query}},i}}$: query function, used by the user to generate his query to the ${\displaystyle i^{\text{th}}}$ data centre. Input and output are random variables.
• ${\displaystyle f_{{\text{ans}},i}}$: answer function, used by the ${\displaystyle i^{\text{th}}}$ data centre to generate his answer to the user’s query. Input and output are random variables.
• ${\displaystyle f_{\text{dec}}}$: decoding function, used by the user to decode the desired database element. Input and output are random variables.
• ${\displaystyle S_{i}}$: QKD key random variable (the user has ${\displaystyle S_{2}}$ and ${\displaystyle S_{4}}$ to communicate with data centres 1 and 2 respectively; data centre 1 has ${\displaystyle S_{1}}$ and ${\displaystyle S_{5}}$ to communicate with the user and data centre 2 respectively; data centre 2 has ${\displaystyle S_{3}}$ and ${\displaystyle S_{6}}$ to communicate with the user and data centre 1 respectively); ${\displaystyle s_{i}}$: given QKD key (${\displaystyle S_{i}=s_{i}}$).
• ${\displaystyle S_{i}^{\text{enc}}}$: half of the key ${\displaystyle S_{i}}$ used for encryption (random variable); ${\displaystyle s_{i}^{\text{enc}}}$: given key (${\displaystyle S_{i}^{\text{enc}}=s_{i}^{\text{enc}}}$).
• ${\displaystyle S_{i}^{\text{dec}}}$: half of the key ${\displaystyle S_{i}}$ used for decryption (random variable); ${\displaystyle s_{i}^{\text{dec}}}$: given key (${\displaystyle S_{i}^{\text{dec}}=s_{i}^{\text{dec}}}$).
• ${\displaystyle Q_{i}}$: query generated by the user for the ${\displaystyle i^{\text{th}}}$ data centre.
• ${\displaystyle {\tilde {Q}}_{i}}$: query received by the ${\displaystyle i^{\text{th}}}$ data centre (may be different from ${\displaystyle Q_{i}}$).
• ${\displaystyle C_{Ui}}$: secure channel connecting the user with the ${\displaystyle i^{\text{th}}}$ data centre.
• ${\displaystyle A_{i}}$: reply generated by the ${\displaystyle i^{\text{th}}}$ data centre for the user after receiving ${\displaystyle {\tilde {Q}}_{i}}$.
• ${\displaystyle {\tilde {A}}_{i}}$: reply from the ${\displaystyle i^{\text{th}}}$ data centre received by the client (may be different from ${\displaystyle A_{i}}$).
• ${\displaystyle {\hat {w}}_{x}}$: database element retrieved by the user at the end of the protocol.
• ${\displaystyle p_{\text{fail}}}$: probability that at least one of the three QKD protocols aborted (${\displaystyle p_{\text{fail}}=1-(1-p_{\perp ,U1})(1-p_{\perp ,U2})(1-p_{\perp ,12})}$).
• ${\displaystyle p_{\perp ,AB}}$: probability that the QKD protocol between parties ${\displaystyle A}$ and ${\displaystyle B}$ aborts, where ${\displaystyle A,B\in \{U,1,2\}}$ (${\displaystyle U}$: user; ${\displaystyle 1}$: data centre 1; ${\displaystyle 2}$: data centre 2).
• ${\displaystyle {\text{pass}}}$: this is the event “none of the three QKD protocols aborted”.
• ${\displaystyle \Delta (.,.)}$: trace distance between two quantum systems (${\displaystyle \Delta (\rho ,\sigma )={\frac {1}{2}}||\rho -\sigma ||_{1}}$ where ${\displaystyle ||.||_{1}}$ is the trace norm).
• ${\displaystyle \rho _{UE}^{w}}$: total view of the user ${\displaystyle U}$ and the eavesdropper ${\displaystyle E}$ conditioned by ${\displaystyle w}$.
• ${\displaystyle \rho _{D_{j}E}^{x}}$: total view of data centre ${\displaystyle D_{j}}$ and the eavesdropper ${\displaystyle E}$ conditioned by ${\displaystyle x}$.
• ${\displaystyle \rho _{E}^{x,w}}$: total view of the eavesdropper ${\displaystyle E}$ conditioned by ${\displaystyle x}$ and ${\displaystyle w}$.

## 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:

• ${\displaystyle \eta _{\text{cor}}}$-correctness: If the user and the data centres are honest, then for any index ${\displaystyle x}$ and database ${\displaystyle w}$, ${\displaystyle (1-p_{\text{fail}})Pr[{\hat {w}}_{x}\neq w_{x}|{\text{pass}}]\leq \eta _{\text{cor}}}$.
• ${\displaystyle \eta _{UP}}$-user privacy: If the user is honest, then for any database ${\displaystyle w}$ and shared secret keys between the data centres ${\displaystyle (s_{5},s_{6})}$, and for any data centre ${\displaystyle D_{j}}$, ${\displaystyle \Delta (\rho _{D_{j}E}^{x},\rho _{D_{j}E}^{x'})\leq \eta _{UP}}$ for all indexes ${\displaystyle x}$ and ${\displaystyle x'}$.
• ${\displaystyle \eta _{DP}}$-database privacy: If the data centres are honest, then for any index ${\displaystyle x}$, randomness ${\displaystyle r}$ and keys ${\displaystyle (s_{1}^{\text{dec}},s_{2}^{\text{enc}},s_{3}^{\text{dec}},s_{4}^{\text{enc}})}$, then there exists an index ${\displaystyle x'}$ such that for all databases ${\displaystyle w}$ and ${\displaystyle w'}$ with ${\displaystyle w_{x'}={w'}_{x'}}$, ${\displaystyle \Delta (\rho _{UE}^{w},\rho _{UE}^{w'})\leq \eta _{DP}}$.

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 ${\displaystyle w}$ or the index of the desired database element ${\displaystyle x}$. 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.

• ${\displaystyle \eta _{PS}}$-protocol secrecy: If the user and the data centres are honest, then for all index-database pairs ${\displaystyle (x,w)}$ and ${\displaystyle (x',w')}$, ${\displaystyle \Delta (\rho _{E}^{x,w},\rho _{E}^{x',w'})\leq \eta _{PS}}$.

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 ${\displaystyle (\eta _{\text{cor}},\eta _{UP},\eta _{DP},\eta _{PS})}$-secure.

A two-database one-round ${\displaystyle (0,0,0,0)}$-secure SPIR protocol with ideal keys replaced by ${\displaystyle \epsilon }$-secure QKD keys, where ${\displaystyle \epsilon =\epsilon _{\text{corr}}+\epsilon _{\text{sec}}}$ (see QKD security definitions), can be shown to be ${\displaystyle (3\epsilon _{\text{corr}},2\epsilon ,2\epsilon ,4\epsilon )}$-secure (see Kon and Lim (2021) for a proof).

## Protocol Description

Inputs:

• User ${\displaystyle U}$: index of desired database item, ${\displaystyle X=x}$; randomness ${\displaystyle R}$; ${\displaystyle f_{{\text{query}},1}}$,${\displaystyle f_{{\text{query}},2}}$,${\displaystyle f_{\text{dec}}}$.
• Data centre ${\displaystyle D_{1}}$: database ${\displaystyle W=w}$.
• Data centre ${\displaystyle D_{2}}$: database ${\displaystyle W=w}$.

Output:

• User ${\displaystyle U}$: retrieved database element ${\displaystyle {\hat {w}}_{x}}$ (it may be different from the desired database element ${\displaystyle w_{x}}$ in the case of malicious parties).

Protocol:

• Sharing secret keys between parties: each pair of parties perform a single-round quantum key distribution protocol (see e.g., MDI-QKD and this specific protocol), so that at the end of the secret sharing phase, data centre ${\displaystyle D_{1}}$ and the user ${\displaystyle U}$ share secret key pair ${\displaystyle (S_{1},S_{2})}$; data centre ${\displaystyle D_{2}}$ and the user ${\displaystyle U}$ share secret key pair ${\displaystyle (S_{3},S_{4})}$; and data centres ${\displaystyle D_{1}}$ and ${\displaystyle D_{2}}$ share secret key pair ${\displaystyle (S_{5},S_{6})}$. 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 Gertner et al (2000).

• Query: Query ${\displaystyle Q_{1}=f_{{\text{query}},1}(x,R)}$ (resp. ${\displaystyle Q_{2}=f_{{\text{query}},2}(x,R)}$) is generated by the user and sent via QKD-secured (one-time pad encryption with QKD shared secret keys) classical channel ${\displaystyle C_{U1}}$ (resp. ${\displaystyle C_{U2}}$) to data centre ${\displaystyle D_{1}}$ (resp. ${\displaystyle D_{2}}$).
• Answer: After receiving query ${\displaystyle {\tilde {Q}}_{1}}$ (resp. ${\displaystyle {\tilde {Q}}_{2}}$), data centre ${\displaystyle D_{1}}$ (resp. ${\displaystyle D_{2}}$) generates answer ${\displaystyle A_{1}=f_{{\text{ans}},1}({\tilde {Q}}_{1},w,S_{5})}$ (resp. ${\displaystyle A_{2}=f_{{\text{ans}},2}({\tilde {Q}}_{2},w,S_{6})}$) and sends it to the user via ${\displaystyle C_{U1}}$ (resp. ${\displaystyle C_{U2}}$).
• Retrieval: The user decodes the received database element ${\displaystyle {\hat {w}}_{x}}$ using ${\displaystyle f_{\text{dec}}}$: ${\displaystyle {\hat {w}}_{x}=f_{\text{dec}}({\tilde {A}}_{1},{\tilde {A}}_{2},Q_{1},Q_{2},x,R)}$.

## 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 Gertner et al (2000)).
• With current QKD technology, this SPIR protocol is feasible, as shown by Kon and Lim (2021).

*contributed by Marine Demarty