Abstract | ||
---|---|---|
We develop a conceptual approach for probabilistic analysis of adaptive adversaries via Maurer's methodology of random systems (Eurocrypt'02). We first consider a well-known comparison theorem of Maurer according to which, under certain hypotheses, adaptivity does not help for achieving a certain event. This theorem has subsequently been misinterpreted, leading to a misrepresentation with one of Maurer's hypotheses being omitted in various applications. In particular, the only proof of (a misrepresentation of) the theorem available in the literature contained a flaw. We clarify the theorem by pointing out a simple example illustrating why the hypothesis of Maurer is necessary for the comparison statement to hold and provide a correct proof. Furthermore, we prove several technical statements applicable in more general settings where adaptivity might be helpful, which can be seen as the random system analogue of the game-playing arguments recently proved by Jetchev, Özen and Stam (TCC'12). |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-34961-4_20 | ASIACRYPT |
Keywords | Field | DocType |
comparison statement,certain event,correct proof,well-known comparison theorem,conceptual approach,certain hypothesis,random system analogue,random system,adaptive adversary,game-playing argument,understanding adaptivity | Conditional probability distribution,Computer science,Misrepresentation,Probabilistic analysis of algorithms,Random permutation,Hash function,Comparison theorem,Calculus | Conference |
Volume | ISSN | Citations |
7658 | 0302-9743 | 129 |
PageRank | References | Authors |
3.13 | 20 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dimitar Jetchev | 1 | 160 | 7.64 |
Onur Özen | 2 | 236 | 8.61 |
Martijn Stam | 3 | 1659 | 67.36 |