Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers

Abstract

Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple classical files by downloading quantum systems from non-communicating $\mathsf{n}$ servers each of which contains a copy of all files, while the identity of the retrieved file is unknown to each server. Symmetric QPIR (QSPIR) is QPIR in which the user only obtains the queried file but no other information of the other files. In this paper, we consider the $(\mathsf{n}-1)$-private QSPIR in which the identity of the retrieved file is secret even if any $\mathsf{n}-1$ servers collude, and derive the QSPIR capacity for this problem which is defined as the maximum ratio of the retrieved file size to the total size of the downloaded quantum systems. For an even number n of servers, we show that the capacity of the $(\mathsf{n}-1)$-private QSPIR is $2/\mathsf{n}$, when we assume that there are prior entanglements among the servers. We construct an $(\mathsf{n}-1)$-private QSPIR protocol of rate $\lceil \mathsf{n}/2{\rceil }^{-1}$ and prove that the capacity is upper bounded by $2/\mathsf{n}$ even if any error probability is allowed. The $(\mathsf{n}-1)$-private QSPIR capacity is strictly greater than the classical counterpart.

References in corpus (2)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Superdense coding over optical fiber links with complete Bell-state measurements

Cited by in corpus (5)

• Unified Approach to Secret Sharing and Symmetric Private Information Retrieval with Colluding Servers in Quantum Systems
• The Capacity of Classical Summation over a Quantum MAC with Arbitrarily Distributed Inputs and Entanglements
• On the Capacity of Secure $K$-user Product Computation over a Quantum MAC
• Prior Entanglement Exponentially Improves One-Server Quantum Private Information Retrieval for Quantum Messages
• Two-Server Oblivious Transfer for Quantum Messages