Cryptology ePrint Archive: Report 2018/984

Pseudorandomness Against Mean and Variance Bounded Attackers

Maciej Skorski

Abstract: The recent progress in key derivation (Barak at al. CRYPTO'11, Dodis Yu TCC'2013) introduced the concept of constrained profiles for attackers advantage, recognizing that security bounds can be significantly improved (alternatively: lots of randomness can be saved) when the advantage, as the function of the key, is bounded in mean or variance. This paper studies \emph{minimal requirements for keys} to achieve security under such restricted attackers.

We frame the problem as characterizing \emph{pseudorandomness against constrained distinguishers} and show that minimal assumptions are respectively (a) high smooth min-entropy and (b) high smooth collision entropy. This matches the (folklore extension of) assumptions of previous works.

Besides providing lower bounds, we offer more insights into this key derivation problem and elegant proof techniques of geometric flavor.

Category / Keywords: foundations / key derivation, cryptography with weak keys, pseudorandomness

Date: received 12 Oct 2018, last revised 12 Oct 2018

Contact author: maciej skorski at gmail com

Available format(s): PDF | BibTeX Citation

Note: This paper extends and fixes a flaw in my previous paper "Optimal Overcoming Weak Expectations" (currently withdrawn)

Version: 20181018:122444 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]