Technical Program

Paper Detail

Paper IDP.11.3
Paper Title Private Computation with Individual and Joint Privacy
Authors Anoosheh Heidarzadeh, Alex Sprintson, Texas A&M University, United States
Session P.11: Topics in Privacy and Cryptography
Presentation Lecture
Track Cryptography, Security and Privacy
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract This paper considers the problem of single-server Private Computation (PC) in the presence of Side Information (SI). In this problem, there is a server that stores $K$ i.i.d. messages, and a user who has a subset of $M$ uncoded messages or a coded linear combination of them as side information, where the identities of these messages are unknown to the server. The user wants to privately compute a linear combination of a subset of $D$ other messages by downloading information from the server, where the identities of these messages must be kept private individually or jointly. For each setting, we define the capacity as the supremum of all achievable download rates. We characterize the capacity of both PC with coded and uncoded SI when individual privacy is required, for all $K,M,D$. Our results indicate that both settings have the same capacity. In addition, we establish a non-trivial lower bound on the capacity of PC with coded SI when joint privacy is required, for a range of parameters $K,M,D$. This lower bound is the same as the lower bound we previously established on the capacity of PC with uncoded SI when joint privacy is required.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!