IACR News item: 30 April 2014
Grégory Demay, Peter Gaži, Ueli Maurer, Björn Tackmann
ePrint Reportsystems 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.
Additional news items may be found on the IACR news page.