The Capacity of Private Computation

DOI10.1109/TIT.2018.2888494zbMATH Open1432.94156arXiv1710.11098OpenAlexW2906543194WikidataQ128737197 ScholiaQ128737197MaRDI QIDQ5224040FDOQ5224040

Authors: Hua Sun, Syed A. Jafar 

Publication date: 19 July 2019

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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. Surprisingly, the capacity, $C=left(1+1/N+cdots+1/N^{K-1}ight{)}^{-1}$, matches the capacity of PIR with $N$ servers and $K$ messages. Thus, allowing arbitrary linear computations does not reduce the communication rate compared to pure dataset retrieval. The same insight is shown to hold even for arbitrary non-linear computations when the number of datasets $Kightarrowinfty$.

Full work available at URL: https://arxiv.org/abs/1710.11098

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Authentication, digital signatures and secret sharing (94A62) Privacy of data (68P27)

Cited In (2)

• Private computation using a PEZ dispenser.
• Private Computations over the Integers

This page was built for publication: The Capacity of Private Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224040)