Welcome to the resource topic for 2016/158
Title:
A Subgradient Algorithm For Computational Distances and Applications to Cryptography
Authors: 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.
ePrint: https://eprint.iacr.org/2016/158
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .