In (single-server) Private Information Retrieval (PIR), a server holds a large database\({\mathtt {DB}}\) of sizen, and a client holds an index\(i \in [n]\) and wishes to retrieve\({\mathtt {DB}}[i]\) without revealingi to the server. It is well known that information theoretic privacy even against an “honest but curious” server requires\(\varOmega (n)\) communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (“input purification attack”).

Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity\(O(\sqrt{n})\), and a protocol by Kerenidis et al. (QIC 2016) with communication complexity\(O(\log (n))\), andO(n) shared entanglement.

We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion calledanchored privacy, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries.

Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).

1. 1.

   Throughout this work we will focus on the setting of binary database. We do note that there is vast literature concerned with optimizations for the case of larger alphabet.

2. 2.

   Setup refers to any information that is provided to the parties prior to the execution of the protocol by a trusted entity, but crucially one that does not depend on the parties’ inputs. Shared randomness or shared entanglement are common examples.

3. 3.

   As [DNS10] point out, their model is stronger, i.e. excludes a larger class of attacks, compared to the honest but curious model, even when restricted to a completely classical setting.

4. 4.

   More accurately, indistinguishability is required to hold even in the presence of an environment which can be arbitrary correlated (or entangled) with the parties’ inputs. In the quantum setting this usually corresponds to the environment.

5. 5.

   We note that to the best of our understanding, even prior “entropic” results such as [JRS09] seem to fall short of capturing the potential additional power of shared entanglement. This is essentially due to the property that ifAB are entangled, then it is possible that the reduced state ofB will have (much) higher von Neumann entropy than the jointAB (whose entropy might even be 0).

6. 6.

   This is because we can include the purification register at any point, as the server could have included himself rather than throwing it away.

7. 7.

   We make one minor adaptation – see Remark B.1.

We thank the anonymous referees for presenting us with the work of Kerenidis et al. [KLGR16], and other valuable comments. ZB is supported by the Israel Science Foundation (Grant 468/14), Binational Science Foundation (Grants 2016726, 2014276), and by the European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482) and via Project PROMETHEUS (Grant 780701). OS is supported by ERC Grant 280157, by the Israel Science Foundation (Grant 682/18), and by the Cyber Security Research Center at Ben-Gurion University. CYL is financially supported from the Young Scholar Fellowship Program by Ministry of Science and Technology (MOST) in Taiwan, under Grant MOST107-2636-E-009-005. KMC is partially supported by 2016 Academia Sinica Career Development Award under Grant No. 23-17 and the Ministry of Science and Technology, Taiwan under Grant No. MOST 103-2221- E-001-022-MY3. DA and AG were supported by ERC Grant 280157 for part of the work on this project, and are supported by the Israel Science Foundation (Grant 1721/17).

Authors and Affiliations

1. Hebrew University, Jerusalem, Israel

   Dorit Aharonov & Ayal Green

2. Weizmann Institute of Science, Rehovot, Israel

   Zvika Brakerski

3. Academia Sinica, Taipei, Taiwan

   Kai-Min Chung & Ching-Yi Lai

4. Ben-Gurion University, Beersheba, Israel

   Or Sattath

Corresponding author

Correspondence toDorit Aharonov.

Editors and Affiliations

1. Technion, Haifa, Israel

   Yuval Ishai

2. COSIC Group, KU Leuven, Heverlee, Belgium

   Vincent Rijmen

A Hilbert Spaces and Quantum States

