The Asymptotic Capacity of Private Information Retrieval With Secure Storage Under Disjoint Colluding Sets
IEEE Transactions on Information Theory · 2026-08 · 72 (8) · 6123-6139
DOI: 10.1109/tit.2026.3700044 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-08. Verfasst von Haobo Jia und 1 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben. Gefördert von: National Key Research and Development Program of China, National Science Foundation of China.
Abstract (Originalsprache)
In this paper, we consider the problem of private information retrieval with secure storage (SS-PIR) under a setting with disjoint colluding sets, where the user wishes to privately retrieve one out of $K$ independent messages that are securely stored across $N$ servers. The $N$ servers are partitioned into $M$ disjoint colluding sets, i.e., within the $m$ -th group, $m\in [M]$ , any set of up to $T_{m}$ colluding servers cannot learn any information about the index of the desired message, and any set of up to $X_{m}$ colluding servers cannot learn any information about the $K$ messages. The asymptotic capacity is defined as the maximum possible number of $q$ -ary symbols of the desired message that can be retrieved per $q$ -ary downloaded symbol, in the limit as the number of messages $K\rightarrow \infty $ . We demonstrate that the asymptotic capacity of SS-PIR with disjoint colluding sets is the solution to a linear program parameterized by the server partition, privacy thresholds $T_{m}$ , and security thresholds $X_{m}$ . Our achievability scheme introduces a novel pre-decoding strategy built upon cross-subspace alignment (CSA) codes. In this strategy, instead of requiring the user to decode the message from all of the original CSA coded answer symbols, our approach allows certain servers to perform a local pre-decoding and return intermediate results that turn out to be more communication-efficient. This mechanism is the key to minimizing the download cost, allowing our scheme to match the information-theoretic converse and thereby establish the asymptotic capacity of SS-PIR with disjoint colluding sets.
Förderung
- National Key Research and Development Program of China
- National Science Foundation of China
Zitieren
APA
Jia, H., & Jia, Z. (2026). The Asymptotic Capacity of Private Information Retrieval With Secure Storage Under Disjoint Colluding Sets. IEEE Transactions on Information Theory, 72(8), 6123-6139. https://doi.org/10.1109/tit.2026.3700044
Vancouver
Jia H, Jia Z. The Asymptotic Capacity of Private Information Retrieval With Secure Storage Under Disjoint Colluding Sets. IEEE Transactions on Information Theory. 2026;72(8):6123-6139. doi:10.1109/tit.2026.3700044
BibTeX
@article{Jia2026,
author = {Jia, Haobo and Jia, Zhuqing},
title = {The Asymptotic Capacity of Private Information Retrieval With Secure Storage Under Disjoint Colluding Sets},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {8},
pages = {6123--6139},
doi = {10.1109/tit.2026.3700044}
}
EUVIMED