# 1 Construction

Assume that all data are encoded using the alphabet $$\Sigma = \{0,\dots,n-1\}$$ (where $$n$$ is the length of the alphabet).

Substitution cipher. Given $$\ell \in \mathbb{Z}^+$$ which is the fixed length of the plaintext, define the following encryption scheme $$\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$$:

• Message space $$\mathcal{M} = \{0,\dots,n-1\}^\ell$$.
• Key space $$\mathcal{K} = \mathfrak{S}_\Sigma$$ which is the symmetric group on $$\Sigma$$. (Thus $$|\mathcal{K}| = n!$$)
• Ciphertext space $$\mathcal{C} = \{0,\dots,n-1\}^\ell$$.
• $$\mathsf{Gen}$$ outputs a permutation (as the key) $$\sigma \in \mathcal{K}$$ according to the uniform distribution.
• $$\mathsf{Enc}$$ takes as input a key $$\sigma \in \mathcal{K}$$ and a message $$m \in \mathcal{M}$$, and outputs the ciphertext $\mathsf{Enc}_k(m_1 \dots m_\ell) = c_1 \dots c_\ell \textrm{, where } c_i := \sigma(m_i).$
• $$\mathsf{Dec}$$ takes as input a key $$\sigma \in \mathcal{K}$$ and a ciphertext $$c \in \mathcal{C}$$, and outputs the message $\mathsf{Dec}_k(c_1 \dots c_\ell) = m_1 \dots m_\ell \textrm{, where } m_i := \sigma^{-1}(c_i).$ Note that since $$\sigma$$ is bijective, its inverse $$\sigma^{-1}$$ is guaranteed to exist uniquely.

Obviously, $\sigma^{-1}(\sigma(m_i)) = m_i$ thus this encryption scheme satisfies the correctness requirement.

Remark 1.1. The shift cipher may be considered as a limited form of the substitution cipher, where the key space is merely a permutation group $$\mathcal{K} < \mathfrak{S}_\Sigma$$.

# 2 Secrecy and Cryptanalysis

Notice that $$|\mathcal{K}| = n!$$, $$|\mathcal{M}| = n^\ell$$. If $$|\mathcal{K}| < |\mathcal{M}|$$, then the scheme cannot be perfectly secret.

Theorem 2.1. Substitution cipher is not perfectly secret when $$\ell$$ is sufficiently large (e.g., $$\ell \geq n$$).

Possible cryptanalysis: Frequency analysis.