Privacy in Index Coding: [Formula Omitted]-Limited-Access Schemes

• Published in: IEEE transactions on information theory 2020-01, Vol.66 (5), p.2625
• Main Authors: Karmoose, Mohammed, Song, Linqi, Cardone, Martina, Fragouli, Christina
• Format: Article
• Language: English
• Subjects: Clients; Coding; Lower bounds; Messages; Order parameters; Privacy; Upper bounds
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2019.2957577

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 [Formula Omitted]-limited-access schemes: given an index coding scheme that employs [Formula Omitted] transmissions, we create a [Formula Omitted]-limited-access scheme with [Formula Omitted] transmissions, and with the property that each client needs at most [Formula Omitted] transmissions to decode her message. We derive upper and lower bounds on [Formula Omitted] for all values of [Formula Omitted], 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.