Quantum method improves private data retrieval on forest graphs
Quantum Private Information Retrieval on Forests
Information TheoryCryptography and SecurityNetworking and Internet Architecture
Summary
The paper looks at how to privately retrieve information from servers connected in a simple network structure called a forest, using quantum technology. The authors design a quantum method that improves the efficiency of retrieving data without revealing what was asked for. They use a special quantum state called the GHZ state shared among servers to achieve this. They also find the maximum possible efficiency for a small special case of such networks and provide a matching method to reach it.
What this means in practice
- •For quantum network engineers: Use the scheme to design efficient quantum protocols that allow private retrieval of data on networks structured as forests.
- •For quantum communication architects: Incorporate the quantum capacity results to optimize data retrieval rates while maintaining privacy in quantum distributed systems with simple topology.
Authors
Mohamed Nomeir, Sennur Ulukus
Abstract
We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of $\frac{3}{N}$. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of $G=3K_2$, which is equal to $4/6$. $G=3K_2$ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to $4/6$ and provide the corresponding matching upper bound, establishing it as the capacity.