Simple and Tight Bounds for Information Reconciliation and Privacy Amplification

Shannon entropy is a useful and important measure in information processing, for instance, data compression or randomness extraction, under the assumption—which can typically safely be made in

communication theory

—that a certain random experiment is independently repeated many times. In

cryptography

, however, where a system’s working has to be proven with respect to a malicious adversary, this assumption usually translates to a restriction on the latter’s knowledge or behavior and is generally not satisfied. An example is quantum key agreement, where the adversary can attack each particle sent through the quantum channel differently or even carry out coherent attacks, combining a number of particles together. In information-theoretic key agreement, the central functionalities of

information reconciliation

and

privacy amplification

have, therefore, been extensively studied in the scenario of

general distributions

: Partial solutions have been given, but the obtained bounds are arbitrarily far from tight, and a full analysis appeared to be rather involved to do. We show that, actually, the general case is not more difficult than the scenario of independent repetitions—in fact, given our new point of view, even simpler. When one analyzes the possible efficiency of data compression and randomness extraction in the case of independent repetitions, then Shannon entropy

H

is the answer. We show that

H

can, in these two contexts, be generalized to two

very simple

quantities—

$H_0^\epsilon$

and

$H_\infty^\epsilon$

, called

smooth Rényi entropies

—which are tight bounds for data compression (hence, information reconciliation) and randomness extraction (privacy amplification), respectively. It is shown that the two new quantities, and related notions, do not only extend Shannon entropy in the described contexts, but they also share central properties of the latter such as the chain rule as well as sub-additivity and monotonicity.