Information Leakage in Index Coding With Sensitive and Nonsensitive Messages

Yucheng Liu, Lawrence Ong, Parastoo Sadeghi, Sarah Johnson, Joerg Kliewer, Phee Lep Yeoh

Research output: Contribution to journalArticlepeer-review


Index coding can be viewed as a compression problem with multiple decoders with side information. In such a setup, an encoder compresses a number of messages into a common codeword such that every decoder can decode its requested messages with the help of knowing some other messages as side information. In this paper, we study how much information is leaked to a guessing adversary observing the codeword in index coding, where some messages in the system are sensitive and others are not. The non-sensitive messages can be used by the encoder in a manner similar to secret keys to mitigate leakage of the sensitive messages to the adversary. We first characterize the optimal information leakage rate of a given index coding problem by the optimal compression rate of a related problem, which is constructed by adding an extra decoder with certain parameters to the original problem. Both the achievability and converse of the characterization are derived from a graph-theoretic perspective based on confusion graphs (Alon et al. 2008). In particular, the achievable coding scheme is a randomized mapping exploiting certain symmetrical properties of the confusion graph. Our second main result is a practical deterministic linear coding scheme, developed from the rank minimization method based on fitting matrices (Bar-Yossef et al. 2011). The linear scheme leads to an upper bound on the optimal leakage rate, which is proved to be tight over all deterministic scalar linear codes. While it is shown through an example that simultaneously achieving optimal compression and leakage rates is not always possible, time-sharing between different schemes could be used to balance the compression and leakage rates. Finally, we show how our results can be applied to different variants of index coding.

Original languageEnglish (US)
Pages (from-to)803-814
Number of pages12
JournalIEEE Journal on Selected Areas in Information Theory
Issue number4
StatePublished - Dec 1 2022

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Media Technology
  • Artificial Intelligence
  • Applied Mathematics


  • compression
  • graph theory
  • guessing
  • Index coding
  • information leakage


Dive into the research topics of 'Information Leakage in Index Coding With Sensitive and Nonsensitive Messages'. Together they form a unique fingerprint.

Cite this