Single-Server Private Linear Transformation: The Joint Privacy Case

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

Abstract

This paper introduces the problem of Private Linear Transformation (PLT)which generalizes the problems of private information retrieval and privatelinear computation. The PLT problem includes one or more remote server(s)storing (identical copies of) $K$ messages and a user who wants to compute $L$independent linear combinations of a $D$-subset of messages. The objective ofthe user is to perform the computation by downloading minimum possible amountof information from the server(s), while protecting the identities of the $D$messages required for the computation. In this work, we focus on thesingle-server setting of the PLT problem when the identities of the $D$messages required for the computation must be protected jointly. We considertwo different models, depending on whether the coefficient matrix of therequired $L$ linear combinations generates a Maximum Distance Separable (MDS)code. We prove that the capacity for both models is given by $L/(K-D+L)$, wherethe capacity is defined as the supremum of all achievable download rates. Ourconverse proofs are based on linear-algebraic and information-theoreticarguments that establish connections between PLT schemes and linear codes. Wealso present an achievability scheme for each of the models being considered.

 

Quick Read (beta)

loading the full paper ...