(Symmetric) Private Information Retrieval

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

Apart from using quantum techniques to enhance the classical functionality (i.e., design better protocols than their classical counterparts in terms of different metrics like e.g., communication complexity), there has also been a recent interest in a ‘fully’ quantum (S)PIR where a user wants to query a quantum database (items are quantum states)[1].

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

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.

Protocols

Classical database

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

Single-database protocols

As in the classical setting, in the case of the database being owned by a single server, the trivial solution (downloading the whole database) is the only way to achieve information-theoretically secure PIR – even in the case of a specious (may deviate from the protocol if its malicious operations are unknown to the user) server [2].
As for (quantum or classical) SPIR, it is impossible to achieve information-theoretic security with a single-server; this result was proved in the quantum setting by Lo [3]. Therefore, to design efficient PIR protocols or to achieve SPIR, several assumptions have been considered; they include:

• Hardness assumptions: PIR protocols with computational security.
• Assumptions on the adversarial model:
  • to achieve SPIR: cheat-sensitive protocols (also known as quantum private queries (QPQ) protocols) where it is assumed that the server will not cheat if there is a non-zero probability that he will be caught cheating.
    • QPQ protocols based on quantum oblivious key distribution
    • QPQ protocols based on sending quantum states to an oracle
  • to achieve efficient PIR: assuming an honest server.
    • QPIR protocols in the honest server model
• Prior shared entanglement between server and user: in the honest server model, efficient PIR protocols exist, however for a specious or malicious server, the trivial solution is optimal for PIR[4].
  • QPIR protocols with prior shared entanglement in the honest server model
• Relativistic assumptions: quantum SPIR protocols whose security uses properties from special relativity.
  • Relativistic QOT protocols

Nota bene: single-database (Q)SPIR and one-out-of-n (quantum) oblivious transfer ((Q)OT) are similar cryptographic tasks.

Multi-database protocols

It is possible to achieve information-theoretic (S)PIR with reduced communication complexity (i.e., compared to this of the trivial solution) by considering several servers instead of one, each holding a copy of the database, and with the help of extra assumptions. Usually, to achieve (S)PIR, it is assumed that the servers cannot communicate with each other during and after the protocol ended (no-communication assumption), and that servers share randomness (in the symmetric case only). Examples of such protocols are:

• Quantum multi-database SPIR protocols without shared randomness (replaced by prior shared entanglement between servers)
• Classical multi-database SPIR protocols with QKD secured classical channels
• Multi-database quantum (S)PIR protocols for communicating and colluding servers – to do without the no-communication assumption
• Multi-database quantum (S)PIR protocols for coded servers

Quantum database

For the case of a quantum database, the trivial solution of downloading the whole database is proved to be optimal for one-round QPIR, and for multi-round QPIR in the blind setting (i.e., the servers do not have a classical description of the quantum states of the database) and for the honest server model (and any other attack model)[1].

Prior shared entanglement between the user and the server allows for efficient one-server QPIR protocols in the honest server model and in the blind setting. Multi-database QSPIR protocols for a quantum database with pure states, in the visible setting (servers know a classical description of the quantum database elements) exist as shown by Song and Hayashi [1].

• Single-database quantum PIR protocols in the honest server model and in the blind setting for a quantum database
• Multi-database quantum SPIR protocols in the visible setting for a quantum database

References

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

*contributed by Marine Demarty