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

IEEE Transactions on Information Theory

Capacity of Quantum Private Information Retrieval With Colluding Servers

Seunghoan Song, Masahito Hayashi

Published May 4, 2021• 28 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2021.3077269

Related papers

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 $\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

Capacity of Quantum Symmetric Private Information Retrieval With Collusion of All But One of Servers

Seunghoan Song, Masahito Hayashi

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 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 article, we consider the (n-1)-private QSPIR in which the identity of the retrieved file is secret even if any 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 any even number n of servers, we show that the capacity of the (n-1)-private QSPIR is 2/n, when we assume that there are prior entanglements among the servers. We construct an (n-1)-private QSPIR protocol of rate ⌈n/2⌉-1and prove that the capacity is upper bounded by 2/n even if any error probability is allowed. The (n-1)-private QSPIR capacity is strictly greater than the classical counterpart.

arXiv:1903.12556•IEEE Journal on Selected Areas in Information Theory•Jan 26, 2021•19 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.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•10 citations

Capacity of Quantum Private Information Retrieval With Multiple Servers

Seunghoan Song, Masahito Hayashi

We study the capacity of quantum private information retrieval (QPIR) with multiple servers. In the QPIR problem with multiple servers, a user retrieves a classical file by downloading quantum systems from multiple servers each of which contains the copy of a classical file set while the identity of the downloaded file is not leaked to each server. The QPIR capacity is defined as the maximum rate of the file size over the whole dimension of the downloaded quantum systems. When the servers are assumed to share prior entanglement, we prove that the QPIR capacity with multiple servers is 1 regardless of the number of servers and files. We construct a rate-one protocol only with two servers. This capacity-achieving protocol outperforms its classical counterpart in the sense of the capacity, server secrecy, and upload cost. The strong converse bound is derived concisely without using any secrecy condition. We also prove that the capacity of multi-round QPIR is 1.

arXiv:1903.10209•IEEE Transactions on Information Theory•Sep 7, 2020•35 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.

•Jun 28, 2021•0 citations
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 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\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.
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 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 article, we consider the (n-1)-private QSPIR in which the identity of the retrieved file is secret even if any 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 any even number n of servers, we show that the capacity of the (n-1)-private QSPIR is 2/n, when we assume that there are prior entanglements among the servers. We construct an (n-1)-private QSPIR protocol of rate ⌈n/2⌉-1and prove that the capacity is upper bounded by 2/n even if any error probability is allowed. The (n-1)-private QSPIR capacity is strictly greater than the classical counterpart.
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.
We study the capacity of quantum private information retrieval (QPIR) with multiple servers. In the QPIR problem with multiple servers, a user retrieves a classical file by downloading quantum systems from multiple servers each of which contains the copy of a classical file set while the identity of the downloaded file is not leaked to each server. The QPIR capacity is defined as the maximum rate of the file size over the whole dimension of the downloaded quantum systems. When the servers are assumed to share prior entanglement, we prove that the QPIR capacity with multiple servers is 1 regardless of the number of servers and files. We construct a rate-one protocol only with two servers. This capacity-achieving protocol outperforms its classical counterpart in the sense of the capacity, server secrecy, and upload cost. The strong converse bound is derived concisely without using any secrecy condition. We also prove that the capacity of multi-round QPIR is 1.
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.