Paper 2014/299
Optimality of Non-Adaptive Strategies: The Case of Parallel Games
Grégory Demay, Peter Gaži, Ueli Maurer, and Björn Tackmann
Abstract
Most cryptographic security proofs require showing that two systems are indistinguishable. A central tool in such proofs is that of a game, where winning the game means provoking a certain condition, and it is shown that the two systems considered cannot be distinguished unless this condition is provoked. Upper bounding the probability of winning such a game, i.e., provoking this condition, for an arbitrary strategy is usually hard, except in the special case where the best strategy for winning such a game is known to be non-adaptive. A sufficient criterion for ensuring the optimality of non-adaptive strategies is that of conditional equivalence to a system, a notion introduced in [Mau02]. In this paper, we show that this criterion is not necessary to ensure the optimality of non-adaptive strategies by giving two results of independent interest: 1) the optimality of non-adaptive strategies is not preserved under parallel composition; 2) in contrast, conditional equivalence is preserved under parallel composition.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. 2014 IEEE International Symposium on Information Theory (ISIT)
- Keywords
- indistinguishability proofsconditional equivalencerandom systemsparallel composition
- Contact author(s)
- gregory demay @ inf ethz ch
- History
- 2014-04-30: received
- Short URL
- https://ia.cr/2014/299
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/299,
author = {Grégory Demay and Peter Gaži and Ueli Maurer and Björn Tackmann},
title = {Optimality of Non-Adaptive Strategies: The Case of Parallel Games},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/299},
year = {2014},
url = {https://eprint.iacr.org/2014/299}
}
