### Optimality of Non-Adaptive Strategies: The Case of Parallel Games

Grégory Demay, Peter Gaž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.

Available format(s)
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
Short URL
https://ia.cr/2014/299

CC BY

BibTeX

@misc{cryptoeprint:2014/299,
author = {Grégory Demay and Peter Gaž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},
note = {\url{https://eprint.iacr.org/2014/299}},
url = {https://eprint.iacr.org/2014/299}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.