Simulating Auxiliary Inputs, Revisited
This work addresses a foundational problem in computer science with applications in cryptography and complexity theory, offering incremental improvements to known bounds.
The paper revisits the problem of simulating auxiliary inputs, fixing a flaw in the best known bound from prior work and presenting a novel boosting algorithm that improves the complexity to O(s·2^{5ℓ}ε^{-2}), which is better by a factor of ε^{-2} compared to previous bounds, enabling meaningful provable security for a leakage-resilient stream cipher instantiated with AES256.
For any pair $(X,Z)$ of correlated random variables we can think of $Z$ as a randomized function of $X$. Provided that $Z$ is short, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as \emph{simulating auxiliary inputs}. This idea of simulating auxiliary information turns out to be a powerful tool in computer science, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: \begin{enumerate}[(a)] We discuss and compare efficiency of known results, finding the flaw in the best known bound claimed in the TCC'14 paper "How to Fake Auxiliary Inputs". We present a novel boosting algorithm for constructing the simulator. Our technique essentially fixes the flaw. This boosting proof is of independent interest, as it shows how to handle "negative mass" issues when constructing probability measures in descent algorithms. Our bounds are much better than bounds known so far. To make the simulator $(s,ε)$-indistinguishable we need the complexity $O\left(s\cdot 2^{5\ell}ε^{-2}\right)$ in time/circuit size, which is better by a factor $ε^{-2}$ compared to previous bounds. In particular, with our technique we (finally) get meaningful provable security for the EUROCRYPT'09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like $\mathsf{AES256}$.