Key derivation for squared-friendly applications: Lower bounds Conference Paper


Author(s): Skórski, Maciej
Title: Key derivation for squared-friendly applications: Lower bounds
Title Series: LIPIcs
Affiliation IST Austria
Abstract: Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for 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 any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, 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. While 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.
Keywords: Lower bounds; Key derivation; Square-friendly applications
Conference Title: STACS: Symposium on Theoretical Aspects of Computer Science
Volume: 66
Conference Dates: March 8-11, 2017
Conference Location: Hannover, Germany
ISBN: 978-3-540-67141-1
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2017-03-01
Start Page: article number: 57
DOI: 10.4230/LIPIcs.STACS.2017.57
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work