Simulating auxiliary inputs, revisited

DOI10.1007/978-3-662-53641-4_7zbMATH Open1369.94567arXiv1503.00484OpenAlexW2478529919MaRDI QIDQ3179356FDOQ3179356

Authors: Maciej Skórski 

Publication date: 21 December 2016

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

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$.

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

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

zbMATH Keywords

boostingstream ciphersleakage-resilient cryptographycomputational indistinguishabilitysimulating auxiliary inputs

Mathematics Subject Classification ID

Cryptography (94A60)

Cites Work

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

Cited In (5)

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

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)