Single-Server Private Linear Transformation: The Individual Privacy Case

  • 2021-06-09 17:12:04
  • Anoosheh Heidarzadeh, Nahid Esmati, Alex Sprintson
  • 1

Abstract

This paper considers the single-server Private Linear Transformation (PLT)problem with individual privacy guarantees. In this problem, there is a userthat wishes to obtain $L$ independent linear combinations of a $D$-subset ofmessages belonging to a dataset of $K$ messages stored on a single server. Thegoal is to minimize the download cost while keeping the identity of eachmessage required for the computation individually private. The individualprivacy requirement ensures that the identity of each individual messagerequired for the computation is kept private. This is in contrast to thestricter notion of joint privacy that protects the entire set of identities ofall messages used for the computation, including the correlations between theseidentities. The notion of individual privacy captures a broad set of practicalapplications. For example, such notion is relevant when the dataset containsinformation about individuals, each of them requires privacy guarantees fortheir data access patterns. We focus on the setting in which the requiredlinear transformation is associated with a maximum distance separable (MDS)matrix. In particular, we require that the matrix of coefficients pertaining tothe required linear combinations is the generator matrix of an MDS code. Weestablish lower and upper bounds on the capacity of PLT with individualprivacy, where the capacity is defined as the supremum of all achievabledownload rates. We show that our bounds are tight under certain conditions.

 

Quick Read (beta)

loading the full paper ...