Title: Entropy Loss is Maximal for Uniform Inputs
Author: Leonid Reyzin
Date: September 20, 2007
Abstract:
A secure sketch (defined by Dodis et al.) is an algorithm that on an
input w produces an output s such that w can be reconstructed given
its noisy version w' and s. Security is defined in terms of two
parameters m and m': if w comes from a distribution of entropy m,
then a secure sketch guarantees that the distribution of w conditioned
on s has entropy at least m', where l = m-m' is called the entropy
loss. In this note we show that the entropy loss of any secure sketch
(or, more generally, any randomized algorithm) on any distribution is
no more than it is on the uniform distribution.