Show simple item record

dc.contributor.authorReyzin, Leoniden_US
dc.date.accessioned2011-10-20T04:42:48Z
dc.date.available2011-10-20T04:42:48Z
dc.date.issued2007-09-20
dc.identifier.urihttps://hdl.handle.net/2144/1688
dc.description.abstractA 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 m˜ , where λ = 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.en_US
dc.description.sponsorshipNational Science Foundation (CCR-0311485, CCF-0515100, CNS-0546614, CNS-0202067)en_US
dc.language.isoen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2007-011
dc.titleEntropy Loss is Maximal for Uniform Inputsen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record