Algorithms may be randomised

Algorithms may be randomised unless otherwise indicated. Running time is worst case. If is an algorithm, $y \leftarrow A(x_1, \dots; r)$ denotes running with random coins on inputs $x_1,\dots$ and assigning the output to . If any of inputs taken by is $\bot$ , then all of its outputs are $\top$ . We let $y \leftarrow_\$ A(x_1, ...)$ be the result of picking at random and letting $y \leftarrow A(x_1, \dots; r)$ . We let $[A(x_1,\dots)]$ denote the set of all possible outputs of when invoked with inputs $x_1,\dots$ . Adversaries are algorithms. We require that adversaries never pass $\bot$ as input to their oracles.

Martin R. Albrecht et al., “Four Attacks and a Proof for Telegram”