Projects per year
Abstract
In this work, two practical concepts related to private information retrieval (PIR) are introduced and coined full support-rank PIR and strongly linear PIR. Being of full support-rank is a technical, yet natural condition required to prove a converse result for a capacity expression and satisfied by almost all currently known capacity-achieving schemes, while strong linearity is a practical requirement enabling implementation over small finite fields with low subpacketization degree. Then, the capacity of MDS-coded, linear, full support-rank PIR in the presence of colluding servers is derived, as well as the capacity of symmetric, linear PIR with colluding, adversarial, and nonresponsive servers for the recently introduced concept of matched randomness. This positively settles the capacity conjectures stated by Freij-Hollanti et al. and Tajeddine et al. in the presented cases. It is also shown that, further restricting to strongly-linear PIR schemes with deterministic linear interference cancellation, the so-called star product scheme proposed by Freij-Hollanti et al. is essentially optimal and induces no capacity loss.
Original language | English |
---|---|
Pages (from-to) | 517-537 |
Number of pages | 21 |
Journal | IEEE Transactions on Information Theory |
Volume | 68 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2022 |
MoE publication type | A1 Journal article-refereed |
Keywords
- capacity
- information theoretic privacy
- Private information retrieval (PIR)
- symmetric
Fingerprint
Dive into the research topics of 'Toward the Capacity of Private Information Retrieval from Coded and Colluding Servers'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Hollanti_ICT: Secure Distributed Computation Schemes with Applications to Digitalized Remote Healthcare
Hollanti, C. (Principal investigator), Villamizar Rubiano, D. (Project Member), Hieta-aho, E. (Project Member), Sacikara Kariksiz, E. (Project Member), Yatsyna, P. (Project Member), Kas Hanna, S. (Project Member), Makkonen, O. (Project Member), Matala-aho, T. (Project Member), Karpuk, D. (Project Member), Bolanos Chavez, W. (Project Member) & Allaix, M. (Project Member)
01/01/2021 → 31/12/2023
Project: Academy of Finland: Other research funding