Information leakage to a guessing adversary in index coding is studied, where some messages in the system are sensitive and others are not. The non-sensitive messages can be used by the server like secret keys to mitigate leakage of the sensitive messages to the adversary. We construct a deterministic linear coding scheme, developed from the rank minimization method based on fitting matrices (Bar-Yossef et al. 2011). The linear scheme leads to a novel upper bound on the optimal information leakage rate, which is proved to be tight over all deterministic scalar linear codes. We also derive a converse result from a graph-theoretic perspective, which holds in general over all deterministic and stochastic coding schemes.

Two main privacy models for sanitising datasets are differential privacy (DP) and syntactic privacy. The former restricts individual values’ impact on the output based on the dataset while the latter restructures the dataset before publication to link any record to multiple sensitive data values. Besides both providing mechanisms to sanitise data, these models are often applied independently of each other and very little is known regarding how they relate. Knowing how privacy models are related can help us develop a deeper understanding of privacy and can inform how a single privacy mechanism can fulfil multiple privacy models. In this paper, we introduce a framework that determines if the privacy mechanisms of one privacy model can also guarantee privacy for another privacy model. We apply our framework to understand the relationship between DP and a form of syntactic privacy called t-closeness. We demonstrate, for the first time, how DP and t-closeness can be interpreted in terms of each other by introducing generalisations and extensions of both models to explain the transition from one model to the other. Finally, we show how applying one mechanism to guarantee multiple privacy models increases data utility compared to applying separate mechanisms for each privacy model.

This paper considers the problem of publishing data$X$while protecting the correlated sensitive information$S$. We propose a linear method to generate the sanitized data$Y$with the same alphabet$\mathcal{Y}=\mathcal{X}$that attains local differential privacy (LDP) and log-lift at the same time. It is revealed that both LDP and log-lift are inversely proportional to the statistical distance between conditional probability$P_{Y\vert S}(x\vert s)$and marginal probability$P_{Y}(x)$: the closer the two probabilities are, the more private$Y$is. Specifying$P_{Y\vert S}(x\vert s)$that linearly reduces this distance$\vert P_{Y\vert S}(x\vert s)-P_{Y}(x)\vert =(1-\alpha)\vert P_{X\vert S}(x\vert s)-P_{X}(x)\vert, \forall s, x$for some$\alpha\in(0,1]$, we study the problem of how to generate$\mathrm{Y}$from the original data$S$and$X$. The Markov randomization/sanitization scheme$P_{Y\vert X}(x\vert x^{\prime})=P_{Y\vert S,X}(x\vert s,x^{\prime})$is obtained by solving linear equations. The optimal non-Markov sanitization, the transition probability$P_{Y\vert S,X}(x\vert s,x^{\prime})$that depends on$S$,, can be determined by maximizing the data utility subject to linear equality constraints on data privacy. We compute the solution for two linear utility function: the expected distance and total variance distance. It is shown that the non-Markov randomization significantly improves data utility and the marginal probability$P_{X}(x)$remains the same after the linear sanitization method:$P_{Y}(x)=P_{X}(x),\forall x\in \mathcal{X}$.

We study the information leakage to a guessing adversary in zero-error source coding. The source coding problem is defined by a confusion graph capturing the distinguishability between source symbols. The information leakage is measured by the ratio of the adversary's successful guessing probability after and before eavesdropping the codeword, maximized over all possible source distributions. Such measurement under the basic adversarial model where the adversary makes a single guess and the guess is regarded successful if and only if the estimator sequence equals to the true source sequence is known as the maximum min-entropy leakage or the maximal leakage in the literature. We develop a single-letter characterization of the optimal normalized leakage under the basic adversarial model, together with an optimum-achieving memoryless stochastic mapping scheme. An interesting observation is that the optimal normalized leakage is equal to the optimal compression rate with fixed-length source codes, both of which can be simultaneously achieved by some deterministic coding schemes. We then extend the leakage measurement to generalized adversarial models where the adversary makes multiple guesses and allows a certain level of distortion, for which we derive single-letter lower and upper bounds.

In this work, we study the secure index coding problem where there are security constraints on both legitimate receivers and eavesdroppers. We develop two performance bounds (i.e., converse results) on the symmetric secure capacity. The first one is an extended version of the basic acyclic chain bound (Liu and Sadeghi, 2019) that takes security constraints into account. The second converse result is a novel information-theoretic lower bound on the symmetric secure capacity, which is interesting as all the existing converse results in the literature for secure index coding give upper bounds on the capacity.

We study the information leakage to a guessing adversary in index coding with a general message distribution. Under both vanishing-error and zero-error decoding assumptions, we develop lower and upper bounds on the optimal leakage rate, which are based on the broadcast rate of the subproblem induced by the set of messages the adversary tries to guess. When the messages are independent and uniformly distributed, the lower and upper bounds match, establishing an equivalence between the two rates.

