Shannon Ciphers and Perfect Security

Shannon cipher, named after mathematician Claude Shannon (1916–2001) is a simplified cipher mechanism for encrypting a message using a shared secret key. A cipher is generally defined simply as an algorithm for performing encryption or decryption, i.e. “a series of well-defined steps that can be followed as a procedure”.

Example (Boneh & Shoup, 2020)Suppose Claude and Marvin want to use a ciper such that Claude can send an encrypted message that only Marvin can read.Then, Claude and Marvin must in advance agree on a key k ∈ K. Assuming they do, then when Claude wants to send a message m ∈ M to Marvin, he encrypts m under k, obtaining the ciphertext c = E(k,m) ∈ C, and then sends c to Marvin via some communication channel. Upon receiving the encrypted message c, Marvin decrypts c under k. The correctness property ensures that D(k,c) is the same as Claude's original message m. 

Regarded by many as the foundation of modern cryptography, the concept of a Shannon cipher were first introduced in the 1949 paper Communication Theory and Secrecy Systems published by Shannon in a Bell Systems Technical Journal. The results Shannon presented in the paper was based on an earlier version of his research in a classified report entitled A Mathematical Theory of Cryptography, and preceded Shannon’s publication of his well-known A Mathematical Theory of Communicationpublished a year before, in 1948. The following discussion of Shannon ciphers is based on Chapter 2.1 “Shannon ciphers and perfect security” in the book A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup.

Continue reading