How to fake auxiliary input

D. Jetchev, K.Z. Pietrzak, in:, Y. Lindell (Ed.), Springer, 2014, pp. 566–590.

OA IST-2016-681-v1+1_869_1_.pdf 313.53 KB

Conference Paper | Published | English
Lindell, Yehuda
Series Title
Consider a joint distribution (X,A) on a set. We show that for any family of distinguishers, there exists a simulator such that 1 no function in can distinguish (X,A) from (X,h(X)) with advantage ε, 2 h is only O(2 3ℓ ε -2) times less efficient than the functions in. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ε > 0 is negligible and consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of our theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt'09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem.
Publishing Year
Date Published
566 - 590
TCC: Theory of Cryptography Conference
Conference Location
San Diego, USA
Conference Date
2014-02-24 – 2014-02-26

Cite this

Jetchev D, Pietrzak KZ. How to fake auxiliary input. In: Lindell Y, ed. Vol 8349. Springer; 2014:566-590. doi:10.1007/978-3-642-54242-8_24
Jetchev, D., & Pietrzak, K. Z. (2014). How to fake auxiliary input. In Y. Lindell (Ed.) (Vol. 8349, pp. 566–590). Presented at the TCC: Theory of Cryptography Conference, San Diego, USA: Springer.
Jetchev, Dimitar, and Krzysztof Z Pietrzak. “How to Fake Auxiliary Input.” edited by Yehuda Lindell, 8349:566–90. Springer, 2014.
D. Jetchev and K. Z. Pietrzak, “How to fake auxiliary input,” presented at the TCC: Theory of Cryptography Conference, San Diego, USA, 2014, vol. 8349, pp. 566–590.
Jetchev D, Pietrzak KZ. 2014. How to fake auxiliary input. TCC: Theory of Cryptography Conference, LNCS, vol. 8349, 566–590.
Jetchev, Dimitar, and Krzysztof Z. Pietrzak. How to Fake Auxiliary Input. Edited by Yehuda Lindell, vol. 8349, Springer, 2014, pp. 566–90, doi:10.1007/978-3-642-54242-8_24.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
MD5 Checksum

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


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search