### How to fake auxiliary input

**Pietrzak, C ***(IST Austria)*

Friday 13 April 2012, 10:00-11:00

Seminar Room 1, Newton Institute

#### Abstract

We show that for any joint distribution $(X,A)$ and any family $F$ of distinguishers, e.g. polynomial size circuits, there exists an efficient (deterministic) simulator $h$ such that $F$ cannot distinguish $(X,A)$ from $(X,h(X))$, i.e. for all $f$ in $F$ we have $\bigl| E[f(X,A)]-E(f(X,h(X))] \bigr| <eps$. Efficient means exponential in the length of $A$ and polynomial in $1/eps$. Several known results, including a strong version of the dense model theorem, follow as simple corollaries. The main motivation for this work is to simplify leakage-resilience proofs which currently use the dense model theorem.

#### Video

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

## Comments

Start the discussion!