The Hilbert space of a quantum systemA is denoted by the corresponding calligraphic letter\(\mathcal{A}\) and its dimension is denoted by\(\dim (\mathcal{A})\). Let\(L(\mathcal{A})\) be the space of linear operators on\(\mathcal{A}\). A quantum state of systemA is described by adensity operator\(\rho _A\in L(\mathcal{A})\) that is positive semidefinite and with unit trace\((\text {tr}(\rho _A)=1)\). Let\(S(\mathcal{A})= \{ \rho _A\in L(\mathcal{A}): \rho _A\ge 0, \text {tr}(\rho _A)=1\}\) be the set of density operators on\(\mathcal{A}\). When\(\rho _A\in S(\mathcal{A})\) is of rank one, it is called apure quantum state and we can write\(\rho =|{\psi }\rangle \langle {\psi }|_A\) for some unit vector\(|{\psi }\rangle _A\in \mathcal{A}\), where\(\langle {\psi }|=|{\psi }\rangle ^{\dag }\) is the conjugate transpose of\(|{\psi }\rangle \). If\(\rho _A\) is not pure, it is called amixed state and can be expressed as a convex combination of pure quantum states.

The Hilbert space of a joint quantum systemAB is the tensor product of the corresponding Hilbert spaces\(\mathcal{A}\otimes \mathcal{B}\). For\(\rho _{AB}\in S(\mathcal{A}\otimes \mathcal{B})\), its reduced density operator in systemA is\(\rho _A=\text {tr}_B(\rho _{AB})\), where

for an orthonormal basis\(\{|{i}\rangle _B\}\) for\(\mathcal{B}\). We sometimes use the equivalent notation,

Suppose\(\rho _A\in S(\mathcal{A})\) of finite dimension\(\dim (\mathcal{A})\). Then there exists\(\mathcal{B}\) of dimension\(\dim (\mathcal{B})\ge \dim (\mathcal{A})\) and\(|{\psi }\rangle _{AB}\in \mathcal{A}\otimes \mathcal{B}\) such that

The state\(|{\psi }\rangle _{AB}\) is called a purification of\(\rho _A\).

The trace distance between two quantum states\(\rho \) and\(\sigma \) is

where\(||X||_{\mathrm {tr}}=\frac{1}{2}\text {tr}{\sqrt{X^{\dag }X}}\) is the trace norm ofX. Hence the trace distance between two pure states\(|{\alpha }\rangle , |{\beta }\rangle \) is

Lemma A.1

Consider a quantum state\(\rho _{XY}\) over two registersX, Y, and denote\(\rho _X = \text {tr}_{Y}(\rho _{XY})\). Then if there exists\(\epsilon , |{\varphi }\rangle \) s.t.\(\varDelta (\rho _X, |{{\varphi }}\rangle \langle {{\varphi }}|) \le \epsilon \), then there exists\(\tilde{\rho }_Y\) s.t.\(\varDelta (\rho _{XY}, |{{\varphi }}\rangle \langle {{\varphi }}| \otimes \tilde{\rho }_Y) \le \sqrt{\epsilon }\). Furthermore, if\(\rho _{XY}\) is pure then so is\(\tilde{\rho }_Y\).

Proof

It is sufficient w.l.o.g to prove for a pure\(\rho _{XY}\), since it is always possible to purify\(\rho _{XY}\) by adding an additional registerZ, and consider the pure state\(\rho _{XYZ}\). The transitivity of the partial trace operation implies that if the theorem is true forX, (YZ), then it is also true forX, Y. Also assume w.l.o.g that\(|{\varphi }\rangle =|{0}\rangle \) (this is just a matter of choosing a basis elements).

Thus we will provide a proof in the case where the joint state ofX, Y can be written as a superposition\(|{\alpha }\rangle = \sum _{x,y} w_{x,y} |{x}\rangle |{y}\rangle \). Define\(P_0 = \Pr [X=0] = \sum _{y} \left| {w_{0,y}} \right| ^2\), and note that it must be the case that\(P_0 \ge 1-\epsilon \). To see this, note that\(P_0\) is the probability of measuring\(X=0\) in the experiment where we first trace outY and then measuringX. Since\(\varDelta (\rho _X, |{{0}}\rangle \langle {{0}}|) \le \epsilon \), the probability of measuring\(X=0\) after tracing outY is\(\epsilon \) close to the probability of measuring\(X=0\) in\(|{{0}}\rangle \langle {{0}}|\), which is 1 (see, e.g., [AKN98]). The claim\(P_0 \ge 1-\epsilon \) follows.

