Name
Abstract | ||
|---|---|---|
Consider a joint distribution (X, A) on a set X x{0, 1}(l). We show that for any family F of distinguishers f : X x{0, 1}(l) -> {0, 1}, there exists a simulator h: X -> {0, 1}(l) such that no function in F can distinguish (X, A) from (X, h( X)) with advantage epsilon, h is only O(2(3l) epsilon(-2)) times less efficient than the functions in F. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, epsilon > 0 is negligible and F 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-642-54242-8_24 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Conference | 8349 | 0302-9743 |
Citations | PageRank | References |
9 | 0.53 | 25 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitar Jetchev | 1 | 160 | 7.64 |
| Krzysztof Pietrzak | 2 | 1513 | 72.60 |