Notes on conditional entropy and commitment capacity
Nemanja Nedić,
Mladen Kovačević,
Darko Čapko,
Srdan Vukmirović
Abstract:
The so-called commitment capacity of a discrete memoryless channel is
given by the maximum of the conditional Shannon entropy H(X|Y) over all
input distributions. We examine in detail this optimization problem,
motivated by its relevance in information-theoretic cryptography. In
particular, we study the role of the channel’s connected components
in
attaining the commitment capacity, and the questions of uniqueness
and
support of the optimal (capacity-achieving) input and output
distributions. We also describe an iterative algorithm for computing the
commitment
capacity and the optimal input distribution.
2010 AMS Mathematics Subject Classification: Primary 94A60;
Secondary 94A15, 94A17.
Keywords and phrases:conditional entropy, equivocation, commitment capacity, Blahut--Arimoto algorithm.