Now define\(|{\beta }\rangle = \tfrac{1}{\sqrt{P_0}} \sum _y w_{0,y} |{y}\rangle \), and let\(\tilde{\rho }_Y = |{{\beta }}\rangle \langle {{\beta }}|\). Then

We have

which implies that indeed\(\varDelta (\rho _{XY}, |{{0}}\rangle \langle {{0}}| \otimes \tilde{\rho }_Y) = \sqrt{1-P_0} \le \sqrt{\epsilon }\).    \(\square \)

B Security Analysis of Kereneidis et al.’s Protocol

For completeness, we restate^Footnote7 the QPIR protocol with pre-shared entanglement by Kerenidis et al. [KLGR16, Section 6]. Given a database\({\mathtt {DB}}\in \{0,1\}^{n}\) for some\({n}=2^{\ell }\) as input to the server, and index\(i \in [{n}]\) as input to the client (If the client’s input is a superposition, the algorithm is run in superposition), we denote the protocol\(\varPi _{n}\) as follows.

The protocol\(\varPi _{n}\) is recursive and calls\(\varPi _{{n}/2}\) as a subroutine. For the execution of\(\varPi _{n}\), the parties are required to pre-share a pair of entangled state registers\(\tfrac{1}{2^{{n}/4}}\sum _{\mathbf {{r}}\in \{0,1\}^{{n}/2}} |{\mathbf {{r}}}\rangle _R |{\mathbf {{r}}}\rangle _{R'}\), whereR is held by the server and\(R'\) is held by the client. They also share an entangled state needed for the recursive application of the protocol\(\varPi _{{n}/2}\) (and the recursive calls it entails). Unfolding the recursion, this means that for all\({n}'=2^{{\ell }'}\) with\({\ell }' \in [{\ell }-1]\), there is an entangled register of length\({n}'\) shared between the client and the server.

The protocol execution is described in shorthand Fig. 1. In what follows we provide a detailed description and analyze the steps of the protocol to establish correctness and assert properties that will allow us to analyze privacy.

1. 1.

   If\({n}=1\) then the database contains a single value. In this case there is no need for shared entanglement, and the server sends a registerF containing\(|{{\mathtt {DB}}}\rangle \) (the final response) to the client, and the protocol terminates. This is trivially secure and efficient. Otherwise proceed to the next steps.

