Fetching the paper…

Reading the bibliography…

2017

The Capacity of Private Computation

Sun, Hua, Jafar, Syed A.

Original
PDF
Post on X

Understand

We introduce the problem of private computation, comprised of $N$ distributed and non-colluding servers, $K$ independent datasets, and a user who wants to compute a function of the datasets privately, i.e., without revealing which function he wants to compute, to any individual server.

This private computation problem is a strict generalization of the private information retrieval (PIR) problem, obtained by expanding the PIR message set (which consists of only independent messages) to also include functions of those messages.
The capacity of private computation, $C$, is defined as the maximum number of bits of the desired function that can be retrieved per bit of total download from all servers.
We characterize the capacity of private computation, for $N$ servers and $K$ independent datasets that are replicated at each server, when the functions to be computed are arbitrary linear combinations of the datasets.

The Capacity of Private Computation · Around

Built on

B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private Information Retrieval,” Journal of the ACM (JACM) , vol. 45, no. 6, pp. 965–981, 1998
1998
Earlier work this paper cites.
N. Shah, K. Rashmi, and K. Ramchandran, “One Extra Bit of Download Ensures Perfectly Private Information Retrieval,” in Proceedings of IEEE International Symposium on Information Theory (ISIT) , 2014, pp. 856–860
2014
Earlier work this paper cites.
——, “The Capacity of Robust Private Information Retrieval with Colluding Databases,” arXiv preprint arXiv:1605.00635 , 2016
Original
2016
Earlier work this paper cites.
——, “The Capacity of Symmetric Private Information Retrieval,” arXiv preprint arXiv:1606.08828 , 2016
Original
2016
Earlier work this paper cites.

Similar

K. Banawan and S. Ulukus, “The Capacity of Private Information Retrieval from Coded Databases,” arXiv preprint arXiv:1609.08138 , 2016
Original
2016
Cited alongside, same era.
H. Sun and S. A. Jafar, “Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length,” arXiv preprint arXiv:1610.03048 , 2016
Original
2016
Cited alongside, same era.
H. Sun and S. A. Jafar, “The Capacity of Private Information Retrieval,” IEEE Transactions on Information Theory , vol. 63, no. 7, pp. 4075–4088, 2017
2017
Cited alongside, same era.
Q. Wang and M. Skoglund, “Symmetric private information retrieval for mds coded distributed storage,” in Communications (ICC), 2017 IEEE International Conference on . IEEE, 2017, pp. 1–6
2017
Cited alongside, same era.

Then

K. Banawan and S. Ulukus, “The capacity of private information retrieval from byzantine and colluding databases,” arXiv preprint arXiv:1706.01442 , 2017
Original
2017
Closest in time.
R. Tandon, “The capacity of cache aided private information retrieval,” arXiv preprint arXiv:1706.07035 , 2017
Original
2017
Closest in time.
M. Mirmohseni and M. A. Maddah-Ali, “Private function retrieval,” arXiv preprint arXiv:1711.04677 , 2017
Original
2017
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…