Privacy in Index Coding : K-Limited-Access Schemes

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations

Author(s)

  • Mohammed Karmoose
  • Linqi Song
  • Martina Cardone
  • Christina Fragouli

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number8922781
Pages (from-to)2625-2641
Journal / PublicationIEEE Transactions on Information Theory
Volume66
Issue number5
Online published4 Dec 2019
Publication statusPublished - May 2020

Abstract

In the traditional index coding problem, a server employs coding to send messages to a set of clients within the same broadcast domain. Each client already has some messages as side information and requests a particular unknown message from the server. All clients learn the coding matrix so that they can decode and retrieve their requested data. Our starting observation comes from the work by Karmoose et al., which shows that learning the coding matrix can pose privacy concerns: it may enable a client to infer information about the requests and side information of other clients. In this paper, we mitigate this privacy concern by allowing each client to have limited access to the coding matrix. In particular, we design coding matrices so that each client needs only to learn some of (and not all) the rows to decode her requested message. We start by showing that this approach can indeed help mitigate that privacy concern. We do so by considering two different privacy metrics. The first one shows the attained privacy benefits based on a geometric interpretation of the problem. Differently, the second metric, referred to as maximal information leakage, provides upper bounds on: (i) the guessing power of the adversaries (i.e., curious clients) when our proposed approach is employed, and (ii) the effect of decreasing the number of accessible rows on the attained privacy. Then, we propose the use of k-limited-access schemes: given an index coding scheme that employsT transmissions, we create a k-limited-access scheme withTk >T transmissions, and with the property that each client needs at most k transmissions to decode her message. We derive upper and lower bounds onTk for all values of k, and develop deterministic designs for these schemes, which are universal, i.e., independent of the coding matrix. We show that our schemes are order-optimal for some parameter regimes, and we propose heuristics that complement the universal schemes for the remaining regimes.

Research Area(s)

  • broadcasting, Index coding, k-limited-access scheme, maximal information leakage, privacy

Citation Format(s)

Privacy in Index Coding : K-Limited-Access Schemes. / Karmoose, Mohammed; Song, Linqi; Cardone, Martina; Fragouli, Christina.

In: IEEE Transactions on Information Theory, Vol. 66, No. 5, 8922781, 05.2020, p. 2625-2641.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review