2. 2.

   The server denotes\({\mathtt {DB}}_0, {{\mathtt {DB}}}_1 \in \{0,1\}^{{n}/2}\) s.t.\({\mathtt {DB}}= [{{\mathtt {DB}}}_0 \Vert {\mathtt {DB}}_1]\), i.e. the low-order and high-order bits of the database respectively. The server starts with two single-bit registers\(Q_0, Q_1\) initialized to 0. The server CNOTs\(Q_b\) with the inner product ofR and\({\mathtt {DB}}_b\) so that it contains\(|{\mathbf {{r}}\cdot {\mathtt {DB}}_b}\rangle _{Q_b}\), and sends\(Q_0, Q_1\) to the client. At this point, the joint state between the client and (an honest) server is

   $$\begin{aligned} \sum _{\mathbf {{r}}\in \{0,1\}^{{n}/2}} |{\mathbf {{r}}}\rangle _R |{\mathbf {{r}}}\rangle _{R'} |{\mathbf {{r}}\cdot {\mathtt {DB}}_0}\rangle _{Q_0} |{\mathbf {{r}}\cdot {\mathtt {DB}}_1}\rangle _{Q_1}. \end{aligned}$$

   In particular the reduced density matrix of the server’s state is independent of the indexi.

3. 3.

   Let\(b^*=\lfloor \tfrac{i-1}{{n}} \rceil \) denote the most significant bit ofi. The client evaluates aZ gate on\(Q_{b^*}\). It sends\(Q_0, Q_1\) back to the server. At this point, the joint state between the client and (an honest) server is

   $$\begin{aligned} \sum _{\mathbf {{r}}\in \{0,1\}^{{n}/2}} (-1)^{\mathbf {{r}}\cdot {\mathtt {DB}}_{b^*}} |{\mathbf {{r}}}\rangle _R |{\mathbf {{r}}}\rangle _{R'} |{\mathbf {{r}}\cdot {\mathtt {DB}}_0}\rangle _{Q_0} |{\mathbf {{r}}\cdot {\mathtt {DB}}_1}\rangle _{Q_1}. \end{aligned}$$

   Importantly, the reduced density matrix of the server, which contains the registers\(R, Q_0, Q_1\), is the diagonal matrix that corresponds to the classical distribution of sampling a random\(\mathbf {{r}}\) in registerR, and placing\(\mathbf {{r}}\cdot {\mathtt {DB}}_0, \mathbf {{r}}\cdot {\mathtt {DB}}_1\) in\(Q_0, Q_1\). This density matrix is independent of\(b^*\) and therefore ofi.

4. 4.

   The server again CNOTs\(Q_b\) with the inner product ofR and\({\mathtt {DB}}_b\). At this point, the joint state between the client and (an honest) server is

   $$\begin{aligned} \sum _{\mathbf {{r}}\in \{0,1\}^{{n}/2}} (-1)^{\mathbf {{r}}\cdot {\mathtt {DB}}_{b^*}} |{\mathbf {{r}}}\rangle _R |{\mathbf {{r}}}\rangle _{R'} |{0}\rangle _{Q_0} |{0}\rangle _{Q_1}. \end{aligned}$$

   From this point on we disregard\(Q_0, Q_1\) since they remain zero throughout. Since this step only involves a local unitary by the server, we are guaranteed that its reduced density matrix is still independent ofi.

5. 5.

   The server performs QFT onR and the client performs QFT on\(R'\). The resulting state is

   $$\begin{aligned} \tfrac{1}{2^{3 {n}/4}} \sum _{\mathbf {{r}},\mathbf {{y}},\mathbf {{w}} \in \{0,1\}^{{n}/2} } (-1)^{\mathbf {{r}}\cdot ({\mathtt {DB}}_{b^*}\oplus \mathbf {{y}}\oplus \mathbf {{w}})} |{\mathbf {{y}}}\rangle _R |{\mathbf {{w}}}\rangle _{R'} = \tfrac{1}{2^{{n}/4}} \sum _{\mathbf {{y}} \in \{0,1\}^{{n}/2} } |{\mathbf {{y}}}\rangle _R |{\underbrace{\mathbf {{y}} \oplus {\mathtt {DB}}_{b^*}}_{\mathbf {{w}}}}\rangle _{R'}. \end{aligned}$$

   Since we only performed local operations on the server and client side (without communication), the server’s density matrix remains perfectly independent of\(b^*\) and thus ofi.

6. 6.

   Note that at this point, the joint state of the client and server is a “shifted” entangled state where the shift corresponds to the half-database\({\mathtt {DB}}_{b^*}\) that contains the element that the client wishes to retrieve. More explicitly,\({\mathtt {DB}}[i] = {\mathtt {DB}}_{b^*}[i^*]\) for\(i^*=i \pmod {{n}/2}\) contains the\(({\ell }-1)\) least significant bits ofi. Therefore, for all\(\mathbf {{y}}, \mathbf {{w}}\) in the support of the joint state, it holds that\({\mathtt {DB}}[i] = \mathbf {{w}}[i^*] \oplus \mathbf {{y}}[i^*]\). The client will now ignore (temporarily) the register\(R'\) and execute\(\varPi _{{n}/2}\) recursively on index\({i}^*\). The (honest) server will carry out the protocol with the value\(\mathbf {{y}}\) from the registerR serving as the server’s database. Note that since the register\(R'\) is not touched, for the purposes of executing the protocol the value\(\mathbf {{w}}\) in\(R'\) is equivalent to have been measured, and the value\(\mathbf {{y}}\) inR is equivalent to the deterministic register\(\mathbf {{w}}\oplus {\mathtt {DB}}_{b^*}\). We are recursively guaranteed that in the end of the execution of\(\varPi _{{n}/2}\), the client receives a registerF containing the value\(\mathbf {{y}}[i^*] = \mathbf {{w}}[i^*]\oplus {\mathtt {DB}}_{b^*}[i^*] = \mathbf {{w}}[i^*]\oplus {\mathtt {DB}}[i]\). Since the client still maintains the original register\(R'\) containing\(\mathbf {{w}}\), it can CNOT the value\(\mathbf {{w}}[i^*]\) fromF and obtain\(|{{\mathtt {DB}}[i]}\rangle _A\). Namely, in the end of the execution, the registerF indeed contains the desired value\({\mathtt {DB}}[i]\).

7. 7.

   Lastly, if the client and server desire to “clean up” and restore the shared entanglement so that it can be reused in consequent executions, the client can copy the contents of the registerF to a fresh register (which is possible since this register contains a classical value). Since the client and server are pure (i.e. do not measure) throughout the protocol, they can rewind the execution of the protocol to restore their initial joint entanglement.

If the final cleanup step is not executed then the total number of rounds of\(\varPi _{{n}}\) is\(2 {\ell } + 1\), and the total communication complexity is\(4l+1\) (recall that\({\ell } = \log ({n})\)). If the cleanup step is executed, the round complexity and communication complexity are doubled due to rewinding the execution.

Remark B.1

Note that in the original protocol by Kerenidis et al. step 7 does not appear, and it is not mentioned that the shared entanglement can be cleaned and reused.

Lemma B.2

The protocol\(\varPi _{n}\) is a PIR protocol with perfect correctness and perfect anchored privacy against honest servers. It furthermore has communication complexity\(O(\log {n})\), and uses\(O({n})\) bits of (reusable) shared entanglement.

Proof

The analysis in the body of the protocol establishes that the local view of the adversary is independent of the inputi, wheni is treated as a fixed (classical) parameter. Next, we show that the server’s local state is independent of the client’s input, even when the input is an arbitrary quantum state.

We observe two facts: (i) since we are interested in the server’s local view, the input register is traced out, (ii) the client interacts with its input qubits as control bits for Controlled operations only. By property (i), we can assume for the sake of the analysis that the qubits are measured just before tracing them out. Using property (ii), the entire protocol commutes with a measurement in the standard basis of the input register. Therefore, we can assume the server’s local view would not be changed by adding a measurement in the standard basis of the input register at the very beginning of the protocol. By the argument in the previous paragraph, we already know that for a classical input, the server’s local view is independent of the input. The measurement in the standard basis collapses the state a classical, and we conclude that the server’s local view is independent of the input, for any input state.

In order to comply with the simulation based privacy definition (see Definition 2.5), we can define the simulators to be simulations of the protocol run with input\(i=|{{0}}\rangle \langle {{0}}|\). Since the server’s state is independent of the input, we complete the proof that the protocol has perfect anchored privacy against honest servers.

The communication complexity and the amount of reusable shared entanglement needed in this protocol follow directly from the protocol.    \(\square \)

We can therefore apply Theorem 3.2 and conclude that\(\varPi \) is secure against anchored-specious adversaries.

Corollary B.3

There exists a PIR protocol\(\varPi \) with logarithmic communication complexity assuming linear shared entanglement, which is perfectly correct and anchored\(O(\sqrt{\gamma })\)-private against\(\gamma \)-specious adversaries.

The QPIR protocol of Kerenidis et al.

Full size image

Reprints and permissions

© 2019 International Association for Cryptologic Research

Policies and ethics