Private Information Retrieval from Coded Databases with Colluding Servers

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Date
2017
Major/Subject
Mcode
Degree programme
Language
en
Pages
18
647–664
Series
SIAM Journal on Applied Algebra and Geometry, Volume 1, issue 1
Abstract
We present a general framework for private information retrieval (PIR) from arbitrary coded databases that allows one to adjust the rate of the scheme to the suspected number of colluding servers. If the storage code is a generalized Reed--Solomon code of length $n$ and dimension $k$, we design PIR schemes that achieve a PIR rate of $\frac{n-(k+t-1)}{n}$ while protecting against any $t$ colluding servers, for any $1\leq t\leq n-k$. This interpolates between the previously studied cases of $t=1$ and $k=1$ and achieves PIR capacity in both of these cases asymptotically as the number of files in the database grows.
Description
Keywords
private information retrieval, distributed storage systems, generalized Reed--Solomon codes
Other note
Citation
Freij-Hollanti , R , Gnilke , O , Hollanti , C & Karpuk , D 2017 , ' Private Information Retrieval from Coded Databases with Colluding Servers ' , SIAM Journal on Applied Algebra and Geometry , vol. 1 , no. 1 , pp. 647–664 . https://doi.org/10.1137/16M1102562