Capacity of Quantum Private Information Retrieval with Colluding Servers

Quantum private information retrieval (QPIR) is a protocol that a user retrieves a file from non-communicating $\vN$ servers by downloading quantum systems without revealing the identity of the target file. We study the $\vT$-private QPIR that the identity of the target file is kept secret even if at most $\vT$ servers may collude to reveal the identity. As a result, we prove that the $\vT$-private QPIR capacity is $1$ for $1\leq \vT \leq \vN/2$ and $2(\vN-\vT)/\vN$ for $\vN/2<\vT<\vN$, where the QPIR capacity is the maximum rate of the file size over the size of downloaded quantum systems. We construct a capacity-achieving QPIR protocol with zero-error and perfect user secrecy against the collusion of $\vT$ servers. Our protocol also achieves the server secrecy, i.e., the user obtains no other information than the target file. We also prove the optimality of our protocol with converse bounds.


I. INTRODUCTION
When a user retrieves information from databases, it is often required to protect the privacy of the user. Private information retrieval (PIR) is the problem to retrieve one of f files from non-communicating n servers without revealing to each individual server which file is downloaded. Chor, Goldreich, Kushilevitz, and Sudan [1] originally considered this problem for one server and one-bit files, and proved that the optimal communication complexity is O(f), i.e., downloading all files in the server is optimal. They also considered a PIR protocol with multiple servers, and along with the following works [2]- [4], the communication complexity is significantly improved. Furthermore, on PIR with multiple servers and in the case where the file size is allowed to be arbitrarily large, Sun and Jafar [5] started to discuss the PIR capacity which is the maximum rate of the file size over the download size, and derived that the PIR capacity is (1 − 1/n)/(1 − (1/n) f ). PIR with large file size and PIR capacities have also been derived in many other settings [6]- [19].
On the other hand, in recent years, there has been a growing interest in quantum communication as a means to overcome the limitations of existing communication technologies. Above all, there has been a great deal of interest in enhancing security and efficiency, and thus, the quantum PIR (QPIR) has also been studied [20]- [27]. Le Gall [24] showed that the communication complexity for the one-server QPIR for f one-bit files is enhanced as O( √ f). For multi-server QPIR, the paper [26] derived that the QPIR capacity is 1, and the proposed QPIR protocol achieves the capacity only with two servers. Whereas the papers [20]- [25] considered the QPIR model with quantum upload and quantum download, the papers [26], [27] considered the QPIR model with the classical upload and quantum download but instead allowing an entangled state is shared among servers before the protocol starts.
In PIR, the user may obtain some information on the n − 1 non-target files. Therefore, it is preferable to consider the server secrecy that the user obtains no information other than the target file. The PIR with the server secrecy is called symmetric PIR, which is also called oblivious transfer [28] in one-server case. The paper [29] proved that shared randomness among servers is necessary to construct symmetric PIR protocols. Assuming the shared randomness among servers, the paper [7] derived that the symmetric PIR capacity is 1 − n −1 . In quantum case, the paper [21] proved that the symmetric QPIR can be implemented if quantum upload and quantum download are available. This result fundamentally follows from the fact that the quantum upload may generate entanglement among the user and the servers. t-Private PIR 1 − t/n 1 − (t/n) f [8] 1 for t ≤ n/2 ‡ 2(n − t) n for n/2 < t ‡ t-Private symmetric PIR n − t n [16] † * n, f: the numbers of servers and files, respectively. † Shared randomness among servers is necessary. ‡ Capacities are derived with the strong converse bounds.
Furthermore, one weakness of the multi-server PIR is the assumption of no communication among servers. To relieve this assumption, PIR has also been studied even in the case where some of the servers may collude. The t-private PIR is the PIR with stronger user secrecy, called user t-secrecy or t-privacy, that the identity of the retrieved file is unknown to any collection of t servers. The paper [8] proved that the t-private PIR capacity is (1 − (t/n))/(1 − (t/n) f ) for any 1 ≤ t < n. Assuming the shared randomness among servers, the paper [16] derived that the symmetric t-private PIR capacity is (n − t)/n. On the other hand, in quantum case, the paper [27] proved that the symmetric (n − 1)-private QPIR capacity is 2/n for even number n of servers, but it is unknown for 1 ≤ t < n − 1.
As an extension of the capacity results in [26], [27], we consider the symmetric t-private QPIR capacity for 1 ≤ t < n, where n is the number of servers. Similarly to the papers [26] and [27], we define the QPIR model as follows: a user retrieves one of m files from n non-communicating servers each of which contain the whole classical file set; the servers share an entangled state before the protocol starts; and the user uploads classical queries, downloads quantum systems, and recover the target file by quantum measurement. The capacity is defined with four security parameters: error probability, server secrecy, user t-secrecy, and upload cost. As a main result, we prove that the symmetric t-private QPIR capacity is 1 for 1 ≤ t ≤ n/2 and 2(n − t)/n for n/2 < t < n. We also construct the capacity-achieving protocol by stabilizer formalism, and presents the converse bounds for 1 ≤ t ≤ n/2 and n/2 < t < n, respectively.
Our result implies that for 1 ≤ t ≤ n/2, the symmetric t-private QPIR capacity is 1 regardless of requiring the strongest security condition that the protocol has zero-error, perfect user t-secrecy, and perfect server secrecy, or requiring the weakest security condition that the protocol has arbitrary error less than 1, no user t-secrecy, and no server secrecy. This implies that the QPIR guarantees the user ⌊n/2⌋-secrecy without sacrificing any communication rate. Furthermore, whereas the capacity result in [26] shows that there is no advantage over to use more than two servers in PIR without collusion, our result implies that QPIR with more servers can obtain the stronger secrecy against the collusion.
The remainder of the paper is organized as follows. Section II formally describes the QPIR protocol, defines the QPIR capacity, and presents the main results of the paper. Section III gives the preliminaries for code construction and Section IV constructs the capacity-achieving QPIR protocol with colluding servers. Section V presents the converse bounds of the capacity result. Section VI is the conclusion of the paper.
Terms and Notations: The matrix I n denotes the n × n identity matrix, and Pr X [q(X)] is the probability that X satisfies the condition q(X). The quantum information measures used in the paper is given in Appendix A.

