*15:17*[Pub][ePrint] Optimality of Non-Adaptive Strategies: The Case of Parallel Games, by Grégory Demay and Peter Gaži and 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.