Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers

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

doi:10.1109/TIT.2018.2890285

Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers

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

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

56 Citations (Scopus)

224 Downloads (Pure)

Abstract

The problem of private information retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an [n,k] Reed-Solomon storage code is designed, protecting against t-collusion, and handling up to b Byzantine and r unresponsive servers, when n>k+t+2b+r-1. This scheme achieves a PIR rate of ((n-r-(k+2b+t-1))/n-r). In the case where the capacity is known, namely, when k=1, it is asymptotically capacity achieving as the number of files grows. Finally, the scheme is adapted to symmetric PIR.

Original language	English
Article number	8598994
Pages (from-to)	3898-3906
Number of pages	9
Journal	IEEE Transactions on Information Theory
Volume	65
Issue number	6
Early online date	2019
DOIs	https://doi.org/10.1109/TIT.2018.2890285
Publication status	Published - 1 Jun 2019
MoE publication type	A1 Journal article-refereed

Keywords

Byzantine
information retrieval
Privacy
Reed-Solomon codes
reliability
robustness
servers

Access to Document

10.1109/TIT.2018.2890285

SCI_Tajeddine_et_al_Private_Information_Byzantine_Journal_paper_Final_teo_colsAccepted author manuscript, 247 KB

Cite this

@article{dc09391ef0864838b4b56f2286d18b78,

title = "Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers",

abstract = "The problem of private information retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an [n,k] Reed-Solomon storage code is designed, protecting against t-collusion, and handling up to b Byzantine and r unresponsive servers, when n>k+t+2b+r-1. This scheme achieves a PIR rate of ((n-r-(k+2b+t-1))/n-r). In the case where the capacity is known, namely, when k=1, it is asymptotically capacity achieving as the number of files grows. Finally, the scheme is adapted to symmetric PIR.",

keywords = "Byzantine, information retrieval, Privacy, Reed-Solomon codes, reliability, robustness, servers",

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

year = "2019",

month = jun,

day = "1",

doi = "10.1109/TIT.2018.2890285",

language = "English",

volume = "65",

pages = "3898--3906",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "IEEE",

number = "6",

}

TY - JOUR

T1 - Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers

AU - Tajeddine, Razane

AU - Gnilke, Oliver

AU - Karpuk, David

AU - Freij-Hollanti, Ragnar

AU - Hollanti, Camilla

PY - 2019/6/1

Y1 - 2019/6/1

N2 - The problem of private information retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an [n,k] Reed-Solomon storage code is designed, protecting against t-collusion, and handling up to b Byzantine and r unresponsive servers, when n>k+t+2b+r-1. This scheme achieves a PIR rate of ((n-r-(k+2b+t-1))/n-r). In the case where the capacity is known, namely, when k=1, it is asymptotically capacity achieving as the number of files grows. Finally, the scheme is adapted to symmetric PIR.

AB - The problem of private information retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an [n,k] Reed-Solomon storage code is designed, protecting against t-collusion, and handling up to b Byzantine and r unresponsive servers, when n>k+t+2b+r-1. This scheme achieves a PIR rate of ((n-r-(k+2b+t-1))/n-r). In the case where the capacity is known, namely, when k=1, it is asymptotically capacity achieving as the number of files grows. Finally, the scheme is adapted to symmetric PIR.

KW - Byzantine

KW - information retrieval

KW - Privacy

KW - Reed-Solomon codes

KW - reliability

KW - robustness

KW - servers

UR - http://www.scopus.com/inward/record.url?scp=85065976996&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2890285

DO - 10.1109/TIT.2018.2890285

M3 - Article

SN - 0018-9448

VL - 65

SP - 3898

EP - 3906

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 6

M1 - 8598994

ER -

Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Number-theoretic and combinatorial tools for private and secure cloud services

Applied Algebra and Number Theory in Robust and Secure Wireless Cloud Storage Systems

Applied algebra in communications technology

Cite this

Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Number-theoretic and combinatorial tools for private and secure cloud services

Applied Algebra and Number Theory in Robust and Secure Wireless Cloud Storage Systems

Applied algebra in communications technology

Cite this