Editing
Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution
Jump to navigation
Jump to search
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
<!-- This is a comment. You can erase them or write below --> <!-- Intro: brief description of the protocol --> 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: related pages or category --> '''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== <!-- It describes the setting in which the protocol will be successful. --> *'''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== <!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol --> 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== <!-- Connects the non-mathematical outline with further sections. --> * <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>. <!--==Knowledge Graph==--> <!-- Add this part if the protocol is already in the graph --> <!--{{graph}}--> ==Requirements== * Quantum channels to perform QKD between parties. * Classical authenticated channels. * QKD devices to prepare and measure qubits. ==Properties== <!-- important information on the protocol: parameters (threshold values), security claim, success probability... --> 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== <!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. --> '''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== <!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... --> * 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)]. <!--==References==--> <div style='text-align: right;'>''*contributed by Marine Demarty''</div>
Summary:
Please note that all contributions to Quantum Protocol Zoo may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
Quantum Protocol Zoo:Copyrights
for details).
Do not submit copyrighted work without permission!
To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:
Cancel
Editing help
(opens in new window)
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Log in
Namespaces
Page
Discussion
English
Views
Read
Edit
View history
More
Search
Navigation
Main page
News
Protocol Library
Certification Library
Nodal Subroutines
Codes Repository
Knowledge Graphs
Submissions
Categories
Supplementary Information
Recent Changes
Contact us
Help
Tools
What links here
Related changes
Special pages
Page information