Abstract
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 the 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 α for any 1 < α < 2 is a lower bound for smooth entropy, up to a small parameter depending on α, 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.
Supported by the Swiss National Science Foundation, grant no. 20-42105.94.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
C. H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin, “Experimental quantum cryptography,” Journal of Cryptology, vol. 5, no. 1, pp. 3–28, 1992.
C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer, “Generalized privacy amplification,” IEEE Transactions on Information Theory, vol. 41, pp. 1915–1923, Nov. 1995.
C. H. Bennett, G. Brassard, and J.-M. Robert, “How to reduce your enemy’s information,” in Advances in Cryptology — CRYPTO’ 85 (H. C. Williams, ed.), vol. 218 of Lecture Notes in Computer Science, pp. 468–476, Springer-Verlag, 1986.
C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy amplification by public discussion,” SIAM Journal on Computing, vol. 17, pp. 210–229, Apr. 1988.
G. Brassard and C. Crépeau, “25 years of quantum cryptography,” SIGACT News, vol. 27, no. 3, pp. 13–24, 1996.
G. Brassard and C. Crépeau, “Oblivious transfers and privacy amplification.” Proceedings of EUROCRYPT’ 97, 1997.
C. Cachin and U. Maurer, “Smoothing probability distributions and smooth entropy.” Preprint (abstract to appear in Proceedings of International Symposium on Information Theory, ISIT 97), 1997.
J. L. Carter and M. N. Wegman, “Universal classes of hash functions,” Journal of Computer and System Sciences, vol. 18, pp. 143–154, 1979.
T. M. Cover and J. A. Thomas, Elements of Information Theory. New York: Wiley, 1991.
C. Crépeau, “Efficient cryptographic protocols based on noisy channels.” Proceedings of EUROCRYPT’ 97, 1997.
J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby, “Construction of a pseudorandom generator from any one-way function,” Tech. Rep. 91-068, International Computer Science Institute (ICSI), Berkeley, 1991.
R. Impagliazzo, L. A. Levin, and M. Luby, “Pseudo-random generation from one-way functions,” in Proc. 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 12–24, 1989.
M. Kharitonov, “Cryptographic hardness of distribution-specific learning,” in Proc. 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 372–381, 1993.
M. Luby, Pseudorandomness and Cryptographic Applications. Princeton University Press, 1996.
M. Luby and A. Wigderson, “Pairwise independence and derandomization,” Tech. Rep. 95-035, International Computer Science Institute (ICSI), Berkeley, 1995.
U. M. Maurer, “Secret key agreement by public discussion from common information,” IEEE Transactions on Information Theory, vol. 39, pp. 733–742, May 1993.
N. Nisan, “Extracting randomness: How and why — a survey,” in Proc. 11th Annual IEEE Conference on Computational Complexity, 1996.
A. Rényi, “On measures of entropy and information,” in Proc. 4th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, (Berkeley), pp. 547–561, Univ. of Calif. Press, 1961.
S. Vembu and S. Verdú, “Generating random bits from an arbitrary source: Fundamental limits,” IEEE Transactions on Information Theory, vol. 41, pp. 1322–1332, Sept. 1995.
D. Zuckerman, “Simulating BPP using a general weak random source,” Algorithmica, vol. 16, pp. 367–391, 1996. Preliminary version presented at 32nd FOCS (1991).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cachin, C. (1997). Smooth Entropy and Rényi Entropy. In: Fumy, W. (eds) Advances in Cryptology — EUROCRYPT ’97. EUROCRYPT 1997. Lecture Notes in Computer Science, vol 1233. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-69053-0_14
Download citation
DOI: https://doi.org/10.1007/3-540-69053-0_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62975-7
Online ISBN: 978-3-540-69053-5
eBook Packages: Springer Book Archive