🌑

☀️

Hi Folks.

Home Explore About

🇨🇳 🔎

Explore / Study / Computer Science / Cryptography 785 words | 4 minutes

Construction of CPA-secure encryption scheme $\Pi$ $Π$ from any pseudorandom function. Let $F$ $F$ be a pseudorandom function. Define a private-key encryption scheme $\Pi$ $Π$ for messages of length $n$ $n$ as:
- $Gen$ : given input $1^n$ , output uniform key $k \leftarrow \{0,1\}^n$ .
- $Enc$ : given inputs a key $k \in \{0,1\}^n$ and a message $m \in \{0,1\}^n$ , choose a uniform $r \in \{0,1\}^n$ and output the ciphertext $c := \left \langle r, F_k(r) \oplus m \right \rangle$ .
- $Dec$ : given inputs a key $k \in \{0,1\}^n$ and a ciphertext $c = \langle r, s \rangle$ , output the plaintext message $m := F_k(r) \oplus s$ .

Theorem. If $F$ is a pseudorandom function, then the construction $\Pi$ is a CPA-secure private-key encryption scheme for messages of length $n$ .

$Gen$ : On input $1^n$ , output a uniformly chosen key of length $n$ , i.e., $k \leftarrow \{0,1\}^n$ .
$Enc$ $E n c$ : To encrypt message $m = m_1m_2 \ldots m_l$ $m = m_{1} m_{2} \dots m_{l}$ where each block $m_i \in \{0,1\}^n$ $m_{i} \in {0, 1}^{n}$ , we do the following:
- Choose random initialization vector ( $IV$ ) of length $n$ , i.e., set $c_0 = IV \leftarrow \{0,1\}^n$ .
- For $i = 1$ to $l$ , set $c_i = F_k (c_{i-1} \oplus m_i)$ .
- Output $\langle c_0, c_1, \ldots, c_l\rangle$ .
$Dec$ : Given inputs $\langle c_0, c_1, \ldots, c_l\rangle$ and $k \in \{0,1\}^n$ , compute $m_i := F^{-1}_k (c_i) \oplus c_{i-1}$ for $i = 1$ to $l$ . Output $\langle m_1, \dots, m_l \rangle$ .
Theorem. If $F$ is a pseudorandom function, then the construction $\Pi$ is a CPA-secure private-key encryption scheme for messages of length $l \cdot n$ .

$Gen$ : On input $1^n$ , output a uniformly chosen key of length $n$ , i.e., $k \leftarrow \{0,1\}^n$ .
$Enc$ $E n c$ : To encrypt message $m = m_1m_2 \ldots m_l$ $m = m_{1} m_{2} \dots m_{l}$ where each block $m_i \in \{0,1\}^n$ $m_{i} \in {0, 1}^{n}$ , we do the following:
- For $i = 1$ to $l$ , set $c_i = F_k (m_i)$ .
- Output $\langle c_1, \ldots, c_l\rangle$ .
$Dec$ : Given inputs $\langle c_1, \ldots, c_l\rangle$ and $k \in \{0,1\}^n$ , compute $m_i := F^{-1}_k (c_i)$ for $i = 1$ to $l$ . Output $\langle m_1, \dots, m_l \rangle$ .

$Gen$ : On input $1^n$ , output a uniformly chosen key of length $n$ , i.e., $k \leftarrow \{0,1\}^n$ .
$Enc$ $E n c$ : To encrypt message $m = m_1m_2 \ldots m_l$ $m = m_{1} m_{2} \dots m_{l}$ where each block $m_i \in \{0,1\}^n$ $m_{i} \in {0, 1}^{n}$ , we do the following:
- Choose a uniform value $\texttt{ctr} \in \{0,1\}^n$ . Generate the pseudorandom stream $y_i := F_k (\text{ctr} + i)$ where $\texttt{ctr}$ and $i$ are viewed as integers and addition is done modulo $2^n$ .
- For $i = 1$ to $l$ , set $c_i := y_i \oplus m_i$ .
- Output $\langle \texttt{ctr}, c_1, \ldots, c_l\rangle$ .
$Dec$ : Given inputs $\langle c_0, c_1, \ldots, c_l\rangle$ and $k \in \{0,1\}^n$ , compute $m_i := F_k (c_0 + i) \oplus c_i$ for $i = 1$ to $l$ . Output $\langle m_1, \dots, m_l \rangle$ .
Theorem. If $F$ is a pseudorandom function, then CTR mode is CPA-secure.

— Feb 14, 2023

Related: #Cryptography

§7 CPA Secure Encryption and Block Cipher Modes of Operation 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.

Made with ❤ at Earth.