Message Recovery Attack

Updated 11 Aug 2026

•
Definition
- •
  an attack game where the adversary is given the encryption of a uniformly random message and tries to recover the message exactly
- •
  advantage: $\mathrm{MRadv}[A, \mathcal{E}] := |\Pr[\text{recovers } m] - 1/|M||$ — how much better than blind guessing the adversary does
•
Key result
- •
  semantic security implies security against message recovery — proven via reduction: any efficient message-recovery adversary can be converted into an efficient semantic-security adversary
•
Related
- •
  Semantic Security
- •
  Security Reduction

Linked references 2