Paper 2016/157

Key Derivation for Squared-Friendly Applications: Lower Bounds

Maciej Skorski

Abstract

Security of a cryptographic application is typically defined by a security game. The adversary, within certain resources, cannot win with probability much better than $0$ (for unpredictability applications, like one-way functions) or much better than $\frac{1}{2}$ (indistinguishability applications for instance encryption schemes). In so called \emph{squared-friendly applications} the winning probability of the adversary, for different values of the application secret randomness, is not only close to $0$ or $\frac{1}{2}$ on average, but also concentrated in the sense that it's second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important in the context of key derivation. Barak et al. observed that for square-friendly applications one can beat the ``RT-bound'', extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a ``weak'' key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for ``weak'' keys. We show that \emph{any} application which is either (a) secure with weak keys or (b) allows for saving entropy in a key derived by hashing, \emph{must} be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC'13, CRYPTO'11) Hence, they can be understood as a general characterization of squared-friendly applications. Whereas the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.

Note: Editorial changes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
key derivationsuqare-friendly applications
Contact author(s)
maciej skorski @ gmail com
History
2016-11-26: revised
2016-02-18: received
See all versions
Short URL
https://ia.cr/2016/157
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/157,
      author = {Maciej Skorski},
      title = {Key Derivation for Squared-Friendly Applications: Lower Bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2016/157},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/157}},
      url = {https://eprint.iacr.org/2016/157}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.