II. QPIR MODEL AND MAIN RESULT
In this section, we formally state the definition of QPIR protocol and present the main result of the paper.

A. Description of QPIR Protocol
In this subsection, we review the description of the QPIR protocol given in [26], [27].

User
Target Index: K ∈ {1, . . . , f} Colluding Servers . . , A ′ n be d ′ -dimensional Hilbert spaces. The state of the quantum system A ′ 1 ⊗ · · · ⊗ A ′ n is initialized as ρ prev , and is distributed such that the s-th server serv s contains A ′ s . The user chooses the file index K ∈ {1, . . . , f} uniformly and independently of M in order to retrieve the file M K . The user chooses a randomness R user from a set R user and encodes the index K to queries Q 1 , . . . , Q n , i.e., where Q 1 , . . . , Q n are finite sets. Then, the user sends Q s to the s-th server serv s (s = 1, . . . , n). Let A 1 , . . . , A n be d-dimensional Hilbert spaces. After receiving the query Q s , the s-th server serv s constructs a TP-CP map Λ s from A ′ s to A s by the server encoder as Enc servs (Q s , M ) = Λ s , applies Λ s on A ′ s , and sends A s to the user. Then, the state on A 1 ⊗ · · · ⊗ A n after server encoding is written as ρ M Q := Λ 1 ⊗ · · · ⊗ Λ n (ρ prev ).
The user decodes the received state by decoder. The decoder is defined as a positive-operator valued measure (POVM) Y KQ := {Y KQ (w) | w ∈ {0, . . . , m − 1}} on A 1 ⊗ · · · ⊗ A n , where the measurement outcome associated with Y KQ (w) is w. By the POVM, the user outputs the measurement outcome W as the retrieval result.
Given the numbers n, f of servers and files, the QPIR protocol is defined by the four-tuple B. Security Parameters and Capacity of t-Private QPIR Given the number t ∈ {1, . . . , n − 1} of colluding servers, the security parameters and the capacity are defined. 1) Security Parameters: Let W be the protocol output, M c k be the collection of all files except for M k , S n be the symmetric group of {1, . . . , n}, i.e., the set of all permutations on {1, . . . , n}, and Q π,t := (Q π(1) , . . . , Q π(t) ) for π ∈ S n . The security of a QPIR protocol is evaluated by the error probability, server secrecy, and user t-secrecy: = max m=(m1,...,mn), k∈{1,...,f}, q∈Q1×···×Qn where I(·; ·|·) ρ is the quantum conditional mutual information.
Remark 1. The server secrecy is also written as This follows from QPIR ) ≤ β, the condition p kq = 0 implies p iq = 0 for any k = i ∈ {1, . . . , f}. Otherwise, we derive a contradiction as follows. If p kq , p iq = 0 for some k = i, the server secrecy S serv (Ψ (m) However, we have the following contradiction where (a) is derived from Lemma V.1.

C. Main Result
The following theorem is the main result of the paper.
Theorem II.1. The capacity of t-private QPIR with n ≥ 2 servers and f ≥ 2 files is for any α ∈ [0, 1) and any β, γ, θ ∈ [0, ∞], and The capacity-achieving QPIR protocol is constructed in Section IV for n/2 ≤ t < n. The protocol obtains zeroerror (P err (Ψ Since the user (n/2)-secrecy guarantees the user t-secrecy for 1 ≤ t < n/2, the constructed protocol for t = n/2 is also the capacity-achieving protocol for 1 ≤ t < n/2. The converse bounds are given in Section V. (13) is derived for the case where any server secrecy β ∈ [0, ∞) is allowed. However, one may notice that for some parameters (n, t, f), the capacity (13) is smaller than the capacity (1 − (t/n))/(1 − (t/n) f ) [8] of classical t-private PIR without server secrecy. For instance, when (n, t, f) = (4, 3, 2), the capacity (13) is 0.5 and the capacity in [8] is 0.57. This follows from the fact that the capacity (13) is derived for finite β but the capacity in [8] is derived for the case where the β is allowed to be infinite.

III. PRELIMINARIES FOR PROTOCOL CONSTRUCTION
In this section, we give preliminaries for our protocol construction in Section IV.

A. Stabilizer Formalism
Let F q be a finite field for a prime power q = p r , and A be a q-dimensional Hilbert space with a basis where ω := exp(2π √ −1/p). Here, we define tr x := Tr T x ∈ F p for x ∈ F q , where T x ∈ F r×r p denotes the matrix representation of the map y ∈ F q → xy ∈ F q by identifying the finite field F q with the vector space F r p . For a = (a 1 , . . . , a n ), b = (b 1 , . . . , b n ) ∈ F n q , define the following unitaries on A ⊗n : X(a) := X(a 1 ) ⊗ X(a 2 ) ⊗ · · · ⊗ X(a n ), where (14), all elements of S(V) are commutative, and therefore, are simultaneously diagonalized.
Since (16) is also written as where holds because for any v ∈ V, Therefore, all eigenspaces A V [w] have the same dimension dim A ⊗n /|F 2n q /V ⊥J | = q n /q d = q n−d , and the quantum system A ⊗n is decomposed as where W is the d-dimensional subspace with the basis

B. Lemmas for code construction
In this subsection, we prepare two lemmas for the code construction.
Since X 2 = X and X * = X, the X is an orthogonal projection. Since |[w + w ′ ] ⊗ C q n−d is an invariant subspace of X and rank X = q n−d , the X is the orthogonal projection onto |[w + w ′ ] ⊗ C q n−d , which implies the lemma.
The following proposition is a slight generalization of the construction [31, Appendix A].
Proposition III.1. Let F p be the finite field of prime order p and F q be the algebraic extension F p (α 1 , . . . , α k−2 ), where α i ∈ F p (α 1 , . . . , α i−1 ) for any i. Given two positive integers r < k, define a matrix A = (a ij ) ∈ F (k−r)×r q such that Then, any r row vectors of the matrixĀ are linearly independent. In particular, when k = 2r, the square matrix A ∈ F r×r q is invertible.
Proof: Before we give the proof, we introduce the following notation: The following lemma is fundamental to guarantee the user t-secrecy in our protocol.

Define two square matrices
i.e., Since the matrix is a symplectic matrix if X is symmetric, the matrix is a symplectic matrix, where the inverse A −1 exists from Proposition III.1. With the notation Now, we prove that the row vectors of S ′ := (s 1 , . . . , s 2m ) satisfy condition (a). Since (i) the right multiplication of invertible matrices and (ii) elementary column operations do not change the linear independence of the row vectors, we manipulate the matrix S ′ in the following way: . By the above transformation, the linear independence of the row vectors of S ′ is equivalent to that of S ′′ . Let by adding the row vectors (I 2m−n , 0, 0) to S ′′ . If any 2m row vectors of S ′′′ are linearly independent, then S ′′ and S ′ also satisfy the same property. Since by applying Proposition III.1 for S ′′′ , any 2m row vectors of S ′′′ are linearly independent. Thus, the matrix S ′ also satisfies the same property as S ′′′ , which implies condition (a).

IV. CONSTRUCTION OF QPIR PROTOCOL WITH COLLUDING SERVERS
In this section, we construct the capacity-achieving QPIR protocol for n ≥ 2 servers, f ≥ 2 files, n/2 ≤ t < n colluding servers. For the collusion of 1 ≤ t < n/2 servers, the protocol for t = n/2 is the capacity-achieving protocol.

A. Construction of Protocol
Let n ≥ 2, f ≥ 2, and n/2 ≤ t < n. For the construction of the protocol, we choose a sufficiently large prime power q and a basis v 1 , . . . , v 2n of F 2n q such that the vectors v 1 , . . . , v 2t satisfy the conditions of Lemma III.2. Let V := span{v 1 , v 2 , . . . , v 2n−2t } ⊂ F 2n q . Then, from condition (b) of Lemma III.2, the subspace V is self-orthogonal with respect to ·, J· , V ⊥J = span{v 1 , . . . , v 2t }, and F 2n We assume that the vectors v 1 , . . . , v 2n are publicly known to the user and all servers. The target file index is k, i.e., the user retrieves m k .
The protocol is described as follows.

3) [Download]
For each s = 1, 2, . . . , n, the s-th server applies X(q ⊤ sX m)Z(q ⊤ sZ m) to A s and sends A s to the user.

4) [Recovery] The user applies the PVM
. The measurement outcome of the user is denoted by [w out ]. In the expansion

B. Analysis of Protocol IV.1
In this section, we analyze the performance of Protocol IV.1. First, we show that the user obtains m k without error. Let The state after the server encoding is where the equality holds from Lemma III.1. Thus, the measurement outcome is Since V 1 R ⊤ m is a vector in V ⊥J and the protocol output (c 2t+1 , c 2t+2 , . . . , c 2n ) ∈ F 2(n−t) q is independent of the representative of [w out ], the user obtains (c 2t+1 , c 2t+2 , . . . , c 2n ) = (m k,1 , . . . , m k,2(n−t) ) = m k without error.
The download cost is dim n s=1 A s = q n and the file size is |F 2(n−t) q | = q 2(n−t) , which implies that the QPIR rate is 2(n − t)/n.
The protocol has the perfect server secrecy because from (39), the state after server encoding is |[w ′ ] [w ′ ]|⊗ρ mix , which is independent of the non-retrieved files.
In the remainder of this section, we present the proof of (46). For any π ∈ S n , let Q π,t c := (Q π(t+1) , . . . , Q π(n) ), A π,t := t s=1 A π(s) , and A π,t c := n s=t+1 A π(s) . Let d t := d t and d t c := d n−t be the dimensions of A π,t and A π,t c , respectively. Let ρ M Qπ,t be the state of the t-colluding servers after the server encoding. The function h(x) is the binary entropy function h(x) : We prepare two lemmas. The security conditions (2), (3), and (4) give the following bounds.
The proof of Lemma V.1 is given in Appendix B. The quantities evaluated in Lemma V.1 can be considered as weak security conditions. We only use these quantities for the converse proofs. The following lemma is the fundamental lemma in the converse proof.
≤ I(M k ; A π,t Q π,t |M c k , K = k) ρMQ π,t (55) The equality (a) holds because Q π,t c is independent of M k and the state ρ M Qπ,t on A π,t . The inequality (c) follows from the server secrecy and the inequality (d) is from (47) and (48). The inequality (b) is derived as follows. From (49), the user t-secrecy S When we defineρ M Qπ,t|k := m,qπ,t (1/m) f · p Qπ,t=qπ,t|K=k · |m, q π,t m, q π,t | ⊗ ρ mqπ,t for k ∈ {1, . . . , f}, the inequality (63) implies that for any i = k ∈ {1, . . . , f}, where d is the trace distance d(ρ, σ) := (1/2) · Tr |ρ − σ| for quantum states ρ, σ. Thus, Fannes inequality for mutual information [30,Eq. (5.106)] implies that QPIR ) ≤ γ. Fix K = k and π ∈ S n . Let ρ w,z be the quantum state on the composite system n s=1 A s , where w is the file to be retrieved, i.e., the k-th file, and z := (m c , q) for the collection m c of non-retrieved f − 1 files and the collection q of queries. Let σ z := (1/m) m−1 w=0 ρ w,z . Considering the entire system A as a bipartite system A π,t ⊗ A π,t c , let σ z,t and ρ w,z,t be the reduced densities on A π,t of σ z and ρ w,z , respectively. Dependently of Z, we denote the decoding POVM by {Y w,Z } w . Then, we define the states R Z := m−1 w=0 (1/m)|w w| ⊗ ρ w,Z and S Z := m−1 w=0 (1/m)|w w|⊗σ Z,t ⊗I/d t c , and the operator Y Z := m−1 w=0 |w w|⊗Y w,Z . Considering the information processing inequality for the two-valued measurement {Y Z , I − Y Z }, we have where P err,k (Ψ (m) The equation (a) can be shown as follows.

VI. CONCLUSION
We have discussed the t-private quantum private information retrieval, where the identity of the target file is secret to the colluding t servers. We defined two secrecy parameters, the user t-secrecy and the server secrecy. The user t-secrecy is the secrecy that any collection of t queries contains no information of the user's request, and the server secrecy is the secrecy that the user obtains no information of the other files than the target file. We derived two capacities of the t-private QPIR, the exact and asymptotic security-constrained capacities. When the number t of colluding servers is less than or equal to a half of the number n of servers, the capacities are exactly 1 whether considering the security conditions or not, and if t > n/2, the capacities are 2(n − t)/n. For the proof of the capacity, we constructed a t-private QPIR protocol with perfect security conditions by the stabilizer formalism. The converse bounds are also derived, which complete the optimality of our protocol. One open problem is the t-private QPIR capacity for t ≥ n/2 when the server secrecy is not asymptotically negligible to the file size. It is also unknown the QPIR capacity without shared entanglement among servers.

APPENDIX C PROOFS OF (44) AND (45)
In the following proofs, we use the notations given in Section V. That is, given K = k and a permutation π ∈ S n , we denote A π,t := t s=1 A π(s) , A π,t c := n s=t+1 A π(s) , d t := dim A π,t = d t , d t c := dim A π,t c = d (n−t) , P err,k (Ψ (m) QPIR ) := Pr W,Mk [W = M k |K = k]. The state ρ w,z is the state on A = A π,t ⊗ A π,t c after server encoding, where w is the target file, i.e., the k-th file, and z := (m c , q) for the collection m c of all files except for w and the collection q of queries, the state ρ w,z,t is the reduced state on A π,t of ρ w,z . Define the state σ z := (1/m)· m−1 w=0 ρ w,z and the operator Y z := m−1 w=0 |w w| ⊗ Y w,z . Eq. (44) is proved as follows. Fix K = k. Applying [30, (4.66)] with σ Z and Y Z , we have QPIR ) = 0. We consider the case K = k and an arbitrary π ∈ S n is fixed. Since Lemma V.2 guarantees that the reduced density ρ w,z,t on A π,t does not depend on w, we denote it by ρ z,t . Applying [30, (4.66)] with ρ Z,t ⊗ (I/d t c ) and Y Z , we have for any r ∈ (0, 1). Given z and w, consider the decomposition ρ w,z = x p x |ψ w,z,x ψ w,z,x |. Let ρ z,x,t be the reduced density of |ψ w,z,x ψ w,z,x | on A π,t , i.e., ρ z = x p x ρ z,x,t . Then, where (98) is obtained by applying the inequality φ(−r|ρ σ) := log Tr ρ 1+r σ −r ≥ φ(−r|κ(ρ) κ(σ)) for states ρ, σ, TP-CP map κ, and r ∈ (0, 1) [30, (5.53)] to the choice ρ := x p x |x x| ⊗ |ψ w,z,x ψ w,z,x |, σ := x p x |x x| ⊗ (ρ z,x,t ⊗ I/d t c ) on the composite system X ⊗ A, and κ := Tr X . The last inequality (b) is shown as follows. Since ρ z,x,t is a reduced state of the pure state |ψ w,z,x in A π,t ⊗ A π,t c , we have rank ρ z,x,t ≤ min{dim A π,t c , dim A π,t c } = d t c , which implies Tr ρ 1−r z,x,t ≤ d r t c . Combining (97)  QPIR has the QPIR rate greater than 2(n − t)/n for any sufficiently large ℓ, then (D(Ψ (mℓ) QPIR )) 2(n−t)/n /m ℓ = d 2(n−t) /m goes to 0. Therefore, from (100), the probability 1 − P err,k (Ψ (mℓ) QPIR ) approaches to 0, which implies (45).