Paper 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.

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
key derivationcryptography with weak keyspseudorandomness
Contact author(s)
maciej skorski @ gmail com
History
2018-10-18: received
Short URL
https://ia.cr/2018/984
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/984,
      author = {Maciej Skorski},
      title = {Pseudorandomness Against Mean and Variance Bounded Attackers},
      howpublished = {Cryptology ePrint Archive, Paper 2018/984},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/984}},
      url = {https://eprint.iacr.org/2018/984}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.