How to Smooth Entropy?

Smooth entropy of X is defined as possibly biggest entropy of a distribution Y close to X. It has found many applications including privacy amplification, information reconciliation, quantum information theory and even constructing random number generators. However the basic question about the optimal shape for the distribution Y has not been answered yet. In this paper we solve this problem for Renyi entropies in non-quantum settings, giving a formal treatment to an approach suggested at TCC'05 and ASIACRYPT'05. The main difference is that we use a threshold cut instead of a quantile cut to rearrange probability masses of X. As an example of application, we derive tight lower bounds on the number of bits extractable from Shannon memoryless sources.