Information Security and Cryptography Research Group

Smooth Entropy and Rényi Entropy

Christian Cachin

Advances in Cryptology — EUROCRYPT '97, Lecture Notes in Computer Science, Springer-Verlag, vol. 1233, pp. 193–208, May 1997.

The notion of smooth entropy allows a unifying, generalized formulation of privacy amplification and entropy smoothing. Smooth entropy is a measure for the number of almost uniform random bits that can be extracted from a random source by probabilistic algorithms. It is known that Rényi entropy of order at least 2 of a random variable is a lower bound for its smooth entropy. On the other hand, an assumption about Shannon entropy (which is Rényi entropy of order 1) is too weak to guarantee any non-trivial amount of smooth entropy. In this work, we close the gap between Rényi entropy of order 1 and 2. In particular, we show that Rényi entropy of order $\alpha$ for any $1<\alpha<2$ is a lower bound for smooth entropy, up to a small parameter depending on $\alpha$, the alphabet size and the failure probability. The results have applications in cryptography for unconditionally secure protocols such as quantum key agreement, key agreement from correlated information, oblivious transfer, and bit commitment.

BibTeX Citation

@inproceedings{Cachin97,
    author       = {Christian Cachin},
    title        = {Smooth Entropy and {R}ényi Entropy},
    editor       = {Walter Fumy},
    booktitle    = {Advances in Cryptology --- EUROCRYPT~'97},
    pages        = {193--208},
    series       = {Lecture Notes in Computer Science},
    volume       = {1233},
    year         = {1997},
    month        = {5},
    publisher    = {Springer-Verlag},
}

Files and Links