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


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)
Publication info
Published elsewhere. 2014 IEEE International Symposium on Information Theory (ISIT)
indistinguishability proofsconditional equivalencerandom systemsparallel composition
Contact author(s)
gregory demay @ inf ethz ch
2014-04-30: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.