Paper 2013/708
Key Derivation Without Entropy Waste
Yevgeniy Dodis, Krzysztof Pietrzak, and Daniel Wichs
Abstract
We revisit the classical problem of converting an imperfect source of randomness into a usable cryptographic key. Assume that we have some cryptographic application $P$ that expects a uniformly random $m$bit key $R$ and ensures that the best attack (in some complexity class) against $P(R)$ has success probability at most $\delta$. Our goal is to design a keyderivation function (KDF) $h$ that converts any random source $X$ of minentropy $k$ into a sufficiently ``good'' key $h(X)$, guaranteeing that $P(h(X))$ has comparable security $\delta'$ which is `close' to $\delta$. Seeded randomness extractors provide a generic way to solve this problem for \emph{all} applications $P$, with resulting security $\delta' = O(\delta)$, provided that we start with entropy $k\ge m+2\logdelO(1)$. By a result of Radhakrishnan and TaShma, this bound on $k$ (called the ``RTbound'') is also known to be tight in general. Unfortunately, in many situations the loss of $2\logdel$ bits of entropy is unacceptable. This motivates the study KDFs with less entropy waste by placing some restrictions on the source $X$ or the application $P$. In this work we obtain the following new positive and negative results in this regard:  Efficient samplability of the source $X$ does not help beat the RTbound for general applications. This resolves the SRT (samplable RT) conjecture of DachmanSoled et al.~\cite{DGKM12} in the affirmative, and also shows that the existence of computationallysecure extractors beating the RTbound implies the existence of oneway functions.  We continue in the line of work initiated by Barak et al. \cite{BDK+11} and construct new informationtheoretic KDFs which beat the RTbound for large but restricted classes of applications. Specifically, we design efficient KDFs that work for all unpredictability applications $P$ (e.g., signatures, MACs, oneway functions, etc.) and can either: (1) extract \emph{all} of the entropy $k = m$ with a very modest security loss $\delta'=O(\delta\cdot \log (1/\delta))$, or alternatively, (2) achieve essentially optimal security $\delta' = O(\delta)$ with a very modest entropy loss $k \ge m+\log\log(1/\delta)$. In comparison, the best prior results from \cite{BDK+11} for this class of applications would only guarantee $\delta'=O(\sqrt{\delta})$ when $k=m$, and would need $k\ge m+\logdel$ to get $\delta'=O(\delta)$.  The weaker bounds of \cite{BDK+11} hold for a larger class of socalled ``squarefriendly'' applications (which includes all unpredictability, but also some important indistinguishability, applications). Unfortunately, we show that these weaker bounds are tight for the larger class of applications.  We abstract out a clean, informationtheoretic notion of $(k,\delta,\delta')$unpredictability extractors, which guarantee ``induced'' security $\delta'$ for any $\delta$secure unpredictability application $P$, and characterize the parameters achievable for such unpredictability extractors. Of independent interest, we also relate this notion to the previouslyknown notion of (minentropy) condensers, and improve the stateoftheart parameters for such condensers.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2014
 Keywords
 Information TheoryExtractorsCondensersKey Derivation
 Contact author(s)
 wichs @ ccs neu edu
 History
 20140206: revised
 20131103: received
 See all versions
 Short URL
 https://ia.cr/2013/708
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/708, author = {Yevgeniy Dodis and Krzysztof Pietrzak and Daniel Wichs}, title = {Key Derivation Without Entropy Waste}, howpublished = {Cryptology ePrint Archive, Paper 2013/708}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/708}}, url = {https://eprint.iacr.org/2013/708} }