Simulating auxiliary inputs, revisited

M. Skórski, in:, Springer, 2017, pp. 159–179.


Conference Paper | Published | English
Series Title
LNCS
Abstract
For any pair (X, Z) of correlated random variables we can think of Z as a randomized function of X. If the domain of Z is small, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as simulating auxiliary inputs. This idea of simulating auxiliary information turns out to be a very usefull tool, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: (a) We present a novel boosting algorithm for constructing the simulator. This boosting proof is of independent interest, as it shows how to handle “negative mass” issues when constructing probability measures by shifting distinguishers in descent algorithms. Our technique essentially fixes the flaw in the TCC’14 paper “How to Fake Auxiliary Inputs”. (b) The complexity of our simulator is better than in previous works, including results derived from the uniform min-max theorem due to Vadhan and Zheng. To achieve (s,ϵ) -indistinguishability we need the complexity O(s⋅25ℓϵ−2) in time/circuit size, which improve previous bounds by a factor of ϵ−2. In particular, with we get meaningful provable security for the EUROCRYPT’09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like
Publishing Year
Date Published
2017-01-01
Acknowledgement
This work was supported by the National Science Center, Poland (2015/17/N/ST6/03564).
Volume
9985
Page
159 - 179
Conference
TCC: Theory of Cryptography Conference
IST-REx-ID

Cite this

Skórski M. Simulating auxiliary inputs, revisited. In: Vol 9985. Springer; 2017:159-179. doi:10.1007/978-3-662-53641-4_7
Skórski, M. (2017). Simulating auxiliary inputs, revisited (Vol. 9985, pp. 159–179). Presented at the TCC: Theory of Cryptography Conference, Springer. https://doi.org/10.1007/978-3-662-53641-4_7
Skórski, Maciej. “Simulating Auxiliary Inputs, Revisited,” 9985:159–79. Springer, 2017. https://doi.org/10.1007/978-3-662-53641-4_7.
M. Skórski, “Simulating auxiliary inputs, revisited,” presented at the TCC: Theory of Cryptography Conference, 2017, vol. 9985, pp. 159–179.
Skórski M. 2017. Simulating auxiliary inputs, revisited. TCC: Theory of Cryptography Conference, LNCS, vol. 9985. 159–179.
Skórski, Maciej. Simulating Auxiliary Inputs, Revisited. Vol. 9985, Springer, 2017, pp. 159–79, doi:10.1007/978-3-662-53641-4_7.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar