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 key-derivation function (KDF) $h$ that converts any random source $X$ of min-entropy $k$ into a sufficiently ``good'' key $h(X)$, guaranteeing that $P(h(X))$ has comparable security ${\delta }^{\prime }$ which is `close' to $\delta$. Seeded randomness extractors provide a generic way to solve this problem for \emph{all} applications $$, with resulting security $$, provided that we start with entropy $$. By a result of Radhakrishnan and Ta-Shma, this bound on $$ (called the ``RT-bound'') is also known to be tight in general. Unfortunately, in many situations the loss of $$ bits of entropy is unacceptable. This motivates the study KDFs with less entropy waste by placing some restrictions on the source $$ or the application $$. In this work we obtain the following new positive and negative results in this regard: - Efficient samplability of the source $$ does not help beat the RT-bound for general applications. This resolves the SRT (samplable RT) conjecture of Dachman-Soled et al.~\cite{DGKM12} in the affirmative, and also shows that the existence of computationally-secure extractors beating the RT-bound implies the existence of one-way functions. - We continue in the line of work initiated by Barak et al. \cite{BDK+11} and construct new information-theoretic KDFs which beat the RT-bound for large but restricted classes of applications. Specifically, we design efficient KDFs that work for all unpredictability applications $$ (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract \emph{all} of the entropy $$ with a very modest security loss $$, or alternatively, (2) achieve essentially optimal security $$ with a very modest entropy loss $$. In comparison, the best prior results from \cite{BDK+11} for this class of applications would only guarantee $$ when $$, and would need $$ to get $$. - The weaker bounds of \cite{BDK+11} hold for a larger class of so-called ``square-friendly'' 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, information-theoretic notion of $$-unpredictability extractors, which guarantee ``induced'' security $$ for any $$-secure unpredictability application $$, and characterize the parameters achievable for such unpredictability extractors. Of independent interest, we also relate this notion to the previously-known notion of (min-entropy) condensers, and improve the state-of-the-art parameters for such condensers.