Paper 2016/158

A Subgradient Algorithm For Computational Distances and Applications to Cryptography

Maciej Skórski

Abstract

The task of finding a constructive approximation in the computational distance, while simultaneously preserving additional constrains (referred to as "simulators"), appears as the key difficulty in problems related to complexity theory, cryptography and combinatorics. In this paper we develop a general framework to \emph{efficiently} prove results of this sort, based on \emph{subgradient-based optimization applied to computational distances}. This approach is simpler and natural than KL-projections already studied in this context (for example the uniform min-max theorem from CRYPTO'13), while simultaneously may lead to quantitatively better results. Some applications of our algorithm include: \begin{itemize} \item Fixing an erroneous boosting proof for simulating auxiliary inputs from TCC'13 and much better bounds for the EUROCRYPT'09 leakage-resilient stream cipher \item Deriving the unified proof for Impagliazzo Hardcore Lemma, Dense Model Theorem, Weak Szemeredi Theorem (CCC'09) \item Showing that "dense" leakages can be efficiently simulated, with significantly improved bounds \end{itemize} Interestingly, our algorithm can take advantage of small-variance assumptions imposed on distinguishers, that have been studied recently in the context of key derivation.