Paper 2016/159
Pseudoentropy: Lowerbounds for Chain rules and Transformations
Krzysztof Pietrzak and Maciej Skorski
Abstract
Computational notions of entropy have recently found many applications, including leakageresilient 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 nonadaptive blackbox reductions (and it's hard to imagine how non blackbox reductions or adaptivity could be useful here.) A variable $X$ has $k$ bits of HILL entropy of quality $(\epsilon,s)$ if there exists a variable $Y$ with $k$ bits minentropy which cannot be distinguished from $X$ with advantage $\epsilon$ by distinguishing circuits of size $s$. A weaker notion is Metric entropy, where we switch quantifiers, and only require that for every distinguisher of size $s$, such a $Y$ exists. %For Metric entropy, we further distinguish between a notion that considers probabilistic or only weaker deterministic distinguishers. We first describe our result concerning transformations. By definition, HILL implies Metric without any loss in quality. Metric entropy often comes up in applications, but must be transformed to HILL for meaningful security guarantees. The best known result states that if a variable $X$ has $k$ bits of Metric entropy of quality $(\epsilon,s)$, then it has $k$ bits of HILL with quality $(2\epsilon,s\cdot\epsilon^2)$. We show that this loss of a factor $\Omega(\epsilon^{2})$ in circuit size is necessary. In fact, we show the stronger result that this loss is already necessary when transforming so called deterministic real valued Metric entropy to randomised boolean Metric (both these variants of Metric entropy are implied by HILL without loss in quality). The chain rule for HILL entropy states that if $X$ has $k$ bits of HILL entropy of quality $(\epsilon,s)$, then for any variable $Z$ of length $m$, $X$ conditioned on $Z$ has $km$ bits of HILL entropy with quality $(\epsilon,s\cdot \epsilon^2/ 2^{m})$. We show that a loss of $\Omega(2^m/\epsilon)$ in circuit size necessary here. Note that this still leaves a gap of $\epsilon$ between the known bound and our lower bound.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 pseudorandomnesspseudoentropylower bounds
 Contact author(s)
 maciej skorski @ gmail com
 History
 20160218: received
 Short URL
 https://ia.cr/2016/159
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/159, author = {Krzysztof Pietrzak and Maciej Skorski}, title = {Pseudoentropy: Lowerbounds for Chain rules and Transformations}, howpublished = {Cryptology ePrint Archive, Paper 2016/159}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/159}}, url = {https://eprint.iacr.org/2016/159} }