(Symmetric) Private Information Retrieval: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
(Creating a new page for Private Information Retrieval)
 
No edit summary
 
(2 intermediate revisions by one other user not shown)
Line 4: Line 4:
==Description==
==Description==
<!-- Description: A lucid definition of functionality in discussion.-->
<!-- Description: A lucid definition of functionality in discussion.-->
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>
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>
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 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>
Apart from using quantum techniques to enhance the classical 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>
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:'''  
'''Tags:'''  
Line 15: Line 16:


<!-- Tags Any related page or list of protocols is connected by this section-->
<!-- Tags Any related page or list of protocols is connected by this section-->
==Use-cases==
<!-- Use Case (if available) analyses how practical the protocol is-->
===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]]].


==Properties==
==Properties==
Line 43: Line 55:
====Single-database protocols====
====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 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]]]. Therefore, to design efficient PIR protocols or to achieve SPIR, several assumptions have been considered; they include:
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.
* Hardness assumptions: PIR protocols with computational security.
* Assumptions on the adversarial model:
* 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.  
** 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 Oblivious Key Distribution|QPQ protocols based on quantum oblivious key distribution]]
***[[Quantum Private Queries Protocol Based on Sending Quantum States to an Oracle|QPQ protocols based on sending quantum states to an oracle]]
***[[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.
** 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]]
***[[Single-Database Quantum Private Information Retrieval in the Honest Server Model|QPIR protocols in the honest server model]]
Line 55: Line 67:
* Relativistic assumptions: quantum SPIR protocols whose security uses properties from special relativity.
* Relativistic assumptions: quantum SPIR protocols whose security uses properties from special relativity.
**[[Relativistic Quantum Oblivious Transfer|Relativistic QOT protocols]]
**[[Relativistic Quantum Oblivious Transfer|Relativistic QOT protocols]]
Nota bene: single-database (Q)SPIR and one-out-of-n (quantum) [[Oblivious Transfer|oblivious transfer]] ((Q)OT) are similar cryptographic tasks.


====Multi-database protocols====
====Multi-database protocols====
Line 75: Line 85:
* [[Multi-Database Quantum Symmetric Private Information Retrieval for a Quantum Database|Multi-database quantum SPIR protocols in the visible 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 Case (if available) analyses how practical the protocol is-->




<!-- ==Further Information== -->
==Further Information==
<!-- Any issue that could not be addressed or find a place in the above sections or any review paper discussing a feature of various types of protocols related to the functionality. -->
<!-- Any issue that could not be addressed or find a place in the above sections or any review paper discussing a feature of various types of protocols related to the functionality. -->
===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==
==References==
Line 86: Line 173:
#[https://arxiv.org/pdf/quant-ph/9611031.pdf Lo (1997)]
#[https://arxiv.org/pdf/quant-ph/9611031.pdf Lo (1997)]
#[https://arxiv.org/pdf/1902.09768.pdf Aharonov et al (2019)]
#[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>
<div style='text-align: right;'>''*contributed by Marine Demarty''</div>

Latest revision as of 12:33, 27 September 2024


Description[edit]

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

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

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

In the classical or quantum setting, (Q)SPIR and one-out-of-n (quantum) 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.

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)[1].

Tags: Two Party Protocol, Specific Task, Quantum Enhanced Classical Functionality.

Use-cases[edit]

Classical database[edit]

  • 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 [5].

Properties[edit]

Security definitions[edit]

(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[edit]

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[edit]

Classical database[edit]

In the quantum setting, protocols aiming at achieving (S)PIR for a classical database fall into two main categories:

Single-database protocols[edit]

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 [2].
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 [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:

Multi-database protocols[edit]

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:


Quantum database[edit]

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)[1].

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 [1].


Further Information[edit]

Optimal communication complexity of the (Q)(S)PIR problem[edit]

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.

  •  : number of database elements (quantum states in the 'fully' quantum setting)
  •  : total size of database elements (i.e., the sum of the sizes, in bits, of each database element)
  •  : dimension of the quantum states stored in the quantum database ( if they are qubits)
  •  : number of servers (or equivalently of replicated databases)

Single-database case[edit]

Problem Additional assumptions Optimal communication complexity Reference
Classical PIR 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 \Theta(m)} Chor et al (1995)
Classical SPIR NA (impossible)
Quantum PIR (Classical database) Specious server Baumeler and Broadbent (2015)
Specious server & prior entanglement Aharonov et al (2019)
Honest server Kerenidis et al (2016)
Honest server & prior entanglement 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 O(\log (m))} Kerenidis et al (2016)
Quantum SPIR (Classical database) NA (impossible) 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) Giovannetti et al (2008)
Quantum PIR (Quantum database) Honest server & blind setting Song and Hayashi (2021)
Honest server & visible setting (for one-round) Song and Hayashi (2021)
Honest server & prior entanglement Song and Hayashi (2021)
Quantum SPIR (Quantum database)

Multi-database case[edit]

Problem Additional assumptions Optimal communication complexity Reference
Classical PIR
Classical SPIR Servers do not communicate with each other & secure classical channels Gertner et al (2000)
Quantum PIR (Classical database)
Quantum SPIR (Classical database) Servers do not communicate with each other Kon and Lim (2021)
Servers do not communicate with each other & honest user & prior entanglement Kerenidis and de Wolf (2004)
Quantum PIR (Quantum database)
Quantum SPIR (Quantum database) Servers do not communicate with each other & prior entanglement & visible setting & database contains pure qubit states Song and Hayashi (2021)
Servers do not communicate with each other & prior entanglement & visible setting & database contains pure qudit states Song and Hayashi (2021)
Servers do not communicate with each other & prior entanglement & visible setting & database contains commutative unitaries Song and Hayashi (2021)


References[edit]

  1. Song and Hayashi (2021)
  2. Baumeler and Broadbent (2015)
  3. Lo (1997)
  4. Aharonov et al (2019)
  5. Kon and Lim (2021)


*contributed by Marine Demarty