Paper 2016/159
Pseudoentropy: Lower-bounds for Chain rules and Transformations
Krzysztof Pietrzak and Maciej Skorski
Abstract
Computational notions of entropy have recently found many applications, including
leakage-resilient cryptography, deterministic encryption or memory delegation.
The two main types of results which make computational notions so useful are
(1) Chain rules, which quantify by how much the computational entropy of a variable decreases if conditioned on some other variable (2) Transformations, which quantify to which extend one type of entropy implies another.
Such chain rules and transformations typically lose a significant amount in
quality of the entropy, and are the reason why applying these results one gets rather weak
quantitative security bounds. In this paper we for the first time prove lower bounds in this context, showing that existing
results for transformations are, unfortunately, basically optimal for non-adaptive black-box reductions (and it's hard
to imagine how non black-box reductions or adaptivity could be useful here.)
A variable
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- pseudorandomnesspseudoentropylower bounds
- Contact author(s)
- maciej skorski @ gmail com
- History
- 2016-02-18: received
- Short URL
- https://ia.cr/2016/159
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/159, author = {Krzysztof Pietrzak and Maciej Skorski}, title = {Pseudoentropy: Lower-bounds for Chain rules and Transformations}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/159}, year = {2016}, url = {https://eprint.iacr.org/2016/159} }