Simulating auxiliary inputs, revisited

DOI10.1007/978-3-662-53641-4_7MaRDI QIDQ3179356zbMATHOpenAlexFDO

Authors Maciej Skórski

Publication date 21 December 2016

Published in Theory of Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00484

zbMATH Keywords

boostingstream ciphersleakage-resilient cryptographycomputational indistinguishabilitysimulating auxiliary inputs

Mathematics Subject Classification ID

Cryptography (94A60)

Abstract: 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: �egin{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,epsilon)$-indistinguishable we need the complexity $Oleft(scdot{2}^{5ell}epsilo{n}^{-2}ight)$ in time/circuit size, which is better by a factor $epsilo{n}^{-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 $mathsfAES256$.

Recommendations

• How to fake auxiliary input
• On the complexity of simulating auxiliary input
• On cryptography with auxiliary input
• Simulatable leakage: analysis, pitfalls, and new constructions
• Efficiently simulating high min-entropy sources in the presence of side information

Cites work

• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 861531 (Why is no real title available?)
• A Leakage-Resilient Mode of Operation
• A uniform min-max theorem with applications in cryptography
• From weak to strong zero-knowledge and applications
• How to fake auxiliary input
• Leakage-resilient pseudorandom functions and side-channel attacks on Feistel networks
• Practical leakage-resilient pseudorandom objects with minimum public randomness
• Practical leakage-resilient symmetric cryptography
• Quick approximation to matrices and applications
• Security proofs for hash tree time-stamping using hash functions with small output size
• Separating succinct non-interactive arguments from all falsifiable assumptions
• Time space tradeoffs for attacks against one-way functions and PRGs

Cited in

(5)

• Efficiently simulating high min-entropy sources in the presence of side information
• On the complexity of simulating auxiliary input
• Computational two-party correlation: a dichotomy for key-agreement protocols
• How to fake auxiliary input
• Secure non-interactive simulation from arbitrary joint distributions

This page was built for publication: Simulating auxiliary inputs, revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3179356)