In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both with and without collusion. QPIR over [n, k] maximum distance separable (MDS) coded servers was recently considered by Allaix et al., but the collusion was essentially restricted to t = n - $k$ servers in the sense that a smaller $t$ would not improve the retrieval rate. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers $t$ with 1 ≤ $t$ ≤ $n$ - k. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts, as well as those of the previously proposed coded and colluding QPIR schemes. This is enabled by considering the stabilizer formalism and weakly self-dual generalized Reed-Solomon (GRS) star product codes.In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both with and without collusion. QPIR over [n, k] maximum distance separable (MDS) coded servers was recently considered by Allaix et al., but the collusion was essentially restricted to t = n -$k$servers in the sense that a smaller$t$would not improve the retrieval rate. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers$t$with 1 ≤$t$≤$n$- k. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts, as well as those of the previously proposed coded and colluding QPIR schemes. This is enabled by considering the stabilizer formalism and weakly self-dual generalized Reed-Solomon (GRS) star product codes.

arXiv:2102.02511IEEE International Symposium on Information Theory (ISIT)Jul 12, 20217 citations

Quantum Private Information Retrieval from Coded Storage Systems

Matteo Allaix

In the era of extensive data growth, robust and efficient mechanisms are needed to store and manage vast amounts of digital information, such as Data Storage Systems (DSSs). Concurrently, privacy concerns have arisen, leading to the development of techniques like Private Information Retrieval (PIR) to enable data access while preserving privacy. A PIR protocol allows users to retrieve information from a database without revealing the specifics of their query or the data they are accessing. With the advent of quantum computing, researchers have explored the potential of using quantum systems to enhance privacy in information retrieval. In a Quantum Private Information Retrieval (QPIR) protocol, a user can retrieve information from a database by downloading quantum systems from multiple servers, while ensuring that the servers remain oblivious to the specific information being accessed. This scenario offers a unique advantage by leveraging the inherent properties of quantum systems to provide enhanced privacy guarantees and improved communication rates compared to classical PIR protocols. In this thesis we consider the QPIR setting where the queries and the coded storage systems are classical, while the responses from the servers are quantum. This problem was treated by Song et al. for replicated storage and different collusion patterns. This thesis aims to develop QPIR protocols for coded storage by combining known classical PIR protocols with quantum communication algorithms, achieving enhanced privacy and communication costs. We consider different storage codes and robustness assumptions, and we prove that the achieved communication cost is always lower than the classical counterparts.In the era of extensive data growth, robust and efficient mechanisms are needed to store and manage vast amounts of digital information, such as Data Storage Systems (DSSs). Concurrently, privacy concerns have arisen, leading to the development of techniques like Private Information Retrieval (PIR) to enable data access while preserving privacy. A PIR protocol allows users to retrieve information from a database without revealing the specifics of their query or the data they are accessing. With the advent of quantum computing, researchers have explored the potential of using quantum systems to enhance privacy in information retrieval. In a Quantum Private Information Retrieval (QPIR) protocol, a user can retrieve information from a database by downloading quantum systems from multiple servers, while ensuring that the servers remain oblivious to the specific information being accessed. This scenario offers a unique advantage by leveraging the inherent properties of quantum systems to provide enhanced privacy guarantees and improved communication rates compared to classical PIR protocols. In this thesis we consider the QPIR setting where the queries and the coded storage systems are classical, while the responses from the servers are quantum. This problem was treated by Song et al. for replicated storage and different collusion patterns. This thesis aims to develop QPIR protocols for coded storage by combining known classical PIR protocols with quantum communication algorithms, achieving enhanced privacy and communication costs. We consider different storage codes and robustness assumptions, and we prove that the achieved communication cost is always lower than the classical counterparts.

arXiv:2312.07570Dec 10, 20230 citations

On the Capacity of Quantum Private Information Retrieval From MDS-Coded and Colluding Servers

Matteo Allaix, Seunghoan Song, Lukas Holzbaur +3 more

In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied for the first time. Two general classes of QPIR, called stabilizer QPIR and dimension-squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension-squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollantiet al.and the stabilizer QPIR scheme by Songet al.by employing (weakly) self-dual Reed–Solomon codes.In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied for the first time. Two general classes of QPIR, called stabilizer QPIR and dimension-squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension-squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollantiet al.and the stabilizer QPIR scheme by Songet al.by employing (weakly) self-dual Reed–Solomon codes.

arXiv:2106.14719IEEE Journal on Selected Areas in CommunicationsJan 26, 202220 citations

On the Capacity of Quantum Private Information Retrieval from MDS-Coded and Colluding Servers.zip

Matteo Allaix, Seunghoan Song, Lukas Holzbaur +3 more

In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied. Two classes of QPIR, called stabilizer QPIR and dimension squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. The capacities of symmetric and non-symmetric QPIR with coded and colluding servers are proved to coincide, being double to their classical counterparts. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollanti et al. and the stabilizer QPIR scheme by Song et al. by employing (weakly) self-dual Reed--Solomon codes.In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied. Two classes of QPIR, called stabilizer QPIR and dimension squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. The capacities of symmetric and non-symmetric QPIR with coded and colluding servers are proved to coincide, being double to their classical counterparts. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollanti et al. and the stabilizer QPIR scheme by Song et al. by employing (weakly) self-dual Reed--Solomon codes.

Jun 28, 20210 citations

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

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is the problem to retrieve one of f classical files by downloading quantum systems from non-communicating n servers each of which contains the copy of f files, while the identity of the retrieved file is unknown to each server. As an extension, we consider the (n-1)-private QPIR that the identity of the retrieved file is secret even if any n-1 servers collude, and derive the QPIR capacity for this problem which is defined as the maximum rate of the retrieved file size over the download size. For an even number n of servers, we show that the capacity of the (n-1)-private QPIR is 2/n, when we assume that there are preexisting entanglements among the servers and require that no information of the nonretrieved files is downloaded. We construct an (n - 1)-private QPIR protocol of rate Γn/21-1and prove that the capacity is upper bounded by 2/n. The (n - 1)-private QPIR capacity is strictly greater than the classical counterpart. The full version of this paper is accessible at: https://arxiv.org/pdf/1903.12556.Quantum private information retrieval (QPIR) is the problem to retrieve one of f classical files by downloading quantum systems from non-communicating n servers each of which contains the copy of f files, while the identity of the retrieved file is unknown to each server. As an extension, we consider the (n-1)-private QPIR that the identity of the retrieved file is secret even if any n-1 servers collude, and derive the QPIR capacity for this problem which is defined as the maximum rate of the retrieved file size over the download size. For an even number n of servers, we show that the capacity of the (n-1)-private QPIR is 2/n, when we assume that there are preexisting entanglements among the servers and require that no information of the nonretrieved files is downloaded. We construct an (n - 1)-private QPIR protocol of rate Γn/21-1and prove that the capacity is upper bounded by 2/n. The (n - 1)-private QPIR capacity is strictly greater than the classical counterpart. The full version of this paper is accessible at: https://arxiv.org/pdf/1903.12556.

IEEE Information Theory Workshop (ITW)Aug 1, 201910 citations

k

servers in the sense that a smaller

t

would not improve the retrieval rate. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers

t

with 1 ≤

t

≤

n

- k. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts, as well as those of the previously proposed coded and colluding QPIR schemes. This is enabled by considering the stabilizer formalism and weakly self-dual generalized Reed-Solomon (GRS) star product codes.