Welcome to the resource topic for 2016/157
Title:
Key Derivation for Squared-Friendly Applications: Lower Bounds
Authors: 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.
ePrint: https://eprint.iacr.org/2016/157
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .