Privacy in Index Coding: Improved Bounds and Coding Schemes

Mohammed Karmoose, Linqi Song, Martina Cardone, Christina Fragouli

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


It was recently observed in [1], that in index coding, learning the coding matrix used by the server can pose privacy concerns: curious clients can extract information about the requests and side information of other clients. One approach to mitigate such concerns is the use of k-limited-access schemes [1], that restrict each client to learn only part of the index coding matrix, and in particular, at most k rows. These schemes transform a linear index coding matrix of rank T to an alternate one, such that each client needs to learn at most k of the coding matrix rows to decode its requested message. This paper analyzes k-limited-access schemes. First, a worst-case scenario, where the total number of clients n is 2 T-1 is studied. For this case, a novel construction of the coding matrix is provided and shown to be order-optimal in the number of transmissions. Then, the case of a general n is considered and two different schemes are designed and analytically and numerically assessed in their performance. It is shown that these schemes perform better than the one designed for the case n=2 T-1.

Original languageEnglish (US)
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781538647806
StatePublished - Aug 15 2018
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: Jun 17 2018Jun 22 2018

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2018 IEEE International Symposium on Information Theory, ISIT 2018
Country/TerritoryUnited States

Bibliographical note

Funding Information:
The work of the authors was partially funded by NSF under Awards 1423271, 1314937 and 1740047.

Publisher Copyright:
© 2018 IEEE.


Dive into the research topics of 'Privacy in Index Coding: Improved Bounds and Coding Schemes'. Together they form a unique fingerprint.

Cite this