Key Derivation without Entropy Waste

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

δ

. 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

δ

′ which is ‘close’ to

δ

.

Seeded randomness extractors provide a generic way to solve this problem for

all

applications

P

, with resulting security

δ

′ = 

O

(

δ

), provided that we start with entropy

$k\ge m+2\log\left({1}/{\delta}\right)-O(1)$

. By a result of Radhakrishnan and Ta-Shma, this bound on

k

(called the “RT-bound”) is also known to be tight in general. Unfortunately, in many situations the loss of

$2\log\left({1}/{\delta}\right)$

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 RT-bound for general applications. This resolves the SRT (samplable RT) conjecture of Dachman-Soled et al. [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. [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

P

(e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract

all

of the entropy

k

 = 

m

with a very modest security loss

$\delta'=O(\delta\cdot \log\left({1}/{\delta}\right))$

, or alternatively, (2) achieve essentially optimal security

δ

′ = 

O

(

δ

) with a very modest entropy loss

$k \ge m+\log\!\log\left({1}/{\delta}\right)$

. In comparison, the best prior results from [BDK+11] for this class of applications would only guarantee

$\delta'=O(\sqrt{\delta})$

when

k

 = 

m

, and would need

$k\ge m+\log\left({1}/{\delta}\right)$

to get

δ

′ = 

O

(

δ

).

The weaker bounds of [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 (

k

,

δ

,

δ

′)

-unpredictability extractors

, which guarantee “induced” security

δ

′ for any

δ

-secure unpredictability application

P

, 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.