1. On the Capacity of Private Nonlinear Computation for Replicated Databases
- Author
-
Eirik Rosnes, Jorg Kliewer, Sarah A. Obead, and Hsuan-Yin Lin
- Subjects
FOS: Computer and information sciences ,Monomial ,Database ,Computer science ,Computation ,Computer Science - Information Theory ,Information Theory (cs.IT) ,020206 networking & telecommunications ,02 engineering and technology ,Function (mathematics) ,computer.software_genre ,Nonlinear system ,020204 information systems ,Distributed data store ,0202 electrical engineering, electronic engineering, information engineering ,Special case ,Message size ,computer ,Finite set - Abstract
We consider the problem of private computation (PC) in a distributed storage system. In such a setting a user wishes to compute a function of $f$ messages replicated across $n$ noncolluding databases, while revealing no information about the desired function to the databases. We provide an information-theoretically accurate achievable PC rate, which is the ratio of the smallest desired amount of information and the total amount of downloaded information, for the scenario of nonlinear computation. For a large message size the rate equals the PC capacity, i.e., the maximum achievable PC rate, when the candidate functions are the $f$ independent messages and one arbitrary nonlinear function of these. When the number of messages grows, the PC rate approaches an outer bound on the PC capacity. As a special case, we consider private monomial computation (PMC) and numerically compare the achievable PMC rate to the outer bound for a finite number of messages., Comment: 5 pages, 1 figure, 1 table. Presented at the 2019 IEEE Information Theory Workshop (ITW). Figure 1 is updated as it contained incorrect data-points for $f=2$ and $g=3$. arXiv admin note: text overlap with arXiv:2003.10007
- Published
- 2023
- Full Text
- View/download PDF