Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution

This example protocol performs the task of symmetric private information retrieval (SPIR) and has information-theoretic security. It is based on a quantum oblivious key distribution scheme. Like any quantum private queries protocol, it is cheat-sensitive, in the sense that user privacy relies on the non-zero probability for a cheating server to be detected. As for data privacy, the amount of information accessed by the user about the database is bounded.

Tags: Quantum Enhanced Classical Functionality, Specific Task, Two Party Protocol, Information-Theoretic Security, Symmetric Private Information Retrieval, Quantum Private Queries, Quantum Key Distribution, Quantum Oblivious Key Distribution, Single-Database.

Assumptions

The security of this protocol relies on fundamental physics principles:

• Impossibility of superluminal communication (for user privacy).
• Impossibility to deterministically discriminate non-orthogonal states (for database privacy).

To achieve perfect user privacy, one must make the following assumption:

• The server (Bob) will not cheat if he has a non-zero probability of being caught cheating.

Outline

A user, Alice, wants to retrieve an element from a database owned by a server, Bob, without revealing to Bob which element was retrieved (user privacy). Bob wants the amount of information that Alice can get on other database elements than the desired one to be bounded (data privacy).

• Quantum oblivious key distribution: Alice and Bob perform a quantum key distribution (QKD) protocol in such a way that at the end of the protocol, Alice and Bob share a bit string known entirely to Bob and in a quarter to Alice: such a protocol is referred to as quantum oblivious key distribution. Then the key length is reduced to match the size of the database, while ensuring that Alice knows approximately one bit of the new key (the position of the known bit is unknown to Bob).
  
  
• Query: Alice announces to Bob a (classical) shift corresponding to the difference between the index of the known bit of the key and the index of the desired database element.
  
  
• Answer: Bob encodes the database by bitwise adding the key, shifted by Alice’s shift. Then Bob announces the encoded database.
  
  
• Retrieval: By adding bitwise the shifted key to the encoded database, Alice can recover each database element for which she knew the corresponding (shifted) bit of the key.

Notation

• $N$: number of elements in the database.
• $X$: database; $X_{n}$: $n^{\text{th}}$ database element.
• $i$: index of the desired database element
• $j$: index of a bit of the QKD key known to Alice.
• $k$: a security parameter for the QKD key.
• $|\uparrow \rangle ,|\downarrow \rangle ,|\leftarrow \rangle ,|\rightarrow \rangle$: BB84 states.
• $\updownarrow$: $\{|\uparrow \rangle ,|\downarrow \rangle \}$ basis.
• $\leftrightarrow$: $\{|\leftarrow \rangle ,|\rightarrow \rangle \}$ basis.
• $K^{f}$: key used to encode the database; it is a random bit string of length $N$.
• $C$: encoded database (by bitwise adding the shifted QKD key).

Requirements

User (Alice):

• Can measure single qubits.

Server (Bob):

• Can prepare single qubits.

Communication:

• A quantum channel.
• A classical authenticated channel.

Properties

• User privacy: In the case of an honest server (Bob), there is perfect user privacy as Alice never communicates about the index of her known bit of the key. However, there are strategies that allow a malicious server to infer which bit of the key is known to Alice; but any such strategy implies a loss of knowledge on the bit value of this specific key element, and so Bob may introduce errors in the encoding of the database that would automatically be detected by Alice. Hence, assuming that the server will not cheat if there is a non-zero probability of being caught cheating, this protocol ensures perfect user privacy.
  
  
• Data privacy: An honest Alice may know more than one bit of the final QKD key as the number of bits known to her is probabilistic; this means she could access as many extra database elements with certainty as the number of extra bits of the key that she knows. Moreover, for any other database elements whose encoding is unknown to an honest Alice, she has a 50% chance of guessing correctly the corresponding key element. There are some cheating strategies that increase this probability; however, its increase is constrained by the choice of the security parameter $k$. Lastly, it is important to note that a cheating Alice cannot be detected by Bob.

Protocol Description

Inputs:

• User (Alice): index $i$ of the desired database element.
• Server (Bob): classical database $X$ with $N$ elements: $X_{1},...,X_{N}$.
• Both (Alice & Bob): a security parameter $k$.

Output:

• User (Alice): desired database element $X_{i}$.

Protocol:

• Quantum oblivious key distribution:

1. Bob generates a random bit string of length $k\times N$.
2. Bob encodes each bit of the string in the state of a qubit belonging to one of two bases $\updownarrow :=\{|\uparrow \rangle ,|\downarrow \rangle \}$ or $\leftrightarrow :=\{|\leftarrow \rangle ,|\rightarrow \rangle \}$: for each bit, if it is $0$, Bob chooses between $|\uparrow \rangle$ and $|\downarrow \rangle$, if it is $1$, Bob chooses between $|\leftarrow \rangle$ and $|\rightarrow \rangle$.
3. Bob sends the prepared qubits to Alice.
4. Alice measures each state in the $\updownarrow$ basis or $\leftrightarrow$ basis at random.
5. Alice announces to Bob in which instances she detected the sent qubit.
6. For each qubit that Alice successfully detected, Bob announces a pair of two states including the state that was sent. The other state is chosen at random in the other basis.
7. Partial reconstruction of the key: Using her measurement outcomes and Bob’s announced pairs of qubits, Alice can deduce the bit value of part of the key ($1/4$ of conclusive results).

At this stage, Alice and Bob share a secret key of length $k\times N$ which is known partially (${1/4}^{\text{th}}$) to Alice and entirely to Bob. Bob does not know which bits of the key are known to Alice.

1. Reduction of the key length: The key is cut into $k$ substrings of length $N$. Then pieces of the key are added bitwise to create a new key of length $N$, $K^{f}$. This reduces the number of bits of the new key that Alice knows to roughly one bit (ideally, Alice should know exactly one bit of the new key).

• Query: Alice announces to Bob a shift $s=j-i$ where $i$ is the index of the desired database element and $j$ is the index of a bit of the key known to Alice.
• Answer: Bob announces to Alice $N$ bits $C_{n}=X_{n}\oplus K_{n+s}^{f}$ corresponding to the encoded database.
• Retrieval: Alice recovers the desired database element $X_{i}$ by adding her known bit of the key, $K_{j}^{f}$ to the $i^{\text{th}}$ received bit $C_{i}$: $C_{i}\oplus K_{j}^{f}=X_{i}\oplus K_{i+s}^{f}\oplus K_{j}^{f}=X_{i}\oplus K_{i+j-i}^{f}\oplus K_{j}^{f}=X_{i}$.

Further Information

• The QKD part of this quantum private queries protocol is based on the SARG04 QKD scheme. However, any QKD protocol that is compatible with the SARG04 scheme would work.
• This protocol is loss resistant and scalable to large databases.

*contributed by Marine Demarty