Security Reduction

Updated 11 Aug 2026

•
Definition
- •
  the primary proof technique in cryptography: to prove that breaking security property X is hard, show that any efficient adversary $A$ breaking X could be mechanically converted ("wrapped") into an efficient adversary $B$ breaking some other property Y that's already assumed/proven hard
- •
  since no efficient $B$ can break Y, it follows that no efficient $A$ can break X either
•
Worked example: message recovery from semantic security
- •
  claim: if a cipher is semantically secure, no efficient adversary can recover the plaintext from a ciphertext better than random guessing (Message Recovery Attack)
- •
  proof sketch: given a message-recovery adversary $A$ , build an SS adversary $B$ that generates two random messages, forwards the SS challenge ciphertext to $A$ , and outputs "1" if $A$ 's guess matches one of them — $B$ 's SS advantage is shown to lower-bound $A$ 's message-recovery advantage, so if SS holds, message recovery must be hard too
•
Worked example: a secure PRG implies a semantically secure stream cipher
- •
  see Stream Cipher for the full "swap-to-random" reduction — one of the cleanest illustrations of the technique, and worth understanding in detail since the same "swap the pseudorandom thing for a truly random thing, argue the adversary can't tell" pattern recurs throughout cryptography
•
Related

Linked references 5