Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2106.14719 · IEEE Journal on Selected Areas in Communications

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

Matteo Allaix, Seunghoan Song, Lukas Holzbaur, Tefjol Pllaha, Masahito Hayashi, Camilla Hollanti

Published Jan 26, 2022• 20 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/jsac.2022.3142363

Related papers

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.

•Jun 28, 2021•0 citations

High-Rate Quantum Private Information Retrieval with Weakly Self-Dual Star Product Codes

Matteo Allaix, Lukas Holzbaur, Tefjol Pllaha +1 more

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.02511•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•7 citations

Quantum Private Information Retrieval from MDS-coded and Colluding Servers

Matteo Allaix, Lukas Holzbaur, Tefjol Pllaha +1 more

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 downloading quantum systems from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any [n, k]-MDS code and t-collusion with t = n - k. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•2 citations

Capacity of Quantum Private Information Retrieval with Colluding Servers

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is a protocol that a user retrieves one of f files from non-communicating n servers by downloading quantum systems without revealing the identity of the target file. As variants of the QPIR with stronger security requirements, the symmetric QPIR is that the files except for the target file are not leaked to the user, and the t-private QPIR is that the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the one file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min {1, 2(n - t)/n} for any 1 ≤ t <; n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•7 citations

Capacity of Quantum Private Information Retrieval With Colluding Servers

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from n non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and t-private QPIR is a protocol in which the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min{1,2( n- t)/ n} for any 1 ≤ t <; n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.

IEEE Transactions on Information Theory•May 4, 2021•28 citations

Capacity of Quantum Private Information Retrieval with Colluding Servers

Seunghoan Song, Masahito Hayashi

Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from $\mathsf{n}$ non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and $\mathsf{t}$-private QPIR is a protocol in which the identity of the target file is kept secret even if at most $\mathsf{t}$ servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric $\mathsf{t}$-private QPIR capacity is $\min\{1,2(\mathsf{n}-\mathsf{t})/\mathsf{n}\}$ for any $1\leq \mathsf{t}< \mathsf{n}$. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.

arXiv:2001.04436•Jan 13, 2020•0 citations
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. 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 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 -kkkservers in the sense that a smallertttwould 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 serverstttwith 1 ≤ttt≤nnn- 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 downloading quantum systems from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any [n, k]-MDS code and t-collusion with t = n - k. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts.
Quantum private information retrieval (QPIR) is a protocol that a user retrieves one of f files from non-communicating n servers by downloading quantum systems without revealing the identity of the target file. As variants of the QPIR with stronger security requirements, the symmetric QPIR is that the files except for the target file are not leaked to the user, and the t-private QPIR is that the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the one file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min {1, 2(n - t)/n} for any 1 ≤ t <; n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.
Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from n non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and t-private QPIR is a protocol in which the identity of the target file is kept secret even if at most t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric t-private QPIR capacity is min{1,2( n- t)/ n} for any 1 ≤ t <; n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.
Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from n\mathsf{n}n non-communicating servers by downloading quantum systems without revealing which file is retrieved. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user, and t\mathsf{t}t-private QPIR is a protocol in which the identity of the target file is kept secret even if at most t\mathsf{t}t servers may collude to reveal the identity. The QPIR capacity is the maximum ratio of the file size to the size of downloaded quantum systems, and we prove that the symmetric t\mathsf{t}t-private QPIR capacity is min⁡{1,2(n−t)/n}\min\{1,2(\mathsf{n}-\mathsf{t})/\mathsf{n}\}min{1,2(n−t)/n} for any 1≤t<n1\leq \mathsf{t}< \mathsf{n}1≤t<n. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol. The proposed capacity is greater than the classical counterpart.