§1 Private-Key Cryptography

Private-Key Cryptography

Private-Key Encryption for Communication over an Insecure Channel

• Private-Key Encryption offers the following solution:

  Alice and Bob first establish a secret random key $k$ over a Secure channel.

  Alice encrypts the message (plaintext) $m$ using the key to obtain a ciphertext $c$.

  Alice sends the ciphertext $c$ over the Insecure channel.

  Bob decrypts the ciphertext $c$ using the key $k$ to decipher the message $m$.

Private-Key Encryption for Secure storage of data

• Private-Key Encryption offers a solution:

  Before time $t_0$ Bob generates a private key $k$.

  At time $t_0$ Bob encrypts his data $m$ using the key $k$ and stores the resulting ciphertext $c$ in his laptop at $t_0$.

  At time $t_1$ Bob decrypts the ciphertext $c$ using the key $k$ to recover the data $m$.

Private-Key Encryption: Formal Definition

• Definition. A private-key encryption scheme on message space $\mathscr M$ is defined by algorithms $(Gen, Enc, Dec)$ :
  1. $Gen$ (Key Generation Algorithm): Generates (randomly) a key $k$ belonging to the key space $\mathscr K$.
  2. $Enc$ (Encryption Algorithm): Given as inputs a key $k \in \mathscr K$ and plaintext $m \in \mathscr M$, outputs a ciphertext $c \leftarrow {Enc}_{k}(m)$.
  3. $Dec$ (Decryption Algorithm): Given as inputs a key $k \in \mathscr K$ and ciphertext $c$, outputs $\underline{m} := {Dec}_{k}(c)$ or $\perp$.

Private-Key Encryption: Correctness

• Correctness: For all plaintexts $m \in \mathscr M$, and keys $k \in \mathscr K$ output by $Gen$, it must hold that

  $${Dec}_{k} ({Enc}_{k}(m)) = m$$

Security: Kerckhoff’s Principle

• Kerckhoff’s Principle: A cryptosystem should be secure even if the attacker knows all details about the system, other than the key.

Illustrative Private-Key Cryptosystems

The Shift Cipher

• The Shift Cipher is an old private key-encryption scheme used to encrypt (English) text.
• The key in the Shift Cipher is a single letter $k \in \{0,\ldots,25\} = \mathscr{K}$, which the $Gen$ algorithm picks at random.
• The Encryption algorithm shifts each plaintext letter by $k$ positions (wrapping around modulo $26$). $c_i = {Enc}_{k}(m_i) = m_i + k \bmod 26 \quad \forall i$.
• The Decryption algorithm shifts back each letter of the ciphertext by $k$ positions (wrapping around modulo $26$). That is $\underline{m}_i = c_i - k \bmod 26 \quad \forall i$.

Shift Cipher / Caesar Cipher

• $\mathscr M$ = {strings over uppercase English alphabet (represented as numbers from 0 to 25)}.
• $Gen$: choose uniform $k \in \{0,\ldots,25\} = \mathscr{K}$.
• $Enc_k (m_1 \ldots m_l) = c_1 \ldots c_l$ where $c_i = [m_i + k \bmod 26]$, the remainder when $m_i + k$ is divided by $26$.
• $Dec_k (c_1 \ldots c_l) = \underline{m}_1 \ldots \underline{m}_l$ where $\underline{m}_i = [c_i - k \bmod 26]$

Security of Shift Cipher?

• The Shift Cipher can be attacked by Brute-Force Analysis since there are only 26 possible keys.
• Given ciphertext $c$, simply try decrypting with every possible key $k' \in \{0,\ldots,25\}$.
• If the ciphertext is long enough, it is likely that only one message out of the 26 will ‘make sense’.

Mono-Alphabetic Substitution Cipher

• In mono-alphabetic substitution, the key defines a fixed substitution for characters in the plaintext.
• The size of the key space $\mathscr K$ is $26! \approx 2^{88}$.
• Brute-force attacks on the substitution cipher are infeasible.

Mono-Alphabetic Substitution Cipher: Sufficient Key-Space

• $c_i = Enc_k (m_i) = \Pi_k(m_i)$.

• $m_i = Dec_k (c_i) = \Pi^{-1} _k (c_i)$.

• Mono-alphabetic substitution cipher satisfies the Sufficient Key Space principle:

  Any secure encryption scheme must have a key space that is sufficiently large to make an exhaustive-search attack infeasible.

Security of Mono-Alphabetic Substitution?

• Even though the substitution cipher has large key space, it is still not secure.
• The substitution cipher can be attacked using statistical patterns in the English language.
• Long texts in English tend to have letter distributions that resemble the known average frequency distribution.

Formalising Security of Private-Key Cryptosystems

Threat Models

• Ciphertext-only attack.

  Adversary observes one or more ciphertexts and attempts to obtain information about underlying plaintexts.

• Known-plaintext attack.

  Adversary is able to learn one or more plaintext/ciphertext m/c pairs generated using some key, i.e., $(m_1, Enc_k(m_1))$, $(m_2, Enc_k(m_2))$, etc.

  Adversary wants to gain information about underlying plaintext of some other ciphertext produced using the same key.

• Chosen-plaintext attack (CPA).

  Adversary can obtain plaintext/ciphertext $m/c$ pairs for plaintexts chosen by the adversary, i.e., $(m_i, Enc_k(m_i))$ for $m_i$ chosen by Eve.

• Chosen-ciphertext attack (CCA).

  Adversary can obtain decryption of ciphertexts $c$ of her choice. i.e., $(c_i, Dec_k(c_i))$ for $c_i$ chosen by Eve.

Probability distributions of the Key and Message

• In an encryption scheme, the algorithm $Gen$ defines a distribution over the key-space $\mathscr K$. i.e., $\Pr [K = k] = \Pr [Gen \text{ outputs } k]$
• The probability distribution of the message, i.e. $\Pr [M = m]$ gives the likelihood of message $m \in \mathscr{M}$ being chosen by Alice in terms of the adversary’s a priori information about the message.

Probability Distribution of Ciphertext

• The distribution over $\mathscr C$ is obtained by using $Gen$ to choose key k ∈ 𝒦 and message $m \in \mathscr{M}$ according to the message distribution and then computing $c \leftarrow Enc_k(m)$ using the $Enc$ algorithm.

  $$\operatorname{Pr}[C=c \mid M=m]=\sum_{\substack{k: E n c_{k}(m)=c}} \operatorname{Pr}[K=k]$$

Private-Key Encryption Formulae

• In general, we have the following useful formulae:

  $$\operatorname{Pr}[C=c \mid M=m]=\sum_{\substack{k: E n c_{k}(m)=c}} \operatorname{Pr}[K=k]$$

  $$\operatorname{Pr}[C=c]=\sum_{m^{\prime}} \operatorname{Pr}\left[C=c \mid M=m^{\prime}\right] \cdot \operatorname{Pr}\left[M=m^{\prime}\right]$$

  $$\operatorname{Pr}[M=m \mid C=c]=\operatorname{Pr}[C=c \mid M=m] \cdot \frac{\operatorname{Pr}[M=m]}{\operatorname{Pr}[C=c]}$$

— Feb 1, 2023

§1 Private-Key Cryptography by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.