Private Index Coding

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 communicatio...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2022-03, Vol.68 (3), p.2020-2049
Main Authors: Narayanan, Varun, Ravi, Jithin, Mishra, Vivek K., Dey, Bikash Kumar, Karamchandani, Nikhil, Prabhakaran, Vinod M.
Format: Article
Language:English
Subjects:
broadcasting
Codes
Coding
Decoding
Encoding
Index coding
Indexes
Messages
network security
Privacy
Randomness
Receivers
Security
Servers
Time sharing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 the private index coding problem. 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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2021.3130629