Preserving Privacy while Broadcasting: k-Limited-Access Schemes

Index coding employs coding across clients within the same broadcast domain. This typically assumes that all clients learn the coding matrix so that they can decode and retrieve their requested data. However, learning the coding matrix can pose privacy concerns: it may enable clients to infer information about the requests and side information of other clients [1]. In this paper, we formalize the intuition that the achieved privacy can increase by decreasing the number of rows of the coding matrix that a client learns. Based on this, we propose the use of k-limited-access schemes: given an index coding scheme that employs Τ transmissions, we create a k-limited-access scheme with T_k ≥ T transmissions, and with the property that each client learns at most k rows of the coding matrix to decode its message. We derive upper and lower bounds on T_k for all values of k, and develop deterministic designs for these schemes for which T_k has an order-optimal exponent for some regimes.