TY - GEN

T1 - On the Capacity of Private Nonlinear Computation for Replicated Databases

AU - Obead, Sarah A.

AU - Lin, Hsuan Yin

AU - Rosnes, Eirik

AU - Kliewer, Jorg

N1 - Funding Information:
This work is supported by US NSF grant CNS-1526547.

PY - 2019/8

Y1 - 2019/8

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/ITW44776.2019.8989267

DO - 10.1109/ITW44776.2019.8989267

M3 - Conference contribution

AN - SCOPUS:85081109977

T3 - 2019 IEEE Information Theory Workshop, ITW 2019

BT - 2019 IEEE Information Theory Workshop, ITW 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE Information Theory Workshop, ITW 2019

Y2 - 25 August 2019 through 28 August 2019

ER -