This paper studies the tradeoff in privacy and utility in a single-trial multi-terminal guessing (estimation) framework using a system model that is inspired by index coding. There are n independent discrete sources at a data curator. There are m legitimate users and one adversary, each with some side information about the sources. The data curator broadcasts a distorted function of sources to legitimate users, which is also overheard by the adversary. In terms of utility, each legitimate user wishes to perfectly reconstruct some of the unknown sources and attain a certain gain in the estimation correctness for the remaining unknown sources. In terms of privacy, the data curator wishes to minimize the maximal leakage: the worst-case guessing gain of the adversary in estimating any target function of its unknown sources after receiving the broadcast data. Given the system settings, we derive fundamental performance lower bounds on the maximal leakage to the adversary, which are inspired by the notion of confusion graph and performance bounds for the index coding problem. We also detail a greedy privacy enhancing mechanism, which is inspired by the agglomerative clustering algorithms in the information bottleneck and privacy funnel problems.

In index coding, a server broadcasts multiple messages to their respective receivers, each with some side information that can be utilized to reduce the amount of communication from the server. Distributed index coding is an extension of index coding in which the messages are broadcast from multiple servers, each storing different subsets of the messages. In this paper, the optimal tradeoff among the message rates and the server broadcast rates, which is defined formally as the capacity region, is studied for a general distributed index coding problem. Inner and outer bounds on the capacity region are established that have matching sum-rates for all 218 non-isomorphic four-message problems with equal link capacities for all the links from servers to receivers. The proposed inner bound is built on a distributed composite coding scheme that outperforms the existing schemes by incorporating more flexible decoding configurations and enhanced fractional rate allocations into two-stage composite coding, a scheme that was originally introduced for centralized index coding. The proposed outer bound is built on the polymatroidal axioms of entropy, as well as functional dependences such as the fd-separation introduced by the multi-server nature of the problem. This outer bound utilizes general groupings of servers with different levels of granularity, which allows a natural tradeoff between computational complexity and tightness of the bound, and includes and improves upon all existing outer bounds for distributed index coding. Specific features of the proposed inner and outer bounds are demonstrated through concrete examples with four or five messages.

In this paper, we study the information-theoretic converse for the index coding problem. We generalize the definition for the alignment chain, introduced by Maleki et al., to capture more flexible relations among interfering messages at each receiver. Based on this, we derive improved converse results for the single-server index coding problem. Compared to the maximum acyclic induced subgraph (MAIS) bound, the new bounds are always as tight and can strictly outperform the MAIS bound. They can also be useful for large problems, where the generally tighter polymatroidal bound is computationally impractical. We then extend these new bounds to the multi-server index coding problem. We also present a separate, but related result where we identify a smaller single-server index coding instance, compared to those identified in the literature, for which non-Shannon-type inequalities are necessary to give a tighter converse.

Simplification methods are introduced for composite coding, which is an existing layered random coding technique for the index coding problem. As the problem size grows, the original number of composite indices grows exponentially and the number of possible decoding configurations (decoding sets) grows super exponentially, leading to considerably high computational complexity. The proposed simplifications address both issues and do not affect the performance (tightness) of the coding scheme. Removing composite indices is achieved by pairwise comparison of any two indices and removing one if its corresponding rate can be transferred without loss to the other in the expressions of the achievable rate region. Decoding configurations are reduced by establishing a baseline or natural decoding configuration, where no smaller decoding configuration can provide a strictly larger rate region. A heuristic method is also proposed for reducing the number of composite indices even further, but possibly with some performance loss. Numerical results demonstrate good performance with substantial reduction in complexity. To achieve the capacity region for all 9608 non-isomorphic index coding problems with n = 5, a single natural decoding configuration per problem and less than 3 out of 25-1=31 composite indices are sufficient, on average. In only 31 problems, 7 to at most 10 composite indices are used.

We extend the composite coding (CC) scheme for the index coding problem from two layers to more layers of random binning. We explicitly introduce the three-layer composite coding (TLCC) scheme and provide the achievable rate region and the error analysis for it. We present a concrete non-trivial example with n = 7 messages where the TLCC strictly outperforms the CC scheme. We also present a number of simplification methods for the TLCC scheme towards better understanding of the scheme, as well as significantly reducing its computational complexity. We further prove that even a simplified version of the TLCC, which can be possibly weaker than the TLCC, still subsumes the CC scheme.

The distributed index coding problem is studied, whereby multiple messages are stored at different servers to be broadcast to receivers with side information. First, the existing composite coding scheme is enhanced for the centralized (single-server) index coding problem, which is then merged with fractional partitioning of servers to yield a new coding scheme for distributed index coding. New outer bounds on the capacity region are also established. For all distributed index coding problems with n ≤ 4 messages and equal server link capacities, the achievable sum-rate of the proposed distributed composite coding scheme match the outer bounds, thus establishing the sum-capacity for these problems.