Revision History for: Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography
- 2026-04-06 at 20:57 by kimworrall
implements (Symmetric) Private Information Retrieval
Introduction
This protocol [1] implements 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. It uses quantum key distribution (QKD) to share randomness between servers and to secure classical channels between the user and the servers, and thus does not need the assumption of perfectly secure channels that classical multi-database SPIR protocols rely on.
Related Paper(s)
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, from 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 an encryption of the index of the desired database element using 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: Finally, the user can reconstruct the desired database element from the answers of each data centre and his own inputs.
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.
Requirements
- Quantum channels to perform QKD between parties.
- Classical authenticated channels.
- QKD devices to prepare and measure qubits.
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.
- $A_i$: reply generated by the $i^{\\\text{th}}$ data centre for the user after receiving $\\\tilde{Q}_i$.
- $\\\tilde{A}_i$: reply from the $i^{\\\text{th}}$ data centre received by the client (may be different from $A_i$).
- $\\\hat{w}_x$: database element retrieved by the user at the end of the protocol.
- $p_\\\text{fail}$: probability that at least one of the three QKD protocols aborted ($p_\\\text{fail}=1-(1-p_{\\\perp,U1})(1-p_{\\\perp,U2})(1-p_{\\\perp,12})$).
- $p_{\\\perp,AB}$: probability that the QKD protocol between parties $A$ and $B$ aborts, where $A,B\\\in{U,1,2}$ ($U$: user; $1$: data centre 1; $2$: data centre 2).
- $\\\text{pass}$: this is the event “none of the three QKD protocols aborted”.
- $\\\Delta(.,.)$: trace distance between two quantum systems ($\\\Delta(\\\rho,\\\sigma)=\\\frac{1}{2} ||\\\rho-\\\sigma||_1$ where $||.||_1$ is the trace norm).
- $\\\rho_{UE}^w$: total view of the user $U$ and the eavesdropper $E$ conditioned by $w$.
- $\\\rho_{D_j E}^x$: total view of data centre $D_j$ and the eavesdropper $E$ conditioned by $x$.
- $\\\rho_E^{x,w}$: total view of the eavesdropper $E$ conditioned by $x$ and $w$.
Properties
For this protocol, SPIR security definitions (see (Symmetric) Private Information Retrieval) are extended as follow:
- $\\\eta_\\\text{cor}$-correctness: If the user and the data centres are honest, then for any index $x$ and database $w$, $(1-p_\\\text{fail})Pr[\\\hat{w}x \\\neq w_x|\\\text{pass}]\\\leq\\\eta\\\text{cor}$.
- $\\\eta_{UP}$-user privacy: If the user is honest, then for any database $w$ and shared secret keys between the data centres $(s_5,s_6)$, and for any data centre $D_j$, $\\\Delta(\\\rho_{D_{j} E}^x,\\\rho_{D_{j} E}^{x\’}) \\\leq \\\eta_{UP}$ for all indexes $x$ and $x\’$.
- $\\\eta_{DP}$-database privacy: If the data centres are honest, then for any index $x$, randomness $r$ and keys $(s_1^\\\text{dec},s_2^\\\text{enc},s_3^\\\text{dec},s_4^\\\text{enc})$, then there exists an index $x\’$ such that for all databases $w$ and $w\’$ with $w_{x\’}={w\’}{x\’}$, $\\\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 $w$ or the index of the desired database element $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.
- $\\\eta_{PS}$-protocol secrecy: If the user and the data centres are honest, then for all index-database pairs $(x,w)$ and $(x\’,w\’)$, $\\\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 $(\\\eta_\\\text{cor},\\\eta_{UP},\\\eta_{DP},\\\eta_{PS})$-secure.
A two-database one-round $(0,0,0,0)$-secure SPIR protocol with ideal keys replaced by $\\\epsilon$-secure QKD keys, where $\\\epsilon=\\\epsilon_\\\text{corr}+\\\epsilon_\\\text{sec}$ (see Quantum Key Distribution), can be shown to be $(3\\\epsilon_\\\text{corr},2\\\epsilon,2\\\epsilon,4\\\epsilon)$-secure (see Kon and Lim (2021) [1] for a proof).
Technical Description
Inputs:
- User $U$: index of desired database item, $X=x$; randomness $R$; $f_{\\\text{query},1}$,$f_{\\\text{query},2}$,$f_\\\text{dec}$.
- Data centre $D_1$: database $W=w$.
- Data centre $D_2$: database $W=w$. Output:
- User $U$: retrieved database element $\\\hat{w}_x$ (it may be different from the desired database element $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|quantum key distribution protocol (see e.g., Measurement Device Independent Quantum Key Distribution (MDI-QKD)) and this specific protocol[2]), so that at the end of the secret sharing phase, data centre $D_1$ and the user $U$ share secret key pair $(S_1,S_2)$; data centre $D_2$ and the user $U$ share secret key pair $(S_3,S_4)$; and data centres $D_1$ and $D_2$ share secret key pair $(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)[3].
- Query: Query $Q_1=f_{\\\text{query},1} (x,R)$ (resp. $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 $C_{U1}$ (resp. $C_{U2}$) to data centre $D_1$ (resp. $D_2$).
- Answer: After receiving query $\\\tilde{Q}1$ (resp. $\\\tilde{Q}2$), data centre $D_1$ (resp. $D_2$) generates answer $A_1=f{\\\text{ans},1} (\\\tilde{Q}1,w,S_5)$ (resp. $A_2=f{\\\text{ans},2} (\\\tilde{Q}2,w,S_6)$) and sends it to the user via $C{U1}$ (resp. $C{U2}$).
- Retrieval: The user decodes the received database element $\\\hat{w}x$ using $f{\\\text{dec}}$: $\\\hat{w}x=f\\\text{dec} (\\\tilde{A}_1,\\\tilde{A}_2,Q_1,Q_2,x,R)$.
Experimental Implementations
No content has been added to this section, yet!
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))[3].
- With current QKD technology, this SPIR protocol is feasible, as shown by Kon and Lim (2021)[1].
References
- Kon, Wen Yu, and Charles Ci Wen Lim. 2021. “Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography” Entropy 23, no. 1: 54. https://doi.org/10.3390/e23010054
- Curty, M., Xu, F., Cui, W. et al. Finite-key analysis for measurement-device-independent quantum key distribution. Nat Commun 5, 3732 (2014). https://doi.org/10.1038/ncomms4732
- Gertner, Yael, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. ‘Protecting Data Privacy in Private Information Retrieval Schemes’. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, 151–60. STOC ’98. New York, NY, USA: Association for Computing Machinery, 1998. https://doi.org/10.1145/276698.276723.
- 2026-04-06 at 20:57 by kimworrall
implements (Symmetric) Private Information Retrieval
Introduction
This protocol [1] implements 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. It uses quantum key distribution (QKD) to share randomness between servers and to secure classical channels between the user and the servers, and thus does not need the assumption of perfectly secure channels that classical multi-database SPIR protocols rely on.
Related Paper(s)
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, from 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 an encryption of the index of the desired database element using 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: Finally, the user can reconstruct the desired database element from the answers of each data centre and his own inputs.
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.
Requirements
- Quantum channels to perform QKD between parties.
- Classical authenticated channels.
- QKD devices to prepare and measure qubits.
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.
- $A_i$: reply generated by the $i^{\\\text{th}}$ data centre for the user after receiving $\\\tilde{Q}_i$.
- $\\\tilde{A}_i$: reply from the $i^{\\\text{th}}$ data centre received by the client (may be different from $A_i$).
- $\\\hat{w}_x$: database element retrieved by the user at the end of the protocol.
- $p_\\\text{fail}$: probability that at least one of the three QKD protocols aborted ($p_\\\text{fail}=1-(1-p_{\\\perp,U1})(1-p_{\\\perp,U2})(1-p_{\\\perp,12})$).
- $p_{\\\perp,AB}$: probability that the QKD protocol between parties $A$ and $B$ aborts, where $A,B\\\in{U,1,2}$ ($U$: user; $1$: data centre 1; $2$: data centre 2).
- $\\\text{pass}$: this is the event “none of the three QKD protocols aborted”.
- $\\\Delta(.,.)$: trace distance between two quantum systems ($\\\Delta(\\\rho,\\\sigma)=\\\frac{1}{2} ||\\\rho-\\\sigma||_1$ where $||.||_1$ is the trace norm).
- $\\\rho_{UE}^w$: total view of the user $U$ and the eavesdropper $E$ conditioned by $w$.
- $\\\rho_{D_j E}^x$: total view of data centre $D_j$ and the eavesdropper $E$ conditioned by $x$.
- $\\\rho_E^{x,w}$: total view of the eavesdropper $E$ conditioned by $x$ and $w$.
Properties
For this protocol, SPIR security definitions (see (Symmetric) Private Information Retrieval) are extended as follow:
- $\\\eta_\\\text{cor}$-correctness: If the user and the data centres are honest, then for any index $x$ and database $w$, $(1-p_\\\text{fail})Pr[\\\hat{w}x \\\neq w_x|\\\text{pass}]\\\leq\\\eta\\\text{cor}$.
- $\\\eta_{UP}$-user privacy: If the user is honest, then for any database $w$ and shared secret keys between the data centres $(s_5,s_6)$, and for any data centre $D_j$, $\\\Delta(\\\rho_{D_{j} E}^x,\\\rho_{D_{j} E}^{x\’}) \\\leq \\\eta_{UP}$ for all indexes $x$ and $x\’$.
- $\\\eta_{DP}$-database privacy: If the data centres are honest, then for any index $x$, randomness $r$ and keys $(s_1^\\\text{dec},s_2^\\\text{enc},s_3^\\\text{dec},s_4^\\\text{enc})$, then there exists an index $x\’$ such that for all databases $w$ and $w\’$ with $w_{x\’}={w\’}{x\’}$, $\\\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 $w$ or the index of the desired database element $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.
- $\\\eta_{PS}$-protocol secrecy: If the user and the data centres are honest, then for all index-database pairs $(x,w)$ and $(x\’,w\’)$, $\\\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 $(\\\eta_\\\text{cor},\\\eta_{UP},\\\eta_{DP},\\\eta_{PS})$-secure.
A two-database one-round $(0,0,0,0)$-secure SPIR protocol with ideal keys replaced by $\\\epsilon$-secure QKD keys, where $\\\epsilon=\\\epsilon_\\\text{corr}+\\\epsilon_\\\text{sec}$ (see Quantum Key Distribution), can be shown to be $(3\\\epsilon_\\\text{corr},2\\\epsilon,2\\\epsilon,4\\\epsilon)$-secure (see Kon and Lim (2021) [1] for a proof).
Technical Description
Inputs:
- User $U$: index of desired database item, $X=x$; randomness $R$; $f_{\\\text{query},1}$,$f_{\\\text{query},2}$,$f_\\\text{dec}$.
- Data centre $D_1$: database $W=w$.
- Data centre $D_2$: database $W=w$. Output:
- User $U$: retrieved database element $\\\hat{w}_x$ (it may be different from the desired database element $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|quantum key distribution protocol (see e.g., Measurement Device Independent Quantum Key Distribution (MDI-QKD)) and this specific protocol[2]), so that at the end of the secret sharing phase, data centre $D_1$ and the user $U$ share secret key pair $(S_1,S_2)$; data centre $D_2$ and the user $U$ share secret key pair $(S_3,S_4)$; and data centres $D_1$ and $D_2$ share secret key pair $(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)[3].
- Query: Query $Q_1=f_{\\\text{query},1} (x,R)$ (resp. $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 $C_{U1}$ (resp. $C_{U2}$) to data centre $D_1$ (resp. $D_2$).
- Answer: After receiving query $\\\tilde{Q}1$ (resp. $\\\tilde{Q}2$), data centre $D_1$ (resp. $D_2$) generates answer $A_1=f{\\\text{ans},1} (\\\tilde{Q}1,w,S_5)$ (resp. $A_2=f{\\\text{ans},2} (\\\tilde{Q}2,w,S_6)$) and sends it to the user via $C{U1}$ (resp. $C{U2}$).
- Retrieval: The user decodes the received database element $\\\hat{w}x$ using $f{\\\text{dec}}$: $\\\hat{w}x=f\\\text{dec} (\\\tilde{A}_1,\\\tilde{A}_2,Q_1,Q_2,x,R)$.
Experimental Implementations
No content has been added to this section, yet!
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))[3].
- With current QKD technology, this SPIR protocol is feasible, as shown by Kon and Lim (2021)[1].
References
- Kon, Wen Yu, and Charles Ci Wen Lim. 2021. “Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography” Entropy 23, no. 1: 54. https://doi.org/10.3390/e23010054
- Curty, M., Xu, F., Cui, W. et al. Finite-key analysis for measurement-device-independent quantum key distribution. Nat Commun 5, 3732 (2014). https://doi.org/10.1038/ncomms4732
- Gertner, Yael, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. ‘Protecting Data Privacy in Private Information Retrieval Schemes’. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, 151–60. STOC ’98. New York, NY, USA: Association for Computing Machinery, 1998. https://doi.org/10.1145/276698.276723.