  We introduce the blind index coding (BIC) problem, in which a single sender
communicates distinct messages to multiple users over a shared channel. Each
user has partial knowledge of each message as side information. However, unlike
classic index coding, in BIC, the sender is uncertain of what side information
is available to each user. In particular, the sender only knows the amount of
bits in each user's side information but not its content. This problem can
arise naturally in caching and wireless networks. In order to blindly exploit
side information in the BIC problem, we develop a hybrid coding scheme that
XORs uncoded bits of a subset of messages with random combinations of bits from
other messages. This scheme allows us to strike the right balance between
maximizing the transmission rate to each user and minimizing the interference
leakage to others. We also develop a general outer bound, which relies on a
strong data processing inequality to effectively capture the senders
uncertainty about the users' side information. Additionally, we consider the
case where communication takes place over a shared wireless medium, modeled by
an erasure broadcast channel, and show that surprisingly, combining repetition
coding with hybrid coding improves the achievable rate region and outperforms
alternative strategies of coping with channel erasure and while blindly
exploiting side information.
