Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Smoothing probability distributions and smooth entropy

Christian Cachin, Ueli M. Maurer

Published Nov 22, 2002• 10 citations
Publisher

Abstract

We introduce smooth entropy as a measure for the number of almost uniform random bits that can be extracted from a source by probabilistic algorithms. The extraction process should be universal in the sense that it does not require the distribution of the source to be known. Rather, it should work for all sources with some structural property. Smooth entropy unifies previous work on privacy amplification and entropy smoothing. It enables a systematic investigation of the spoiling knowledge proof technique to obtain lower bounds on smooth entropy and to show new connections to Renyi entropy of order /spl alpha/>1.

DOI
10.1109/isit.1997.613006

Related papers

Entropy measures and unconditional security in cryptography

Christian Cachin

One of the most important properties of a cryptographic system is a proof of its security. In the present work, information-theoretic methods are used for proving the security of unconditionally secure cryptosystems. The security of such systems does not depend on unproven intractability assumptions. A survey of entropy measures and their applications in cryptography is presented. A new information measure, smooth entropy, is introduced to quantify the number of almost uniform random bits that can be extracted from a source by probabilistic algorithms. Smooth entropy unifies previous work on privacy amplification in cryptography and on entropy smoothing in theoretical computer science. It enables a systematic investigation of the spoiling knowledge proof technique to obtain lower bounds on smooth entropy. The R'enyi entropy of order at least 2 of a random variable is a lower bound for its smooth entropy, whereas an assumption about R'enyi entropy of order 1, which is equivalent to the ...

•Jan 1, 1997•249 citations

Hashing a source with an unknown probability distribution

Christian Cachin

Renyi entropy of order 2 characterizes how many almost uniform random bits can be extracted from a distribution by universal hashing using a technique known as "privacy amplification" in cryptography. We generalize this result and show that if P/sub S/ is the assumed distribution of a random variable with true distribution P/sub X/, then the amount of extractable almost uniform randomness corresponds to -logP[X=S], when X and S are interpreted as independent random variables.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•1 citation

Rethinking quantum smooth entropies: Tight one-shot analysis of quantum privacy amplification

Bartosz Regula, Marco Tomamichel

We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.

quant-pharXiv:2603.04493•Mar 6, 2026•0 citations

Sharp lower bounds on the extractable randomness from non-uniform sources

Boris Škorić, Chibuzo Obi, Evgeny A. Verbitskiy +1 more

Extraction of uniform randomness from (noisy) non-uniform sources is an important primitive in many security applications, e.g. (pseudo-)random number generators, privacy-preserving biometrics, and key storage based on Physical Unclonable Functions. Generic extraction methods exist, using universal hash functions. There is a trade-off between the length of the extracted bit string and the uniformity of the string. In the literature there are proven lower bounds on this length as a function of the desired uniformity. The best known bound involves a quantity known as smooth min-entropy. Unfortunately, there exist at least three definitions of smooth entropy. In this paper we compare three of these definitions, and we derive improved lower bounds on the extractable randomness.\nWe also investigate the use of almost universal hash functions, which are slightly worse at extracting randomness than universal hash functions, but are preferable in practice because they require far less resources in devices. We show that using them has negligible effect on the extractable randomness.\nKeywords: Leftover Hash Lemma; Universal hash function; Randomness extraction

•Jan 1, 2008•0 citations

A new unified method for intrinsic randomness problems of general sources

Tomohiko Uyematsu, 昇平 國松

The purpose of this paper is to establish a new unified method for random number generation from general sources. Specifically, we introduce an alternative definition of the smooth Rényi entropy of order infinity, and show a unified approach to represent the intrinsic randomness in terms of this information quantity. Our definition of the smooth Rényi entropy is easy to calculate for finite block lengths. We also represent δ-intrinsic randomness and the strong converse property in terms of the smooth Rényi entropy.

IEEE Information Theory Workshop (ITW)•Sep 1, 2013•13 citations

On the Randomness of Independent Experiments

Thomas Holenstein, Renato Renner

Smooth entropies characterize basic information-theoretic properties of random variables, such as the number of bits required to store them or the amount of uniform randomness that can be extracted from them (possibly with respect to side information). In this paper, explicit and almost tight bounds on the smooth entropies of n-fold product distributions, Pn, are derived. These bounds are expressed in terms of the Shannon entropy of a single distribution, P . The results can be seen as an extension of the asymptotic equipartition property (AEP).

IEEE Transactions on Information Theory•Mar 15, 2011•58 citations
We introduce smooth entropy as a measure for the number of almost uniform random bits that can be extracted from a source by probabilistic algorithms. The extraction process should be universal in the sense that it does not require the distribution of the source to be known. Rather, it should work for all sources with some structural property. Smooth entropy unifies previous work on privacy amplification and entropy smoothing. It enables a systematic investigation of the spoiling knowledge proof technique to obtain lower bounds on smooth entropy and to show new connections to Renyi entropy of order /spl alpha/>1.
One of the most important properties of a cryptographic system is a proof of its security. In the present work, information-theoretic methods are used for proving the security of unconditionally secure cryptosystems. The security of such systems does not depend on unproven intractability assumptions. A survey of entropy measures and their applications in cryptography is presented. A new information measure, smooth entropy, is introduced to quantify the number of almost uniform random bits that can be extracted from a source by probabilistic algorithms. Smooth entropy unifies previous work on privacy amplification in cryptography and on entropy smoothing in theoretical computer science. It enables a systematic investigation of the spoiling knowledge proof technique to obtain lower bounds on smooth entropy. The R'enyi entropy of order at least 2 of a random variable is a lower bound for its smooth entropy, whereas an assumption about R'enyi entropy of order 1, which is equivalent to the ...
We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.
Extraction of uniform randomness from (noisy) non-uniform sources is an important primitive in many security applications, e.g. (pseudo-)random number generators, privacy-preserving biometrics, and key storage based on Physical Unclonable Functions. Generic extraction methods exist, using universal hash functions. There is a trade-off between the length of the extracted bit string and the uniformity of the string. In the literature there are proven lower bounds on this length as a function of the desired uniformity. The best known bound involves a quantity known as smooth min-entropy. Unfortunately, there exist at least three definitions of smooth entropy. In this paper we compare three of these definitions, and we derive improved lower bounds on the extractable randomness.\nWe also investigate the use of almost universal hash functions, which are slightly worse at extracting randomness than universal hash functions, but are preferable in practice because they require far less resources in devices. We show that using them has negligible effect on the extractable randomness.\nKeywords: Leftover Hash Lemma; Universal hash function; Randomness extraction
The purpose of this paper is to establish a new unified method for random number generation from general sources. Specifically, we introduce an alternative definition of the smooth Rényi entropy of order infinity, and show a unified approach to represent the intrinsic randomness in terms of this information quantity. Our definition of the smooth Rényi entropy is easy to calculate for finite block lengths. We also represent δ-intrinsic randomness and the strong converse property in terms of the smooth Rényi entropy.
Smooth entropies characterize basic information-theoretic properties of random variables, such as the number of bits required to store them or the amount of uniform randomness that can be extracted from them (possibly with respect to side information). In this paper, explicit and almost tight bounds on the smooth entropies of n-fold product distributions, Pn, are derived. These bounds are expressed in terms of the Shannon entropy of a single distribution, P . The results can be seen as an extension of the asymptotic equipartition property (AEP).