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.

Tags: Quantum Enhanced Classical Functionality, Specific Task, Quantum Key Distribution, Information-Theoretic Security, 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:

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

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

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta_\text{cor}} -correctness: If the user and the data centres are honest, then for any index Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and database Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-p_\text{fail})Pr[\hat{w}_x \neq w_x|\text{pass}]\leq\eta_\text{cor}} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta_{UP}} -user privacy: If the user is honest, then for any database Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} and shared secret keys between the data centres Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_5,s_6)} , and for any data centre Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_j} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta(\rho_{D_{j} E}^x,\rho_{D_{j} E}^{x'}) \leq \eta_{UP}} for all indexes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x'} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta_{DP}} -database privacy: If the data centres are honest, then for any index Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , randomness Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} and keys Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_1^\text{dec},s_2^\text{enc},s_3^\text{dec},s_4^\text{enc})} , then there exists an index Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x'} such that for all databases Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w'} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{x'}={w'}_{x'}} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} or the index of the desired database element Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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.

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta_{PS}} -protocol secrecy: If the user and the data centres are honest, then for all index-database pairs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,w)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x',w')} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\eta_\text{cor},\eta_{UP},\eta_{DP},\eta_{PS})} -secure.

A two-database one-round Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0,0,0,0)} -secure SPIR protocol with ideal keys replaced by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} -secure QKD keys, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon=\epsilon_\text{corr}+\epsilon_\text{sec}} (see QKD security definitions), can be shown to be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (3\epsilon_\text{corr},2\epsilon,2\epsilon,4\epsilon)} -secure (see Kon and Lim (2021) for a proof).

Protocol Description

Inputs:

• User Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} : index of desired database item, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X=x} ; randomness Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} ; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\text{query},1}} ,Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\text{query},2}} ,Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_\text{dec}} .
• Data centre Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_1} : database Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W=w} .
• Data centre Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_2} : database Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W=w} .

Output:

• User Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} : retrieved database element Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{w}_x} (it may be different from the desired database element Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_1} and the user Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} share secret key pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S_1,S_2)} ; data centre Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_2} and the user Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} share secret key pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S_3,S_4)} ; and data centres Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_2} share secret key pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_1=f_{\text{query},1} (x,R)} (resp. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{U1}} (resp. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{U2}} ) to data centre Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_1} (resp. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_2} ).
• Answer: After receiving query Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{Q}_1} (resp. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{Q}_2} ), data centre Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_1} (resp. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_2} ) generates answer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1=f_{\text{ans},1} (\tilde{Q}_1,w,S_5)} (resp. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_2=f_{\text{ans},2} (\tilde{Q}_2,w,S_6)} ) and sends it to the user via Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{U1}} (resp. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{U2}} ).
• Retrieval: The user decodes the received database element Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{w}_x} using Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\text{dec}}} : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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