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

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

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.

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}$$

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.