Bit-Guessing Game

Updated 11 Aug 2026

•
Definition
- •
  an equivalent, often more convenient reformulation of Semantic Security's Attack Game as a single experiment rather than two
- •
  the challenger picks a random bit $b$ , encrypts $m_b$ , and the adversary must guess $b$ ; "winning" means guessing correctly
- •
  bit-guessing advantage: $\mathrm{SSadv}^*[A, \mathcal{E}] := |\Pr[\text{correct guess}] - 1/2|$
•
Key result
- •
  $\mathrm{SSadv}[A, \mathcal{E}]=2 \cdot \mathrm{SSadv}^*[A, \mathcal{E}]$ — the two formulations are equivalent up to a constant factor, so either can be used depending on which is more convenient to analyze
•
Generalizes
- •
  this two-experiments-vs-bit-guessing equivalence holds for any Attack Game of this shape, not just semantic security
•
Related
- •
  Semantic Security
- •
  Attack Game

Linked references 3