Fetching the paper…

Reading the bibliography…

2016

The Capacity of Private Information Retrieval from Coded Databases

Banawan, Karim, Ulukus, Sennur

Original
PDF
Post on X

Understand

We consider the problem of private information retrieval (PIR) over a distributed storage system.

The storage system consists of $N$ non-colluding databases, each storing a coded version of $M$ messages.
In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database.
We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information.

The Capacity of Private Information Retrieval from Coded Databases · Around

Built on

Private information retrieval
B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan · 1998
Earlier work this paper cites.
A survey on private information retrieval
W. Gasarch · 2004
Earlier work this paper cites.
A survey of single-database private information retrieval: Techniques and applications
R. Ostrovsky and W. Skeith III · 2007
Earlier work this paper cites.
Private information retrieval
S. Yekhanin · 2010
Earlier work this paper cites.
A survey on network codes for distributed storage
A. Dimakis, K. Ramchandran, Y. Wu, and C. Suh · 2011
Earlier work this paper cites.

Similar

Blind interference alignment
S. Jafar · 2012
Cited alongside, same era.
One extra bit of download ensures perfectly private information retrieval
N. B. Shah, K. V. Rashmi, and K. Ramchandran · 2014
Cited alongside, same era.
Private information retrieval for coded storage
T. Chan, S. Ho, and H. Yamamoto · 2015
Cited alongside, same era.
PIR with low storage overhead: coding instead of replication
Original
A. Fazeli, A. Vardy, and E. Yaakobi · 2015
Cited alongside, same era.
Private information retrieval from MDS coded data in distributed storage systems
R. Tajeddine and S. El Rouayheb · 2016
Cited alongside, same era.

Then

The capacity of private information retrieval
Original
H. Sun and S. Jafar · 2016
Closest in time.
Blind interference alignment for private information retrieval
Original
H. Sun and S. Jafar · 2016
Closest in time.
The capacity of robust private information retrieval with colluding databases
Original
H. Sun and S. Jafar · 2016
Closest in time.
The capacity of symmetric private information retrieval
Original
H. Sun and S. Jafar · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…