Computational Cipher

Updated 11 Aug 2026

•
Definition
- •
  a pair of efficient algorithms $(E, D)$ — the practical refinement of a Shannon Cipher, where encryption/decryption must actually be computable in reasonable time, and encryption may be probabilistic
•
Probabilistic encryption
- •
  for the same key and message, $E(k, m)$ may output different ciphertexts on different runs; written $c \xleftarrow{R} E(k, m)$
- •
  correctness now requires that decryption recovers the message with probability 1, across the randomness of encryption
•
Relationship to Shannon ciphers
- •
  any deterministic computational cipher is also a Shannon cipher; a Shannon cipher only qualifies as a computational cipher if its functions happen to be efficiently computable
•
Note
- •
  from this point on in the book, "cipher" means computational cipher by default
•
Related
- •
  Shannon Cipher
- •
  Semantic Security

Linked references 3