How to Fake Auxiliary Input

Consider a joint distribution (

X

,

A

) on a set

${\mathcal X}\times\{0, 1\}^\ell$

. We show that for any family

${\mathcal F}$

of distinguishers

$f : {\cal X} \times \{0, 1\}^\ell \rightarrow\{0,1\}$

, there exists a simulator

$h : {\mathcal X} \rightarrow \{0,1\}^\ell$

such that

1

no function in

${\mathcal F}$

can distinguish (

X

,

A

) from (

X

,

h

(

X

)) with advantage

ε

,

2

h

is only

O

(2

3ℓ

ε

− 2

) times less efficient than the functions in

${\mathcal F}$

.

For the most interesting settings of the parameters (in particular, the cryptographic case where

X

has superlogarithmic min-entropy,

ε

 > 0 is negligible and

${\mathcal F}$

consists of circuits of polynomial size), we can make the simulator

h

deterministic

.

As an illustrative application of our theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt’09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES.

Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem.