We study the fundamental problem of index coding under an additional privacy constraint that requires each receiver to learn nothing more about the collection of messages beyond its demanded messages from the server and what is available to it as side information. To enable such private communication, we allow the use of a collection of independent secret keys, each of which is shared amongst a subset of users and is known to the server. The goal is to study properties of the key access structures that make the problem feasible and then design encoding and decoding schemes efficient in the size of the server transmission as well as the sizes of the secret keys. We call this theprivate index codingproblem. We begin by characterizing the key access structures that make private index coding feasible. We also give conditions to check if a given linear scheme is a valid private index code. For up to three users, we characterize the rate region of feasible server transmission and key rates, and show that all feasible rates can be achieved using scalar linear coding and time sharing; we also show that scalar linear codes are sub-optimal for four receivers. The outer bounds used in the case of three users are extended to arbitrary number of users and seen as a generalized version of the well-known polymatroidal bounds for the standard non-private index coding. We also show that the presence of common randomness and private randomness does not change the rate region. Furthermore, we study the case where the server has the ability to multicast to any subset of users, and demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required.

We study the problem of index coding under the privacy requirement that receivers do not learn anything more than the messages they already have as side information and the message they want from the server. To achieve this private index coding, we consider the use of secret keys that are shared among various subsets of users and the server. We characterize key access structures that allow private index coding. For up to three receivers, we characterize the rate region of transmission and key rates and show that scalar coding is optimal; we also show that scalar linear codes are sub-optimal for four receivers. Furthermore, when no keys are available, we consider a weaker notion of privacy analogous to weak security. Finally, for a different setting in which the server is allowed to send messages exclusively to a subset of users, we study the number of transmissions required to achieve error-free decoding and privacy.