====Introduction====
Classical entropy quantities are a way to quantify how much information is revealed in a random event. Shannon first introduced a way to quantify information by associating to an event occuring with probability p, an amount of information -\log p (as is standard in information theory, logarithms are taken in base 2 and so information is measured in bits). If an unlikely event occurs, one gains a large amount of information. The Shannon entropy is the average amount of information gained by observing the outcome of an event. In some cases, in particular ones relevant to cryptography, the average amount of information is not a good quantity, since it assumes many independent repetitions of the same experiment.
====Random Events====
When we discuss random events, we assume that they occur according to
a pre-defined ensemble of possible outcomes of that event, and
associated probabilities. Event X is a single instance drawn from
the ensemble \{0,1,\ldots,|X|\} with probabilities
\{p_0,p_1,\ldots,p_{|X|}\}. We call this probability distribution
P_X. The terminology X=x refers to a single instance drawn from
this distribution taking the value x. One similarly defines
distributions over more than one random variable. For instance,
P_{XY} is the joint distribution of X and Y, and P_{X|Y=y} is
the distribution of X conditioned on the fact that Y takes the
value Y=y.
====Shannon Entropy====
It was Shannon who pioneered the mathematical formulation of
information. In essence his insight was that an event
that occurs with probability p could be associated with an amount of
information -\log p. Consider many independent
repetitions of random event X. The average information revealed by
each instance of X is given by the Shannon entropy of X defined as
follows.
The '''Shannon entropy''' associated with an event x drawn from random
distribution X is
H(X)\equiv\sum_{x\in X}-P_X(x)\log P_X(x).
Likewise, one can define conditional Shannon entropies. H(X|Y=y)
denotes the Shannon entropy of X given Y=y. It measures the average
amount of information one learns from a single instance of X if one
possesses string y\in Y, where X,Y are chosen according to joint
distribution P_{XY}. One can average this quantity to form
H(X|Y), the conditional Shannon entropy.
The '''conditional Shannon entropy''' of an event X given Y is defined by
H(X|Y)\equiv\sum_{x\in X, y\in Y}-P_Y(y)P_{X|Y=y}(x)\log P_{X|Y=y}(x).
This leads one to define the '''mutual Shannon information''' between X
and Y by
I(X:Y)\equiv H(X)-H(X|Y)=H(Y)-H(Y|X).
In some sense, this is the amount of information in common to the two strings X and
Y.
Shannon information was first used to solve problems of compression,
and communication over a noisy channel, as given in the following
theorems.
'''Source coding theorem :'''
Consider a source emitting independent and indentically distributed
(i.i.d.) random variables drawn from distribution P_X. For any
\epsilon>0 and R>H(X), there exists an encoder such that for
sufficiently large N, any sequence drawn from P_X^N can be
compressed to length NR, and a decoder such that, except with
probability <\epsilon, the original sequence can be restored from
the compressed string.
Furthermore, if one tries to compress the same source using R
bits per instance, it is virtually certain that information will be
lost.
For a discrete, memoryless channel, in which Alice sends a random
variable drawn from X to Bob who receives Y, the ''channel capacity'' is defined by C\equiv \max_{P_X}I(X:Y).
'''Noisy channel coding theorem :'''
Consider Alice communicate with Bob via a discrete memoryless channel
which has the property that if Alice draws from an i.i.d. source X,
Bob receives Y. For any \epsilon>0 and R, for large enough
N, there exists an encoding of length N and a decoder such that
\geq RN bits of information are conveyed by the channel for each
encoder-channel-decoder cycle, except with probability <\epsilon.
Notice that in the noisy channel coding theorem, the channel is
memoryless, and Alice has an i.i.d. source. In other words, all
uses of the channel are independent of one another. This is the
situation in which Shannon information is useful. However, in
cryptographic scenarios where the channel may be controlled by an
eavesdropper, such an assumption is not usually valid. Instead, other
entropy measures have been developed that apply for these cases.
====Beyond Shannon entropy====
Rényi introduced the following generalization of the
Shannon entropy.
The '''Rényi entropy of order \alpha''' is defined by
H_{\alpha}(X)\equiv\frac{1}{1-\alpha}\log\sum_{x\in X}P_X(x)^{\alpha}.
We have, H_1(X)\equiv\lim_{\alpha\rightarrow 1}H_{\alpha}(X)=H(X).
Two other important cases are H_0(X)=\log|X| and
H_{\infty}(X)=-\log\max_{x\in X}P_X(x). A useful property is that, for
\alpha\leq\beta, H_{\alpha}(X)\geq H_{\beta}(X).
H_0(X) is sometimes called the '''max entropy''' of X. It is important for ''information reconciliation'', which in essence is error correction.
H_{\infty}(X) is sometimes called the '''min entropy''' of X.
It is important for ''privacy amplification''. There, the
presence of an eavesdropper means that it no longer suffices to
consider each use of the channel as independent. The min entropy
represents the maximum amount of information that could be learned
from the event X, so describes the worst case scenario. In a
cryptographic application, one wants to be assured security even in
the worst case.
In general, Rényi entropies are strongly
discontinuous. As an example, consider the two distributions P_X and
Q_X defined on x\in\{1,\ldots,2^n\}. Take
P_X(1)=2^{-\frac{n}{4}}, P_X(x\neq
1)=\frac{1-2^{-\frac{n}{4}}}{2^n-1}, and Q_X to be the uniform
distribution. The difference between min entropies is
\frac{3n}{4}. In the large n
limit, the two distributions have distance \approx 2^{-\frac{n}{4}},
which is exponentially small, while the difference in min entropies
becomes arbitrarily large.
Smoothed versions of these
quantities have been introduced which remove such discontinuities. In
essence, these smoothed quantities involve optimizing such quantities
over a small region of probability space. They have operational
significance in cryptography in that they provide the relevant
quantities for information reconciliation and privacy amplification.
The conditional versions of these smoothed entropies are relevant in cryptography, hence we provide a
definition of these directly.
For a distribution P_{XY}, and smoothing parameter \epsilon>0, we
define the following '''smoothed Rényi entropies: '''
\begin{array}{ccc}
H_0^{\epsilon}(X|Y)\equiv\min_{\Omega}\max_y\log|\{x:P_{X\Omega|Y=y}(x)>0\}|\\
H_{\infty}^{\epsilon}(X|Y)\equiv\max_{\Omega}\left(-\log\max_y\max_x P_{X\Omega|Y=y}(x)\right),
\end{array}
where \Omega is a set of events with total probability at least
1-\epsilon.
More generally, the smooth Rényi entropy of order \alpha can be
defined. However, up to an additive constant these equal
either H_0^{\epsilon} (for \alpha<1) or H_{\infty}^{\epsilon}
(for \alpha>1). It is
also worth noting that for a large number of independent repetitions
of the same experiment, the Rényi entropies tend to the Shannon
entropy, that is,
\lim_{\epsilon\rightarrow 0}\lim_{n\rightarrow\infty}\frac{H_{\alpha}^{\epsilon}(X^n|Y^n)}{n}=H(X|Y).
====Significance to cryptography====
'''Information Reconciliation'''
The task of information reconciliation can be stated as follows.
Alice has string X and Bob Y, these being chosen with joint
distribution P_{XY}. Alice also possesses some additional
independent random string R. What is the minimum length of string
S=f(X,R) that Alice can compute such that X is uniquely obtainable
by Bob using Y, S and R, except with probability less than
\epsilon?
Renner and Wolf denote this quantity
H_{enc}^{\epsilon}(X|Y). It is tightly bounded by the relation
H_0^{\epsilon}(X|Y)\leq H_{enc}^{\epsilon}(X|Y)\leq
H_0^{\epsilon_1}(X|Y)+\log\frac{1}{\epsilon_2},
where \epsilon_1+\epsilon_2=\epsilon.
It is intuitively clear why H_0^{\epsilon}(X|Y) is the correct
quantity. Recall the definition
H_0^{\epsilon}(X|Y)\equiv\min_{\Omega}\max_y\log|\{x:P_{X\Omega|Y=y}(x)>0\}|,
where \Omega is a set of events with total probability at least
1-\epsilon. The size of the set of strings x that could have
generated Y=y given \Omega is |\{x:P_{X\Omega|Y=y}(x)>0\}|.
Alice's additional information needs to point to one of these. It
hence requires \log |\{x:P_{X\Omega|Y=y}(x)>0\}| bits to encode.
Since Alice does not know y, she must assume the worst, hence we
maximize on y. Furthermore, since some error is tolerable, we
minimize on \Omega, by cutting away unlikely events from the
probability distribution.
'''Privacy Amplification'''
In essence, this task seeks to find the maximum length of string Alice
and Bob can form from their shared string such that Eve has no
information on this string.
This task can be stated more formally as follows. Alice possesses
string X and Eve Z, distributed according to P_{XZ}. Alice also
has some uncorrelated random string R. What is the maximum length
of a binary string S=f(X,R), such that for a uniform random
variable U that is independent of Y and R, we have S=U, except
with probability less than \epsilon?
Again, this quantity, denoted H_{ext}^{\epsilon}(X|Z), has been defined
and bounded by Renner and Wolf :
H_{\infty}^{\epsilon_1}(X|Z)-2\log\frac{1}{\epsilon_2}\leq
H_{ext}^{\epsilon}(X|Z)\leq H_{\infty}^{\epsilon}(X|Z),
where \epsilon_1+\epsilon_2=\epsilon.
The reason that this quantity is relevant follows from the definition of extractors, which are functions commonly exploited for privacy amplification. In essence they take a non-uniform random string, and some additional catalytic randomness, to form a smaller string which is arbitrarily close to being uniform. The length reduction in the string is bounded by its min-entropy.
==References==
#
C. E. Shannon,
Bell System Technical Journal
'''27''', 379 (1948).
#
A. Rényi, in
''Proceedings of the 4th Berkeley Symposium on
Mathematics, Statistics and Probability'' (1961),
vol. 1.
#
R. Renner and
S. Wolf, in
''Advances in Cryptology --- ASIACRYPT 2005'', edited
by B. Roy
(Springer-Verlag, 2005), vol.
3788, pp. 199--216.
[[Category:Entropy]]
[[Category:Classical Information Theory]]
