Revision History for: (Symmetric) Private Information Retrieval

• 2026-06-07 at 19:15 by Mina Doosti
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  The protocols that implement this functionality are:

  • Prepare and Measure Quantum Digital Signature
  • Prepare-and-Send Verifiable Universal Blind Quantum Computation
  • Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  Classical PIR
  Assumptions: –
  Communication complexity: $\\\Theta(m)$
  Reference: Chor et al. (1995) [3]

  Classical SPIR
  Assumptions: –
  Communication complexity: NA, impossible
  Reference: –

  Quantum PIR, classical database
  Assumptions: Specious server
  Communication complexity: $\\\Theta(m)$
  Reference: Baumeler and Broadbent (2015) [4]

  Quantum PIR, classical database
  Assumptions: Specious server; prior entanglement
  Communication complexity: $\\\Theta(m)$
  Reference: Aharonov et al. (2019) [5]

  Quantum PIR, classical database
  Assumptions: Honest server
  Communication complexity: $O(\\\mathrm{poly}\\\log m)$
  Reference: Kerenidis et al. (2016) [6]

  Quantum PIR, classical database
  Assumptions: Honest server; prior entanglement
  Communication complexity: $O(\\\log m)$
  Reference: Kerenidis et al. (2016) [6]

  Quantum SPIR, classical database
  Assumptions: –
  Communication complexity: NA, impossible
  Reference: Lo (1997) [7]

  Quantum SPIR, classical database
  Assumptions: The server will not cheat if there is a risk of detection; the user obtains at most two items
  Communication complexity: $O(\\\log m)$
  Reference: Giovannetti et al. (2008) [8]

  Quantum PIR, quantum database
  Assumptions: Honest server; blind setting
  Communication complexity: $\\\Theta(m)$
  Reference: Song and Hayashi (2021) [1]

  Quantum PIR, quantum database
  Assumptions: Honest server; visible setting
  Communication complexity: $\\\Theta(m)$, one round
  Reference: Song and Hayashi (2021) [1]

  Quantum PIR, quantum database
  Assumptions: Honest server; prior entanglement
  Communication complexity: $O(\\\log m)$
  Reference: Song and Hayashi (2021) [1]

  Multi-database case

  Classical PIR
  Assumptions: –
  Communication complexity: –
  Reference: –

  Classical SPIR
  Assumptions: Non-communicating servers; secure classical channels
  Communication complexity: $O\\\left(m^{\\\frac{1}{2k-1}}\\\right)$ bits
  Reference: Gertner et al. (2000) [9]

  Quantum PIR, classical database
  Assumptions: –
  Communication complexity: –
  Reference: –

  Quantum SPIR, classical database
  Assumptions: Non-communicating servers
  Communication complexity: $O\\\left(m^{\\\frac{1}{2k-1}}\\\right)$ + QKD
  Reference: Kon and Lim (2021) [2]

  Quantum SPIR, classical database
  Assumptions: Non-communicating servers; honest user; prior entanglement
  Communication complexity: $m^{O\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)}$
  Reference: Kerenidis and de Wolf (2004) [10]

  Quantum PIR, quantum database
  Assumptions: –
  Communication complexity: –
  Reference: –

  Quantum SPIR, qubit states
  Assumptions: Non-communicating servers; prior entanglement; visible setting
  Communication complexity: $O(f)+O(1)$ qubits + $O(1)$ ebits
  Reference: Song and Hayashi (2021) [1]

  Quantum SPIR, qudit states
  Assumptions: Non-communicating servers; prior entanglement; visible setting
  Communication complexity: $O(f)+O(d^d \\\log d)$ qubits + $O(d^d \\\log d)$ ebits
  Reference: Song and Hayashi (2021) [1]

  Quantum SPIR, commutative unitaries
  Assumptions: Non-communicating servers; prior entanglement; visible setting
  Communication complexity: $O(f)+O(\\\log d)$ qubits + $O(\\\log d)$ ebits
  Reference: Song and Hayashi (2021) [1]

  References

  ---

  * The original version of this page on the old QPZoo was created by Marine Demarty

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2026-06-07 at 19:12 by Mina Doosti
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  The protocols that implement this functionality are:

  • Prepare and Measure Quantum Digital Signature
  • Prepare-and-Send Verifiable Universal Blind Quantum Computation
  • Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  $$
  \\\scriptsize
  \\\begin{array}{c|c|c|c}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR}
  & –
  & \\\Theta(m)
  & \\\text{Chor et al. (1995) [3]} \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR}
  & –
  & \\\text{NA (impossible)}
  & – \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & \\\text{Specious server}
  & \\\Theta(m)
  & \\\begin{gathered}\\\text{Baumeler and}\\\\\\\\\ \\\text{Broadbent (2015) [4]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & \\\begin{gathered}\\\text{Specious server,}\\\\\\\\\ \\\text{prior entanglement}\\\end{gathered}
  & \\\Theta(m)
  & \\\text{Aharonov et al. (2019) [5]} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & \\\text{Honest server}
  & O(\\\mathrm{poly}\\\log m)
  & \\\text{Kerenidis et al. (2016) [6]} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & \\\begin{gathered}\\\text{Honest server,}\\\\\\\\\ \\\text{prior entanglement}\\\end{gathered}
  & O(\\\log m)
  & \\\text{Kerenidis et al. (2016) [6]} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum SPIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & –
  & \\\text{NA (impossible)}
  & \\\text{Lo (1997) [7]} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum SPIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & \\\begin{gathered}
  \\\text{Server will not cheat}\\\\\\\\\
  \\\text{if there is risk of detection,}\\\\\\\\\
  \\\text{user gets at most two items}
  \\\end{gathered}
  & O(\\\log m)
  & \\\begin{gathered}\\\text{Giovannetti et al.}\\\\\\\\\ \\\text{(2008) [8]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Quantum DB)}\\\end{gathered}
  & \\\begin{gathered}\\\text{Honest server,}\\\\\\\\\ \\\text{blind setting}\\\end{gathered}
  & \\\Theta(m)
  & \\\begin{gathered}\\\text{Song and Hayashi}\\\\\\\\\ \\\text{(2021) [1]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Quantum DB)}\\\end{gathered}
  & \\\begin{gathered}\\\text{Honest server,}\\\\\\\\\ \\\text{visible setting}\\\end{gathered}
  & \\\begin{gathered}\\\Theta(m)\\\\\\\\\ \\\text{(1 round)}\\\end{gathered}
  & \\\begin{gathered}\\\text{Song and Hayashi}\\\\\\\\\ \\\text{(2021) [1]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Quantum DB)}\\\end{gathered}
  & \\\begin{gathered}\\\text{Honest server,}\\\\\\\\\ \\\text{prior entanglement}\\\end{gathered}
  & O(\\\log m)
  & \\\begin{gathered}\\\text{Song and Hayashi}\\\\\\\\\ \\\text{(2021) [1]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\end{array}
  $$

  Multi-database case

  $$
  \\\scriptsize
  \\\begin{array}{c|c|c|c}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR}
  & –
  & –
  & – \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR}
  & \\\begin{gathered}
  \\\text{Non-communicating servers,}\\\\\\\\\
  \\\text{secure classical channels}
  \\\end{gathered}
  & O\\\!\\\left(m^{\\\frac{1}{2k-1}}\\\right)\\\ \\\text{bits}
  & \\\text{Gertner et al. (2000) [9]} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & –
  & –
  & – \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum SPIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & \\\text{Non-communicating servers}
  & O\\\!\\\left(m^{\\\frac{1}{2k-1}}\\\right) + \\\text{QKD}
  & \\\text{Kon and Lim (2021) [2]} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum SPIR}\\\\\\\\\ \\\text{(Classical DB)}\\\end{gathered}
  & \\\begin{gathered}
  \\\text{Non-communicating servers,}\\\\\\\\\
  \\\text{honest user,}\\\\\\\\\
  \\\text{prior entanglement}
  \\\end{gathered}
  & m^{O\\\!\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)}
  & \\\begin{gathered}\\\text{Kerenidis and}\\\\\\\\\ \\\text{de Wolf (2004) [10]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum PIR}\\\\\\\\\ \\\text{(Quantum DB)}\\\end{gathered}
  & –
  & –
  & – \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum SPIR}\\\\\\\\\ \\\text{(Qubit states)}\\\end{gathered}
  & \\\begin{gathered}
  \\\text{Non-communicating servers,}\\\\\\\\\
  \\\text{prior entanglement,}\\\\\\\\\
  \\\text{visible setting}
  \\\end{gathered}
  & \\\begin{gathered}
  O(f)+O(1)\\\ \\\text{qubits}\\\\\\\\\
  +\\\,O(1)\\\ \\\text{ebits}
  \\\end{gathered}
  & \\\begin{gathered}\\\text{Song and Hayashi}\\\\\\\\\ \\\text{(2021) [1]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum SPIR}\\\\\\\\\ \\\text{(Qudit states)}\\\end{gathered}
  & \\\begin{gathered}
  \\\text{Non-communicating servers,}\\\\\\\\\
  \\\text{prior entanglement,}\\\\\\\\\
  \\\text{visible setting}
  \\\end{gathered}
  & \\\begin{gathered}
  O(f)+O(d^d \\\log d)\\\ \\\text{qubits}\\\\\\\\\
  +\\\,O(d^d \\\log d)\\\ \\\text{ebits}
  \\\end{gathered}
  & \\\begin{gathered}\\\text{Song and Hayashi}\\\\\\\\\ \\\text{(2021) [1]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\begin{gathered}\\\text{Quantum SPIR}\\\\\\\\\ \\\text{(Commutative unitaries)}\\\end{gathered}
  & \\\begin{gathered}
  \\\text{Non-communicating servers,}\\\\\\\\\
  \\\text{prior entanglement,}\\\\\\\\\
  \\\text{visible setting}
  \\\end{gathered}
  & \\\begin{gathered}
  O(f)+O(\\\log d)\\\ \\\text{qubits}\\\\\\\\\
  +\\\,O(\\\log d)\\\ \\\text{ebits}
  \\\end{gathered}
  & \\\begin{gathered}\\\text{Song and Hayashi}\\\\\\\\\ \\\text{(2021) [1]}\\\end{gathered} \\\\\\\\\
  \\\hline
  \\\end{array}
  $$

  References

  ---

  * The original version of this page on the old QPZoo was created by Marine Demarty

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2026-06-07 at 19:04 by Mina Doosti
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  The protocols that implement this functionality are:

  • Prepare and Measure Quantum Digital Signature
  • Prepare-and-Send Verifiable Universal Blind Quantum Computation
  • Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & \\\Theta(m) & \\\text{Chor et al. (1995)[3]} \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} & – & \\\text{NA (impossible)} & – \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server} & \\\Theta(m) & \\\text{Baumeler and Broadbent (2015)[4]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server, Prior entanglement} & \\\Theta(m) & \\\text{Aharonov et al. (2019)[5]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server} & O(\\\mathrm{poly} \\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} & – & \\\text{NA (impossible)} & \\\text{Lo (1997)[7]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Server won’t cheat if risk of detection,} \\\\\\\\\
  \\\text{User gets at most 2 items}
  \\\end{array} &
  O(\\\log m) & \\\text{Giovannetti et al. (2008)[8]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Blind setting} & \\\Theta(m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Visible setting} & \\\Theta(m) \\\text{ (1-round)} & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  Multi-database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers} \\\\\\\\\
  \\\text{Secure classical channels}
  \\\end{array} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) \\\text{ bits} &
  \\\text{Gertner et al. (2000)[9]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\text{Non-communicating servers} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) + \\\text{QKD} &
  \\\text{Kon and Lim (2021)[2]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Honest user, Prior entanglement}
  \\\end{array} &
  m^{O\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)} &
  \\\text{Kerenidis and de Wolf (2004)[10]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qubit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(1) \\\text{ qubits} + O(1) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qudit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(d^d \\\log d) \\\text{ qubits} + O(d^d \\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Commutative unitaries)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(\\\log d) \\\text{ qubits} + O(\\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  References

  ---

  * The original version of this page on the old QPZoo was created by Marine Demarty

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2026-03-20 at 17:16 by kimworrall
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  The protocols that implement this functionality are:

  • Prepare and Measure Quantum Digital Signature

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & \\\Theta(m) & \\\text{Chor et al. (1995)[3]} \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} & – & \\\text{NA (impossible)} & – \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server} & \\\Theta(m) & \\\text{Baumeler and Broadbent (2015)[4]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server, Prior entanglement} & \\\Theta(m) & \\\text{Aharonov et al. (2019)[5]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server} & O(\\\mathrm{poly} \\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} & – & \\\text{NA (impossible)} & \\\text{Lo (1997)[7]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Server won’t cheat if risk of detection,} \\\\\\\\\
  \\\text{User gets at most 2 items}
  \\\end{array} &
  O(\\\log m) & \\\text{Giovannetti et al. (2008)[8]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Blind setting} & \\\Theta(m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Visible setting} & \\\Theta(m) \\\text{ (1-round)} & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  Multi-database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers} \\\\\\\\\
  \\\text{Secure classical channels}
  \\\end{array} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) \\\text{ bits} &
  \\\text{Gertner et al. (2000)[9]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\text{Non-communicating servers} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) + \\\text{QKD} &
  \\\text{Kon and Lim (2021)[2]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Honest user, Prior entanglement}
  \\\end{array} &
  m^{O\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)} &
  \\\text{Kerenidis and de Wolf (2004)[10]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qubit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(1) \\\text{ qubits} + O(1) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qudit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(d^d \\\log d) \\\text{ qubits} + O(d^d \\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Commutative unitaries)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(\\\log d) \\\text{ qubits} + O(\\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  References

  ---

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2025-06-24 at 21:29 by JuliaM
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  No protocols implement this functionality yet.

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & \\\Theta(m) & \\\text{Chor et al. (1995)[3]} \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} & – & \\\text{NA (impossible)} & – \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server} & \\\Theta(m) & \\\text{Baumeler and Broadbent (2015)[4]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server, Prior entanglement} & \\\Theta(m) & \\\text{Aharonov et al. (2019)[5]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server} & O(\\\mathrm{poly} \\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} & – & \\\text{NA (impossible)} & \\\text{Lo (1997)[7]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Server won’t cheat if risk of detection,} \\\\\\\\\
  \\\text{User gets at most 2 items}
  \\\end{array} &
  O(\\\log m) & \\\text{Giovannetti et al. (2008)[8]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Blind setting} & \\\Theta(m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Visible setting} & \\\Theta(m) \\\text{ (1-round)} & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  Multi-database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers} \\\\\\\\\
  \\\text{Secure classical channels}
  \\\end{array} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) \\\text{ bits} &
  \\\text{Gertner et al. (2000)[9]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\text{Non-communicating servers} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) + \\\text{QKD} &
  \\\text{Kon and Lim (2021)[2]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Honest user, Prior entanglement}
  \\\end{array} &
  m^{O\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)} &
  \\\text{Kerenidis and de Wolf (2004)[10]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qubit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(1) \\\text{ qubits} + O(1) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qudit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(d^d \\\log d) \\\text{ qubits} + O(d^d \\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Commutative unitaries)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(\\\log d) \\\text{ qubits} + O(\\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  References

  ---

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2025-05-15 at 15:08 by JuliaM
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  No protocols implement this functionality yet.

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & \\\Theta(m) & \\\text{Chor et al. (1995)[3]} \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} & – & \\\text{NA (impossible)} & – \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server} & \\\Theta(m) & \\\text{Baumeler and Broadbent (2015)[4]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server, Prior entanglement} & \\\Theta(m) & \\\text{Aharonov et al. (2019)[5]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server} & O(\\\mathrm{poly} \\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} & – & \\\text{NA (impossible)} & \\\text{Lo (1997)[7]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Server won’t cheat if risk of detection,} \\\\\\\\\
  \\\text{User gets at most 2 items}
  \\\end{array} &
  O(\\\log m) & \\\text{Giovannetti et al. (2008)[8]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Blind setting} & \\\Theta(m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Visible setting} & \\\Theta(m) \\\text{ (1-round)} & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  Multi-database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers} \\\\\\\\\
  \\\text{Secure classical channels}
  \\\end{array} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) \\\text{ bits} &
  \\\text{Gertner et al. (2000)[9]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\text{Non-communicating servers} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) + \\\text{QKD} &
  \\\text{Kon and Lim (2021)[2]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Honest user, Prior entanglement}
  \\\end{array} &
  m^{O\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)} &
  \\\text{Kerenidis and de Wolf (2004)[10]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qubit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(1) \\\text{ qubits} + O(1) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qudit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(d^d \\\log d) \\\text{ qubits} + O(d^d \\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Commutative unitaries)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(\\\log d) \\\text{ qubits} + O(\\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  References

  ---

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2025-05-15 at 15:07 by JuliaM
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  No protocols implement this functionality yet.

  Classical Analogues

  ---

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & \\\Theta(m) & \\\text{Chor et al. (1995)[3]} \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} & – & \\\text{NA (impossible)} & – \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server} & \\\Theta(m) & \\\text{Baumeler and Broadbent (2015)[4]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server, Prior entanglement} & \\\Theta(m) & \\\text{Aharonov et al. (2019)[5]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server} & O(\\\mathrm{poly} \\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} & – & \\\text{NA (impossible)} & \\\text{Lo (1997)[7]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Server won’t cheat if risk of detection,} \\\\\\\\\
  \\\text{User gets at most 2 items}
  \\\end{array} &
  O(\\\log m) & \\\text{Giovannetti et al. (2008)[8]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Blind setting} & \\\Theta(m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Visible setting} & \\\Theta(m) \\\text{ (1-round)} & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & \\\Theta(m) & \\\text{Chor et al. (1995)[3]} \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} & – & \\\text{NA (impossible)} & – \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server} & \\\Theta(m) & \\\text{Baumeler and Broadbent (2015)[4]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server, Prior entanglement} & \\\Theta(m) & \\\text{Aharonov et al. (2019)[5]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server} & O(\\\mathrm{poly} \\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} & – & \\\text{NA (impossible)} & \\\text{Lo (1997)[7]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Server won’t cheat if risk of detection,} \\\\\\\\\
  \\\text{User gets at most 2 items}
  \\\end{array} &
  O(\\\log m) & \\\text{Giovannetti et al. (2008)[8]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Blind setting} & \\\Theta(m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Visible setting} & \\\Theta(m) \\\text{ (1-round)} & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  Multi-database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers} \\\\\\\\\
  \\\text{Secure classical channels}
  \\\end{array} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) \\\text{ bits} &
  \\\text{Gertner et al. (2000)[9]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\text{Non-communicating servers} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) + \\\text{QKD} &
  \\\text{Kon and Lim (2021)[2]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Honest user, Prior entanglement}
  \\\end{array} &
  m^{O\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)} &
  \\\text{Kerenidis and de Wolf (2004)[10]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qubit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(1) \\\text{ qubits} + O(1) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qudit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(d^d \\\log d) \\\text{ qubits} + O(d^d \\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Commutative unitaries)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(\\\log d) \\\text{ qubits} + O(\\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  References

  ---

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2025-05-15 at 15:05 by JuliaM
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  No protocols implement this functionality yet.

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

   

  Multi-database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers} \\\\\\\\\
  \\\text{Secure classical channels}
  \\\end{array} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) \\\text{ bits} &
  \\\text{Gertner et al. (2000)[9]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\text{Non-communicating servers} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) + \\\text{QKD} &
  \\\text{Kon and Lim (2021)[2]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Honest user, Prior entanglement}
  \\\end{array} &
  m^{O\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)} &
  \\\text{Kerenidis and de Wolf (2004)[10]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qubit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(1) \\\text{ qubits} + O(1) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qudit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(d^d \\\log d) \\\text{ qubits} + O(d^d \\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Commutative unitaries)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(\\\log d) \\\text{ qubits} + O(\\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  References

  ---

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2025-05-15 at 15:04 by JuliaM
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  No protocols implement this functionality yet.

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & \\\Theta(m) & \\\text{Chor et al. (1995)[3]} \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} & – & \\\text{NA (impossible)} & – \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server} & \\\Theta(m) & \\\text{Baumeler and Broadbent (2015)[4]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Specious server, Prior entanglement} & \\\Theta(m) & \\\text{Aharonov et al. (2019)[5]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server} & O(\\\mathrm{poly} \\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Kerenidis et al. (2016)[6]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} & – & \\\text{NA (impossible)} & \\\text{Lo (1997)[7]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Server won’t cheat if risk of detection,} \\\\\\\\\
  \\\text{User gets at most 2 items}
  \\\end{array} &
  O(\\\log m) & \\\text{Giovannetti et al. (2008)[8]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Blind setting} & \\\Theta(m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Visible setting} & \\\Theta(m) \\\text{ (1-round)} & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & \\\text{Honest server, Prior entanglement} & O(\\\log m) & \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  Multi-database case

  $$\\\begin{array}{|c|c|c|c|}
  \\\hline
  \\\textbf{Problem} & \\\textbf{Assumptions} & \\\textbf{Comm. Complexity} & \\\textbf{Reference} \\\\\\\\\
  \\\hline
  \\\text{Classical PIR} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Classical SPIR} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers} \\\\\\\\\
  \\\text{Secure classical channels}
  \\\end{array} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) \\\text{ bits} &
  \\\text{Gertner et al. (2000)[9]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Classical DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\text{Non-communicating servers} &
  O\\\left(m^{\\\frac{1}{2k – 1}}\\\right) + \\\text{QKD} &
  \\\text{Kon and Lim (2021)[2]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Classical DB)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Honest user, Prior entanglement}
  \\\end{array} &
  m^{O\\\left(\\\frac{\\\log \\\log k}{k \\\log k}\\\right)} &
  \\\text{Kerenidis and de Wolf (2004)[10]} \\\\\\\\\
  \\\hline
  \\\text{Quantum PIR (Quantum DB)} & – & – & – \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qubit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(1) \\\text{ qubits} + O(1) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Qudit states)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(d^d \\\log d) \\\text{ qubits} + O(d^d \\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\text{Quantum SPIR (Commutative unitaries)} &
  \\\begin{array}{c}
  \\\text{Non-communicating servers}, \\\\\\\\\
  \\\text{Prior entanglement, Visible setting}
  \\\end{array} &
  O(f) + O(\\\log d) \\\text{ qubits} + O(\\\log d) \\\text{ ebits} &
  \\\text{Song and Hayashi (2021)[1]} \\\\\\\\\
  \\\hline
  \\\end{array}$$

  References

  ---

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
  3. Chor et al. (1995)
  4. Baumeler, Ämin, and Anne Broadbent. “Quantum private information retrieval has linear communication complexity.” Journal of Cryptology 28, no. 1 (2015): 161-175.
  5. Aharonov, Dorit, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. “On quantum advantage in information theoretic single-server PIR.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 219-246. Cham: Springer International Publishing, 2019.
  6. Kerenidis, Iordanis, Mathieu Lauriere, F. Le Gall, and Mathys Rennela. “Information cost of quantum communication protocols.” (2016).
  7. Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
  8. Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. “Quantum private queries.” Physical review letters 100, no. 23 (2008): 230502.
  9. 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, pp. 151-160. 1998.
  10. Kerenidis, Iordanis, and Ronald De Wolf. “Quantum symmetrically-private information retrieval.” Information Processing Letters 90, no. 3 (2004): 109-114.
• 2025-05-15 at 13:58 by JuliaM
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  No protocols implement this functionality yet.

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

  acheck

  Multi-database case

  References

  ---

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.
• 2025-05-15 at 13:52 by JuliaM
  Show/Hide Content

  Functionality Description

  ---

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

  Protocols

  ---

  No protocols implement this functionality yet.

  Classical Analogues

  ---

  No content has been added to this section, yet!

  Real-world Use Cases

  ---

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

  Properties

  ---

  Security definitions

  (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

  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.

  Further Information

  ---

  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.

  • $f$ : number of database elements (quantum states in the ‘fully’ quantum setting);
  • $m$ : total size of database elements (i.e., the sum of the sizes, in bits, of each database element);
  • $d$ : dimension of the quantum states stored in the quantum database ($d=2$if they are qubits);
  • $k$ : number of servers (or equivalently of replicated databases).

  Single database case

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

  References

  ---

  1. Song, Seunghoan, and Masahito Hayashi. “Quantum private information retrieval for quantum messages.” In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1052-1057. IEEE, 2021.
  2. Kon, Wen Yu, and Charles Ci Wen Lim. “Provably secure symmetric private information retrieval with quantum cryptography.” Entropy 23, no. 1 (2020): 54.

← Back to post