International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 30 April 2014

Grégory Demay, Peter Gaži, Ueli Maurer, Björn Tackmann
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.