Private Information Retrieval from Coded Databases with Colluding Servers

Ragnar Freij-Hollanti; Oliver Gnilke; Camilla Hollanti; David Karpuk

doi:10.1137/16M1102562

Private Information Retrieval from Coded Databases with Colluding Servers

Ragnar Freij-Hollanti, Oliver Gnilke, Camilla Hollanti, David Karpuk

Research output: Contribution to journal › Article › Scientific › peer-review

161 Citations (Scopus)

252 Downloads (Pure)

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.

Original language	English
Pages (from-to)	647–664
Number of pages	18
Journal	SIAM Journal on Applied Algebra and Geometry
Volume	1
Issue number	1
DOIs	https://doi.org/10.1137/16M1102562
Publication status	Published - 2017
MoE publication type	A1 Journal article-refereed

Keywords

private information retrieval
distributed storage systems
generalized Reed--Solomon codes

Access to Document

10.1137/16M1102562

16m1102562Final published version, 279 KB

Cite this

@article{488bedd1654f491ab696b5a8e87aab18,

title = "Private Information Retrieval from Coded Databases with Colluding Servers",

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.",

keywords = "private information retrieval, distributed storage systems, generalized Reed--Solomon codes",

author = "Ragnar Freij-Hollanti and Oliver Gnilke and Camilla Hollanti and David Karpuk",

year = "2017",

doi = "10.1137/16M1102562",

language = "English",

volume = "1",

pages = "647–664",

journal = "SIAM Journal on Applied Algebra and Geometry",

issn = "2470-6566",

publisher = "Society for Industrial and Applied Mathematics",

number = "1",

}

TY - JOUR

T1 - Private Information Retrieval from Coded Databases with Colluding Servers

AU - Freij-Hollanti, Ragnar

AU - Gnilke, Oliver

AU - Hollanti, Camilla

AU - Karpuk, David

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - private information retrieval

KW - distributed storage systems

KW - generalized Reed--Solomon codes

U2 - 10.1137/16M1102562

DO - 10.1137/16M1102562

M3 - Article

SN - 2470-6566

VL - 1

SP - 647

EP - 664

JO - SIAM Journal on Applied Algebra and Geometry

JF - SIAM Journal on Applied Algebra and Geometry

IS - 1

ER -

Private Information Retrieval from Coded Databases with Colluding Servers

Abstract

Keywords

Access to Document

Fingerprint

Cite this