\documentclass[aspectratio=169, lualatex, handout]{beamer}
\makeatletter\def\input@path{{theme/}}\makeatother\usetheme{cipher}

\title{Applied Cryptography}
\author{Nadim Kobeissi}
\institute{American University of Beirut}
\instituteimage{images/aub_white.png}
\date{\today}
\coversubtitle{CMPS 297AD/396AI\\Fall 2025}
\coverpartname{Part 1: Provable Security}
\covertopicname{1.4: Pseudorandomness}
\coverwebsite{https://appliedcryptography.page}

\begin{document}
\begin{frame}[plain]
	\titlepage
\end{frame}

\section{Pseudorandom Generators}

\begin{frame}{Limitations of One-Time Pad}
	\definitionbox{The Key Length Problem}{
		One-time pad is not a particularly useful encryption scheme in practice.
	}
	\begin{itemize}[<+->]
		\item The key must be as long as the plaintext!
		\item This creates a chicken-and-egg situation:
		      \begin{itemize}[<+->]
			      \item To privately send $n$ bits of information,
			      \item We must already privately share $n$ bits of information.
		      \end{itemize}
		\item Impractical for most real-world applications.
		      \begin{itemize}[<+->]
			      \item Clearly this is not what we're doing when we use HTTPS,
			      \item or WhatsApp, or pay for something via a debit card...
		      \end{itemize}
		\item We need encryption schemes where the key can be smaller than the message.
	\end{itemize}
\end{frame}

\begin{frame}{Idea: find a way to expand the key}
	\begin{itemize}[<+->]
		\item Given a key $k_s$ of size $\left|k_s\right| < \left|m\right|$, find a way to obtain $\left|k_e\right| \geq \left|m\right|$
		\item In the real world, we have two kinds of symmetric encryption schemes:
		      \begin{itemize}[<+->]
			      \item \textbf{Block ciphers}: AES, 3DES, etc.
			      \item \textbf{Stream ciphers}: ChaCha20, RC4, etc.
		      \end{itemize}
		\item This is exactly what stream ciphers do!
		      \begin{itemize}[<+->]
			      \item Start with a small key $k_s$ of a fixed size $\left|k_s\right| = \lambda$,
			      \item Magically expand it to $k_e$ where $\left|k_e\right| \geq \left|m\right|$,
			      \item $\func{enc}{K, M} = K \oplus M$
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Requirements for Key Expansion}
	\begin{itemize}[<+->]
		\item Our method would need to be \textbf{deterministic}, so that both the sender and receiver can expand their key in the same way (to encrypt/decrypt).
		\item Its output distribution would need to be \textbf{uniform}, since that is a crucial property for the security of OTP.
		\item Unfortunately, it's \textbf{not possible} to achieve both of these properties simultaneously.
		      \begin{itemize}[<+->]
			      \item Suppose the expansion method is a deterministic function $G: \bits^n \rightarrow \bits^{n+\ell}$
			      \item Its outputs are $\ell$ bits longer than its inputs!
			      \item There are $2^{n+\ell}$ strings of length $n+\ell$ but only (at most) $2^n$ possible outputs of $G$
			      \item So the outputs of $G$ can never induce a uniform distribution.
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Enter pseudorandomness}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item In cryptography, something is \textbf{pseudorandom} if it is indistinguishable from a uniform distribution.\footnote{The Oxford English Dictionary defines the prefix pseudo- as ``apparently but not really.''}
				\item We need to invent some \textbf{``secure pseudorandom generator'' (PRG)} $G$ that takes a \textbf{seed} $S$ and ends up being indistinguishable from a true uniform distribution when thrown into a library:
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\sslinked{
				\sslibrary{}{prg-real}{
					\sslibrarysubroutine{prg.sample}{}{
						$S \twoheadleftarrow \bits^\lambda$\\
						return $G(S)$
					}{1}
				}{1}
			}{\approxeq}{
				\sslibrary{}{prg-rand}{
					\sslibrarysubroutine{prg.sample}{}{
						$Y \twoheadleftarrow \bits^{\lambda+\ell}$\\
						return $Y$
					}{1}
				}{1}
			}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Enter pseudorandomness}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item In cryptography, something is \textbf{pseudorandom} if it is indistinguishable from a uniform distribution.\footnote{The Oxford English Dictionary defines the prefix pseudo- as ``apparently but not really.''}
				\item We need to invent some \textbf{``secure pseudorandom generator'' (PRG)} $G$ that takes a \textbf{seed} $S$ and ends up being indistinguishable from a true uniform distribution when thrown into a library:
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\imagewithcaption{prg_distributions.pdf}{Source: The Joy of Cryptography}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Enter pseudorandomness}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item We don't know how to make PRGs, or even if they exist.
				\item So we simply invent functions that we think act close enough to PRGs (when subjected to statistical and mathematical analysis).
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\sslinked{
				\sslibrary{}{prg-real}{
					\sslibrarysubroutine{prg.sample}{}{
						$S \twoheadleftarrow \bits^\lambda$\\
						return $G(S)$
					}{1}
				}{1}
			}{\approxeq}{
				\sslibrary{}{prg-rand}{
					\sslibrarysubroutine{prg.sample}{}{
						$Y \twoheadleftarrow \bits^{\lambda+\ell}$\\
						return $Y$
					}{1}
				}{1}
			}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{One-time secrecy of a SKE}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\definitionbox{One-time Secrecy for SKE}{
				An SKE scheme $\Sigma$ has one-time secrecy if the following libraries are interchangeable:
				\vspace{0.5mm}
				\begin{center}
					\sslinked{
						\sslibrary{\Sigma}{ots-real}{
							\sslibrarysubroutine{ots.enc}{M}{
								$K \twoheadleftarrow \Sigma.\mathcal{K}$ \\
								$C \coloneq \Sigma.\textsf{Enc}(K, M)$ \\
								return $C$
							}{1}
						}{0.8}
					}{\interchangeable{}}{
						\sslibrary{\Sigma}{ots-rand}{
							\sslibrarysubroutine{ots.enc}{M}{
								$C \twoheadleftarrow \Sigma.\mathcal{C}$ \\
								return $C$
							}{1}
						}{0.8}
					}
				\end{center}
			}
		\end{column}
		\begin{column}{0.5\textwidth}
			An encryption scheme has one-time secrecy if its ciphertexts are uniformly distributed, when keys are sampled uniformly, kept secret, and used for only one encryption, and no matter how the plaintexts are chosen.
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Does a PRG-based encryption scheme\\ have one-time secrecy?}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			If:
			\sslinked{
				\sslibrary{}{prg-real}{
					\sslibrarysubroutine{ots.enc}{}{
						$S \twoheadleftarrow \bits^\lambda$\\
						return $G(S)$
					}{1}
				}{1}
			}{\approxeq}{
				\sslibrary{}{prg-rand}{
					\sslibrarysubroutine{ots.enc}{}{
						$Y \twoheadleftarrow \bits^{\lambda+\ell}$\\
						return $Y$
					}{1}
				}{1}
			}
		\end{column}
		\begin{column}{0.5\textwidth}
			Then:
			\sslinked{
				\sslibrary{}{ots-real}{
					\sslibrarysubroutine{ots.enc}{M}{
						$K \twoheadleftarrow \bits^\lambda$ \\
						$Y \coloneq G(K)$ \\
						$C \coloneq Y \oplus M$ \\
						return $C$
					}{1}
				}{1}
			}{\approxeq}{
				\sslibrary{}{ots-rand}{
					\sslibrarysubroutine{ots.enc}{M}{
						$C \twoheadleftarrow \bits^{\lambda+\ell}$ \\
						return $C$
					}{1}
				}{1}
			}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Attacking PRGs}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item Assume that $G(S)$ is a secure PRG.
				\item Is \func{h}{S} secure?
			\end{itemize}
			\sssubroutine{H}{S}{
				$A \| B \coloneq G(S)$ \\
				$C \| D \coloneq G(B)$ \\
				return $A \| B \| C \| D$
			}{1}
		\end{column}
		\begin{column}{0.5\textwidth}
			\sslinked{
				\sslibrary{H}{prg-real}{
					\sslibrarysubroutine{ots.enc}{}{
						$S \twoheadleftarrow \bits^\lambda$ \\
						$A \| B \coloneq G(S)$ \\
						$C \| D \coloneq G(B)$ \\
						return $A \| B \| C \| D$
					}{1}
				}{1}
			}{\overset{?}{\approxeq}}{
				\sslibrary{H}{prg-rand}{
					\sslibrarysubroutine{ots.enc}{M}{
						$Y \twoheadleftarrow \bits^{4\lambda}$ \\
						return $Y$
					}{1}
				}{1}
			}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Attacking PRGs}
	\begin{columns}[c]
		\begin{column}{0.45\textwidth}
			\begin{itemize}[<+->]
				\item Assume that $G(S)$ is a secure PRG.
				\item Is \func{h}{S} secure?
				\item \textbf{No}:
				\item \prob{\prog{}\link\lib{H}{prg-real} \Rightarrow \texttt{true}} $ = 1$
			\end{itemize}
		\end{column}
		\begin{column}{0.55\textwidth}
			\begin{flushright}
				\sslinked{
					\ssprogram{}{
						$A \| B \| C \| D \coloneq \func{ots.enc}{}$ \\
						return $G(B) == C \| D$
					}{0.9}
				}{\link}{
					\sslibrary{H}{prg-real}{
						\sslibrarysubroutine{ots.enc}{}{
							$S \twoheadleftarrow \bits^\lambda$ \\
							$A \| B \coloneq G(S)$ \\
							$C \| D \coloneq G(B)$ \\
							return $A \| B \| C \| D$
						}{1}
					}{0.9}
				}
			\end{flushright}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Attacking PRGs}
	\begin{columns}[c]
		\begin{column}{0.45\textwidth}
			\begin{itemize}
				\item<1-3> Assume that $G(S)$ is a secure PRG.
				\item<1-3> Is \func{h}{S} secure?
				\item<1-3> \textbf{No}:
				\item<1-3> \prob{\prog{}\link\lib{H}{prg-real} \Rightarrow \texttt{true}} $ = 1$
				\item<2-3> \prob{\prog{}\link\lib{H}{prg-rand} \Rightarrow \texttt{true}} $ = \frac{1}{2^{2\lambda}}$
				\item<3> Difference certainly not negligible.
			\end{itemize}
		\end{column}
		\begin{column}{0.55\textwidth}
			\begin{flushright}
				\sslinked{
					\ssprogram{}{
						$A \| B \| C \| D \coloneq \func{ots.enc}{}$ \\
						return $G(B) == C \| D$
					}{0.9}
				}{\link}{
					\sslibrary{H}{prg-rand}{
						\sslibrarysubroutine{ots.enc}{M}{
							$Y \twoheadleftarrow \bits^{4\lambda}$ \\
							return $Y$
						}{1}
					}{0.9}
				}
			\end{flushright}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Example: RC4 (a stream cipher)}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item Used in WEP, SSL/TLS, and other protocols.
				\item Simple PRG that takes a seed and produces a keystream.
				\item Basic operation:
				      \begin{itemize}[<+->]
					      \item Initialize S-box with permutation of bytes 0-255.
					      \item Use key to scramble the S-box.
					      \item Generate pseudorandom bytes iteratively.
				      \end{itemize}
				\item Several weaknesses found over time:
				      \begin{itemize}[<+->]
					      \item Statistical biases in initial output.
					      \item Correlation between key and output bytes.
					      \item Considered cryptographically broken today.
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\alertbox{Security Warning}{
				RC4 is presented as a historical example only. It should not be used in new applications due to known weaknesses. Modern alternatives include ChaCha20.
			}
			\vspace{1em}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}[fragile]{RC4 PRG Algorithm}
	\begin{columns}[c]
		\begin{column}{0.55\textwidth}
			\begin{itemize}[<+->]
				\item RC4 generates a pseudorandom stream of bytes used to encrypt data.
				\item After key setup (which initializes array S), the algorithm produces keystream bytes:
				\item Each output byte requires simple operations:
				      \begin{itemize}[<+->]
					      \item Array index calculations.
					      \item Array value swapping.
					      \item Modular addition.
				      \end{itemize}
				\item Fast implementation in software.
				\item Despite simplicity, it has several cryptographic weaknesses.
			\end{itemize}
		\end{column}
		\begin{column}{0.45\textwidth}
			\imagewithcaption{rc4_prga_py.png}{RC4 PRG implementation in Python.}
		\end{column}
	\end{columns}
\end{frame}

\section{Pseudorandom Functions}

\begin{frame}{Pseudorandom function: definition}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\definitionbox{Pseudorandom Function (PRF)}{
				A function $F: \bits^\lambda \times \bits^n \rightarrow \bits^m$ is a secure pseudorandom function (PRF) if the following two libraries are indistinguishable:
			}
			\begin{itemize}
				\item $n$ the input length of the PRF.
				\item $m$ the output length of the PRF.
				\item $\lambda$ is the key size and hence the security parameter.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\sslinked{
				\sslibrary{F}{prf-real}{
					$K \twoheadleftarrow \bits^\lambda$\\[1em]
					\sslibrarysubroutine{prf.query}{X}{
						return $F(K, X)$
					}{1}
				}{1}
			}{\approxeq}{
				\sslibrary{F}{prf-rand}{
					$L \coloneq$ [\ ]\\[1em]
					\sslibrarysubroutine{prf.query}{X}{
						if $L[X]$ undefined:\\
						\quad $L[X] \twoheadleftarrow \bits^m$\\
						return $L[X]$
					}{1}
				}{1}
			}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{PRG vs PRF: Key Differences}
	\begin{columns}[t]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{PRG (Pseudorandom Generator)}:
				      \begin{itemize}[<+->]
					      \item Takes short seed, produces longer output
					      \item Generates entire output as a monolithic string
					      \item $G: \bits^\lambda \rightarrow \bits^{\lambda+\ell}$
				      \end{itemize}
			\end{itemize}
			\begin{center}
				\sslibrary{F}{prf-rand}{
					$L \coloneq$ [\ ]\\[1em]
					\sslibrarysubroutine{prf.query}{X}{
						if $L[X]$ undefined:\\
						\quad $L[X] \twoheadleftarrow \bits^m$\\
						return $L[X]$
					}{1}
				}{0.7}
			\end{center}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{PRF (Pseudorandom Function)}:
				      \begin{itemize}[<+->]
					      \item Maps inputs to pseudorandom outputs
					      \item Provides access to individual blocks of output
					      \item Can generate output for any input on demand
					      \item $F: \bits^\lambda \times \bits^n \rightarrow \bits^m$
				      \end{itemize}
				\item PRFs enable ``selective access'' to pseudorandom values without generating the entire sequence
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{$\mathsf{PRF}: F_{k}= X \rightarrow Y$}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{itemize}
				\item We want the mapping to be:
				      \begin{itemize}
					      \item One-way
					      \item ``Randomized''
					      \item Relations between inputs not reflected in outputs
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.8\textwidth}
			\begin{tikzpicture}[scale=0.38]
				% Define colors
				\definecolor{domaingreen}{RGB}{102, 170, 68}
				\definecolor{rangegreen}{RGB}{170, 187, 136}
				\definecolor{circlecolor}{RGB}{235, 137, 85}
				\definecolor{purplearrow}{RGB}{160, 78, 160}
				\definecolor{redarrow}{RGB}{237, 50, 36}

				% Input space (domain) X - made square
				\draw[dashed, thick, domaingreen, fill=domaingreen]
				(0,0) rectangle (8,8);
				\node[text width=6.5cm, align=center, font=\normalsize]
				at
				(4,-0.8)
				{Size: infinite!};
				\node[font=\small] at (4,9) {Input space (domain) $X$};

				% Output (range) Y - made square - moved more to the right
				\draw[thick, rangegreen, fill=rangegreen] (15,2) rectangle (20,7);
				\node[text width=4cm, align=center, font=\normalsize]
				at
				(17.5,1.2)
				{Size: fixed};
				\node[font=\small] at (17.5,8.5) {Output (range) $Y$};
				% Input dots - adjusted positions for square domain
				\filldraw[circlecolor] (2,7) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,7) -- (16.2,6.4);
				\pause
				\filldraw[circlecolor] (16.2,6.4) circle (0.3);
				\pause

				\filldraw[circlecolor] (3,6) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(3,6) -- (18.6,5.3);
				\pause
				\filldraw[circlecolor] (18.6,5.3) circle (0.3);
				\pause

				\filldraw[circlecolor] (2,5) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,5) -- (16.8,4.2);
				\pause
				\filldraw[circlecolor] (16.8,4.2) circle (0.3);
				\pause

				\filldraw[circlecolor] (4,3.5) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(4,3.5) -- (18.4,3.2);
				\pause
				\filldraw[circlecolor] (18.4,3.2) circle (0.3);
				\pause

				\filldraw[circlecolor] (2,2) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,2) -- (17.1,2.7);
				\pause
				\filldraw[circlecolor] (17.1,2.7) circle (0.3);
				\pause

				\filldraw[circlecolor] (3,1) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, ultra thick, redarrow]
				(3,1) -- (16.8,4.2);
				\node[redarrow, font=\scriptsize\bfseries, rotate=14]
				at
				(10,3)
				{Collisions are inevitable};
			\end{tikzpicture}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{PRFs in the real world: hash functions}
	\begin{columns}[c]
		\begin{column}{0.55\textwidth}
			\definitionbox{Hash Function Properties}{
				\begin{itemize}\item Takes input of \textbf{any size}
					\item Produces output of \textbf{fixed size}
					\item Is \textbf{deterministic} (same input $\rightarrow$ same output)
					\item Even a \textbf{tiny change} in input creates completely different output
					\item Is \textbf{efficient} to compute\end{itemize}
			}
		\end{column}
		\begin{column}{0.45\textwidth}
			\begin{tcolorbox}
				[colback=black!5!white,colframe=ciphergray] $\mathsf{SHA256}(\texttt{hello}) =$ \\ \texttt{2cf24dba5fb0a30e26e83b2ac5}\\ \texttt{b9e29e1b161e5c1fa7425e7304}\\
				\texttt{3362938b9824}

				$\mathsf{SHA256}(\texttt{hullo}) =$ \\ \texttt{7835066a1457504217688c8f5d}\\
				\texttt{06909c6591e0ca78c254ccf174}\\ \texttt{50d0d999cab0}
			\end{tcolorbox}
			\textcolor{cipherprimary}{\textbf{Note:} \small One character change $\rightarrow$
				completely different hash!}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Expected properties of a hash function}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}
				\item \textbf{Collision resistance}: computationally infeasible to find
				      two different inputs producing the same hash.
				\item \textbf{Preimage resistance}: given the output of a hash function,
				      it is computationally infeasible to reconstruct the original input.
				\item \textbf{Second preimage resistance}: given an input and an output,
				      it's computationally infeasible to find another different input
				      producing the same output.
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\imagewithcaption{sha2.png}{SHA-2 compression function. Source: Wikipedia}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Hash functions: what are they good for?}
	\begin{itemize}[<+->]
		\item \textbf{Password storage}: Store the hash of the password on the server,
		      not the password itself. Then check candidate passwords against the hash.
		\item \textbf{Data integrity verification}: Hash a file. Later hash it
		      again and compare hashes to check if the file has changed, suffered storage
		      degradation, etc.
		\item \textbf{Proof of work}: Server asks client to hash something a lot of
		      times before they can access some resource. Useful for anti-spam, Bitcoin
		      mining, etc.
	\end{itemize}
\end{frame}

\begin{frame}{An insecure PRF construction}
	\begin{columns}[c]
		\begin{column}{0.45\textwidth}
			\definitionbox{Claim: An Insecure PRF}{
				The function $F(K, X) = G(K) \oplus X$ is not a secure PRF, even if $G$ is a secure PRG.
			}
			\begin{itemize}[<+->]
				\item This construction fails because:
				      \begin{itemize}[<+->]
					      \item The key $K$ is only fed through the PRG once.
					      \item The same value $G(K)$ is used for all queries.
					      \item This creates exploitable patterns in outputs.
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.55\textwidth}
			\begin{center}
				\sslinked{
					\sslibrary{F}{prf-real}{
						$K \twoheadleftarrow \bits^\lambda$\\[1em]
						\sslibrarysubroutine{prf.query}{X}{
							return $G(K) \oplus X$
						}{1}
					}{1}
				}{\cancel{\approxeq}}{
					\sslibrary{F}{prf-rand}{
						$L \coloneq$ [\ ]\\[1em]
						\sslibrarysubroutine{prf.query}{X}{
							if $L[X]$ undefined:\\
							\quad $L[X] \twoheadleftarrow \bits^m$\\
							return $L[X]$
						}{1}
					}{1}
				}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{An insecure PRF construction}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item When an adversary sees two outputs:
				      \begin{align*}
					      Y_1 & = G(K) \oplus X_1 \\
					      Y_2 & = G(K) \oplus X_2
				      \end{align*}
				\item Taking $Y_1 \oplus Y_2$ causes $G(K)$ to cancel:
				      \begin{align*}
					      Y_1 \oplus Y_2 & = G(K) \oplus X_1 \oplus G(K) \oplus X_2 \\
					                     & = X_1 \oplus X_2
				      \end{align*}
				\item In a truly random function, $Y_1 \oplus Y_2 = X_1 \oplus X_2$ would be extremely unlikely!
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\begin{center}
				\sslinked{
					\sslibrary{F}{prf-real}{
						$K \twoheadleftarrow \bits^\lambda$\\[1em]
						\sslibrarysubroutine{prf.query}{X}{
							return $G(K) \oplus X$
						}{1}
					}{0.7}
				}{\cancel{\approxeq}}{
					\sslibrary{F}{prf-rand}{
						$L \coloneq$ [\ ]\\[1em]
						\sslibrarysubroutine{prf.query}{X}{
							if $L[X]$ undefined:\\
							\quad $L[X] \twoheadleftarrow \bits^m$\\
							return $L[X]$
						}{1}
					}{0.7}
				}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Another insecure PRF construction}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\definitionbox{Claim: Another Insecure PRF}{
				The function $H(K_1 \| K_2, X_1 \| X_2) = F(K_1, X_1) \oplus F(K_2, X_2)$ is not a secure PRF, even if $F$ is a secure PRF.
			}
			\begin{itemize}[<+->]
				\item An unsuccessful attempt to use a PRF with shorter input length to build one with a larger input length.
			\end{itemize}
		\end{column}
		\begin{column}{0.55\textwidth}
			\begin{center}
				\sslinked{
					\sslibrary{H}{prf-real}{
						$K_1 \| K_2 \twoheadleftarrow \bits^{2\lambda}$\\[1em]
						\sslibrarysubroutine{prf.query}{X_1 \| X_2}{
							return $F(K_1, X_1) \oplus F(K_2, X_2)$
						}{1}
					}{0.7}
				}{\cancel{\approxeq}}{
					\sslibrary{H}{prf-rand}{
						$L \coloneq$ [\ ]\\[1em]
						\sslibrarysubroutine{prf.query}{X_1 \| X_2}{
							if $L[X_1 \| X_2]$ undefined:\\
							\quad $L[X_1 \| X_2] \twoheadleftarrow \bits^m$\\
							return $L[X_1 \| X_2]$
						}{1}
					}{0.7}
				}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Why the previous PRF is broken}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item When inputs share the same first half, the corresponding outputs of $H$ have a common term $F(K_1, X_1)$
				\item Consider querying four inputs: $A\|B$, $A\|B'$, $A'\|B$, $A'\|B'$ (where $A \neq A'$ and $B \neq B'$)
				      \begin{align*}
					      Y_1 & = F(K_1, A) \oplus F(K_2, B)   \\
					      Y_2 & = F(K_1, A) \oplus F(K_2, B')  \\
					      Y_3 & = F(K_1, A') \oplus F(K_2, B)  \\
					      Y_4 & = F(K_1, A') \oplus F(K_2, B')
				      \end{align*}
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item If we XOR $Y_1 \oplus Y_2$, the $F(K_1, A)$ terms cancel out.
				\item Similarly, $Y_3 \oplus Y_4$ causes $F(K_1, A')$ to cancel:
				      \begin{itemize}
					      \item $Y_1 \oplus Y_2 = F(K_2, B) \oplus F(K_2, B')$
					      \item $Y_3 \oplus Y_4 = F(K_2, B) \oplus F(K_2, B')$
				      \end{itemize}
				\item So $\prob{Y_1 \oplus Y_2 == Y_3 \oplus Y_4} = 1$
				\item With a truly random function, $\prob{Y_1 \oplus Y_2 == Y_3 \oplus Y_4} = \frac{1}{2^m}$ (extremely unlikely!)
				\item Also, Given $Y_{1\cdots3}$, we can predict $Y_4$!
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{The Golden Rule of PRFs}
	\definitionbox{The Golden Rule of PRFs}{
		If a PRF $F$ is being used as a component in a larger construction $H$, then security usually rests on how well $H$ can ensure distinct inputs to $F$.
	}
	\begin{itemize}[<+->]
		\item When analyzing PRF security, focus on input uniqueness.
		\item Repeated inputs to a PRF create exploitable patterns.
		\item Even if $F$ is secure, $H$ can be broken if it causes $F$ to receive duplicate inputs.
		\item Don't try to directly distinguish $F$'s outputs from uniform.
		\item Instead, exploit how $H$ uses $F$ incorrectly.
		\item Find input patterns that force collisions within $F$.
	\end{itemize}
\end{frame}

\section{Pseudorandom Permutations}

\begin{frame}{What is a permutation?}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\definitionbox{Permutation}{
				A permutation is a rearrangement where each input value maps to exactly one output value, and each possible output appears exactly once.
			}
			\begin{itemize}[<+->]
				\item Permutations rearrange elements rather than transforming them.
				\item Every element in the domain appears exactly once in the range.
				\item The function is invertible.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{Example}: simple substitution cipher. Each letter maps to another letter:
				      \begin{align*}
					      a & \mapsto g,\quad b \mapsto a,\quad c \mapsto r \\
					      d & \mapsto b,\quad e \mapsto l,\quad \ldots
				      \end{align*}
				\item Under this permutation:
				      \begin{itemize}
					      \item ``cabbage'' $\mapsto$ ``rgaagdl''
					      \item ``rgaagdl'' $\mapsto$ ``cabbage''
				      \end{itemize}
				\item This mapping is reversible because it's a permutation over $\{a,\ldots,z\}$.
				\item Each letter appears exactly once in the output alphabet.
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{PRF versus PRP}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\textbf{Pseudo-Random Function (SHA-2)}
			\begin{itemize}[<+->]
				\item \textbf{Input} is arbitrary-length,
				\item \textbf{Output} is fixed-length, looks random (as discussed
				      earlier).
				\item Indistinguishable from a truly random function by an adversary with
				      limited computational power.
			\end{itemize}
		\end{column}

		\begin{column}{0.5\textwidth}
			\textbf{Pseudo-Random Permutation (AES)}
			\begin{itemize}[<+->]
				\item \textbf{Input and output} are the same length, forming a permutation.
				\item Each input maps uniquely to one output, allowing invertibility.
				\item Indistinguishable from a truly random permutation by an adversary
				      with limited computational power.
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{PRPs compared to PRFs}
	\begin{itemize}[<+->]
		\item \textbf{Invertibility}: PRPs can be efficiently inverted given the key
		      \begin{itemize}[<+->]
			      \item Enable both encryption and decryption
			      \item Can recover input from output (and vice versa)
		      \end{itemize}
		\item \textbf{No range collision}: Each input maps to a unique output
		      \begin{itemize}[<+->]
			      \item Provides perfect input recovery
			      \item Reduces vulnerability to collision-based attacks, birthday attacks, and certain forms of differential cryptanalysis
		      \end{itemize}
		\item \textbf{Versatility}: A secure PRP can be used as a PRF
		      \begin{itemize}[<+->]
			      \item ``Downgrade'' trivially by ignoring inverse capability
			      \item The reverse is not true (PRF → PRP conversion is complex)
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{$\mathsf{PRF}: F_{k}= X \rightarrow Y$}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{itemize}
				\item We want the mapping to be:
				      \begin{itemize}
					      \item One-way
					      \item ``Randomized''
					      \item Relations between inputs not reflected in outputs
				      \end{itemize}
			\end{itemize}
		\end{column}

		\begin{column}{0.8\textwidth}
			\begin{tikzpicture}[scale=0.38]
				% Define colors
				\definecolor{domaingreen}{RGB}{102, 170, 68}
				\definecolor{rangegreen}{RGB}{170, 187, 136}
				\definecolor{circlecolor}{RGB}{235, 137, 85}
				\definecolor{purplearrow}{RGB}{160, 78, 160}
				\definecolor{redarrow}{RGB}{237, 50, 36}

				% Input space (domain) X - made square
				\draw[dashed, thick, domaingreen, fill=domaingreen]
				(0,0) rectangle (8,8);
				\node[text width=6.5cm, align=center, font=\normalsize]
				at
				(4,-0.8)
				{Size: infinite!};
				\node[font=\small] at (4,9) {Input space (domain) $X$};

				% Output (range) Y - made square - moved more to the right
				\draw[thick, rangegreen, fill=rangegreen] (15,2) rectangle (20,7);
				\node[text width=4cm, align=center, font=\normalsize]
				at
				(17.5,1.2)
				{Size: fixed};
				\node[font=\small] at (17.5,8.5) {Output (range) $Y$};
				% Input dots - adjusted positions for square domain
				\filldraw[circlecolor] (2,7) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,7) -- (16.2,6.4);
				\pause
				\filldraw[circlecolor] (16.2,6.4) circle (0.3);
				\pause

				\filldraw[circlecolor] (3,6) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(3,6) -- (18.6,5.3);
				\pause
				\filldraw[circlecolor] (18.6,5.3) circle (0.3);
				\pause

				\filldraw[circlecolor] (2,5) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,5) -- (16.8,4.2);
				\pause
				\filldraw[circlecolor] (16.8,4.2) circle (0.3);
				\pause

				\filldraw[circlecolor] (4,3.5) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(4,3.5) -- (18.4,3.2);
				\pause
				\filldraw[circlecolor] (18.4,3.2) circle (0.3);
				\pause

				\filldraw[circlecolor] (2,2) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,2) -- (17.1,2.7);
				\pause
				\filldraw[circlecolor] (17.1,2.7) circle (0.3);
				\pause

				\filldraw[circlecolor] (3,1) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, ultra thick, redarrow]
				(3,1) -- (16.8,4.2);
				\node[redarrow, font=\scriptsize\bfseries, rotate=14]
				at
				(10,3)
				{Collisions are inevitable};
			\end{tikzpicture}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{$\mathsf{PRP}: F_{k}= X \rightarrow X$}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{itemize}
				\item \textbf{Bijective} (two-way)
				      \begin{itemize}
					      \item \textbf{Injective}: no two inputs map to same output (no
					            collisions)
					      \item \textbf{Surjective}: Every output has one corresponding input
				      \end{itemize}
				\item ``Randomized''
				\item Relations between inputs not reflected in outputs
			\end{itemize}
		\end{column}

		\begin{column}{0.8\textwidth}
			\begin{tikzpicture}[scale=0.38]
				% Define colors
				\definecolor{domaingreen}{RGB}{102, 170, 68}
				\definecolor{rangegreen}{RGB}{102, 170, 68}
				\definecolor{circlecolor}{RGB}{235, 137, 85}
				\definecolor{purplearrow}{RGB}{160, 78, 160}

				% Input space (domain) X - made square
				\draw[dashed, thick, domaingreen, fill=domaingreen]
				(0,0) rectangle (8,8);
				\node[text width=6.5cm, align=center, font=\normalsize]
				at
				(4,-0.8)
				{Size: fixed};
				\node[font=\normalsize] at (4,9) {Input space (domain) $X$};

				% Output (range) Y - made square, same size as domain, moved left
				\draw[thick, rangegreen, fill=rangegreen] (12,0) rectangle (20,8);
				\node[text width=6.5cm, align=center, font=\normalsize]
				at
				(16,-0.8)
				{Size: fixed};
				\node[font=\normalsize] at (16,9) {Output (range) $X$};
				% Input dots - adjusted positions for square domain
				\filldraw[circlecolor] (2,7) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,7) -- (14.2,7.4);
				\pause
				\filldraw[circlecolor] (14.2,7.4) circle (0.3);
				\pause

				\filldraw[circlecolor] (3,6) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(3,6) -- (18.6,5.3);
				\pause
				\filldraw[circlecolor] (18.6,5.3) circle (0.3);
				\pause

				\filldraw[circlecolor] (2,5) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,5) -- (13.8,4.2);
				\pause
				\filldraw[circlecolor] (13.8,4.2) circle (0.3);
				\pause

				\filldraw[circlecolor] (4,3.5) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(4,3.5) -- (17.4,2.2);
				\pause
				\filldraw[circlecolor] (17.4,2.2) circle (0.3);
				\pause

				\filldraw[circlecolor] (2,2) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(2,2) -- (16.1,6.7);
				\pause
				\filldraw[circlecolor] (16.1,6.7) circle (0.3);
				\pause

				\filldraw[circlecolor] (3,1) circle (0.3);
				\pause
				\draw[-{Stealth[length=6mm, width=4mm]}, thick, purplearrow]
				(3,1) -- (19.0,1.4);
				\pause
				\filldraw[circlecolor] (19.0,1.4) circle (0.3);
			\end{tikzpicture}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{``Lazy dictionaries'' versus ``lazy permutations''}{Ideal PRF versus ideal PRP}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sslibrary{F}{prf-rand}{
					$L \coloneq$ [\ ]\\[1em]
					\sslibrarysubroutine{prf.query}{X}{
						if $L[X]$ undefined:\\
						\quad $L[X] \twoheadleftarrow \bits^m$\\
						return $L[X]$
					}{1}
				}{1}
			\end{center}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sslibrary{F}{prp-rand}{
					$L \coloneq$ [\ ]\\[1em]
					\sslibrarysubroutine{prp.query}{X}{
						if $L[X]$ undefined:\\
						\quad $Y \twoheadleftarrow \bits^n \ \setminus \ \mathcal{y}$\\
						\quad $\mathcal{y} \coloneq \mathcal{y} \cup \{Y\}$\\
						\quad $L[X] \coloneq Y$\\
						return $L[X]$
					}{1}
				}{1}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{``Lazy dictionaries'' versus ``lazy permutations''}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item While the PRF (on the left) just picks random outputs for each input...
				\item The PRP (on the right) must ensure outputs are never repeated:
				      \begin{itemize}[<+->]
					      \item $\mathcal{y}$ tracks all outputs used so far
					      \item $\setminus$ means ``set difference'' - pick from values not in $\mathcal{y}$
					      \item $\cup$ means ``set union'' - add the new value to $\mathcal{y}$
				      \end{itemize}
				\item This ensures each output appears exactly once - the definition of a permutation
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sslibrary{F}{prp-rand}{
					$L \coloneq$ [\ ]\\[1em]
					\sslibrarysubroutine{prp.query}{X}{
						if $L[X]$ undefined:\\
						\quad $Y \twoheadleftarrow \bits^n \ \setminus \ \mathcal{y}$\\
						\quad $\mathcal{y} \coloneq \mathcal{y} \cup \{Y\}$\\
						\quad $L[X] \coloneq Y$\\
						return $L[X]$
					}{1}
				}{1}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Pseudorandom function: definition}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\definitionbox{Pseudorandom Function (PRF)}{
				A function $F: \bits^\lambda \times \bits^n \rightarrow \bits^m$ is a secure pseudorandom function (PRF) if the following two libraries are indistinguishable:
			}
			\begin{itemize}
				\item $n$ the input length of the PRF.
				\item $m$ the output length of the PRF.
				\item $\lambda$ is the key size and hence the security parameter.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\sslinked{
				\sslibrary{F}{prf-real}{
					$K \twoheadleftarrow \bits^\lambda$\\[1em]
					\sslibrarysubroutine{prf.query}{X}{
						return $F(K, X)$
					}{1}
				}{1}
			}{\approxeq}{
				\sslibrary{F}{prf-rand}{
					$L \coloneq$ [\ ]\\[1em]
					\sslibrarysubroutine{prf.query}{X}{
						if $L[X]$ undefined:\\
						\quad $L[X] \twoheadleftarrow \bits^m$\\
						return $L[X]$
					}{1}
				}{1}
			}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Pseudorandom permutation: definition}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\definitionbox{Pseudorandom Permutation (PRP)}{
				A keyed permutation $F^{\pm}$ is a secure pseudorandom permutation (PRP) if the following two libraries are indistinguishable:
			}
			\begin{itemize}[<+->]
				\item $n$ the input length of the PRP. Also the output length!
				\item $\lambda$ is the key size and hence the security parameter.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\sslinked{
				\sslibrary{F}{prp-real}{
					$K \twoheadleftarrow \bits^\lambda$\\[1em]
					\sslibrarysubroutine{prp.query}{X}{
						return $F(K, X)$
					}{1}
				}{1}
			}{\approxeq}{
				\sslibrary{F}{prp-rand}{
					$L \coloneq$ [\ ]\\[1em]
					\sslibrarysubroutine{prp.query}{X}{
						if $L[X]$ undefined:\\
						\quad $Y \twoheadleftarrow \bits^n \ \setminus \ \mathcal{y}$\\
						\quad $\mathcal{y} \coloneq \mathcal{y} \cup \{Y\}$\\
						\quad $L[X] \coloneq Y$\\
						return $L[X]$
					}{1}
				}{1}
			}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Pseudorandom permutation: definition}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\definitionbox{Pseudorandom Permutation (PRP)}{
				A keyed permutation $F^{\pm}$ is a secure pseudorandom permutation (PRP) if the following two libraries are indistinguishable:
			}
			\begin{itemize}[<+->]
				\item We obviously can't use \lib{F}{prp-rand} in the real world.
				\item It doesn't scale. So we need practical approximative alternatives.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\sslinked{
				\sslibrary{F}{prp-real}{
					$K \twoheadleftarrow \bits^\lambda$\\[1em]
					\sslibrarysubroutine{prp.query}{X}{
						return $F(K, X)$
					}{1}
				}{1}
			}{\approxeq}{
				\sslibrary{F}{prp-rand}{
					$L \coloneq$ [\ ]\\[1em]
					\sslibrarysubroutine{prp.query}{X}{
						if $L[X]$ undefined:\\
						\quad $Y \twoheadleftarrow \bits^n \ \setminus \ \mathcal{y}$\\
						\quad $\mathcal{y} \coloneq \mathcal{y} \cup \{Y\}$\\
						\quad $L[X] \coloneq Y$\\
						return $L[X]$
					}{1}
				}{1}
			}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Building a permutation through Feistel ciphers}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item An $r$-round \textbf{Feistel cipher} with \textbf{round functions} $F_1,\ldots,F_r$ is defined as follows:\\
				      \begin{center}
					      \sssubroutine{$\mathbb{F}$}{X_{0}\|X_{1}}{
					      for $i = 1$ to $r$:\\
					      \quad $X_{i+1} \coloneq X_{i-1} \oplus F_{i}(X_{i})$\\
					      return $X_{r}\|X_{r+1}$
					      }{1}
				      \end{center}
				\item A Feistel cipher is always a permutation on $\bits^{2n}$, regardless of its round functions.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\imagewithcaption{feistel_cipher.pdf}{Feistel cipher.\\Source: The Joy of Cryptography}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Building a permutation through Feistel ciphers}
	\definitionbox{Feistel Ciphers Are Permutations}{
		A Feistel cipher is always a permutation on $\bits^{2n}$, regardless of its round functions.
	}
	\begin{itemize}[<+->]
		\item \textbf{Proof:} Each round of a Feistel cipher computes the next block as:
		      \begin{itemize}[<+->]
			      \item $X_{i+1} = X_{i-1} \oplus F_{i}(X_{i})$
		      \end{itemize}
		\item To invert this round, we can rearrange the equation to solve for $X_{i-1}$ in terms of $X_{i}$ and $X_{i+1}$:
		      \begin{itemize}[<+->]
			      \item $X_{i-1} = X_{i+1} \oplus F_{i}(X_{i})$
		      \end{itemize}
		\item $F_i$ itself does not need to have an inverse - both the forward and inverse direction of the Feistel cipher evaluate $F_i$ in the forward direction! $\qed$
	\end{itemize}
\end{frame}

\begin{frame}{Building a permutation through Feistel ciphers}{Inversion}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item $\mathbb{F}^{-1}$ is the \textbf{inversion}, allowing Feistel ciphers to function as PRPs:
				      \begin{center}
					      \sssubroutine{$\mathbb{F}^{-1}$}{X_{r}\|X_{r+1}}{
					      for $i = r$ \hl{down to} $1$:\\
					      \quad $X_{i-1} \coloneq X_{i+1} \oplus F_{i}(X_{i})$\\
					      return $X_{0}\|X_{1}$
					      }{1}
				      \end{center}
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\imagewithcaption{feistel_cipher_inv.pdf}{Feistel cipher inversion.\\Source: The Joy of Cryptography}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Forward and backward on one slide}{Just in case it's helpful}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sssubroutine{$\mathbb{F}$}{X_{0}\|X_{1}}{
				for $i = 1$ to $r$:\\
				\quad $X_{i+1} \coloneq X_{i-1} \oplus F_{i}(X_{i})$\\
				return $X_{r}\|X_{r+1}$
				}{1.2}
			\end{center}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sssubroutine{$\mathbb{F}^{-1}$}{X_{r}\|X_{r+1}}{
				for $i = r$ down to $1$:\\
				\quad $X_{i-1} \coloneq X_{i+1} \oplus F_{i}(X_{i})$\\
				return $X_{0}\|X_{1}$
				}{1.2}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Keyed Feistel ciphers}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item Let's add a key in there. Wow, encryption!
				\item $K_{1\cdots i}$ called is the \textbf{key schedule}.
				\item If each round function $F_i$ uses a distinct key $K_i$, it increases the security of the Feistel network against certain attacks.
				\item By using a PRF as round function $F_i$, the security of the Feistel cipher would be grounded on the PRF's security basis.
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\begin{center}
				\sssubroutine{$\mathbb{F}$}{K_1\|\cdots\|K_r,\ X_0\|X_1}{
				for $i = 1$ to $r$:\\
				\quad $X_{i+1} \coloneq X_{i-1} \oplus F_{i}(K_{i}, X_{i})$\\
				return $X_{r}\|X_{r+1}$
				}{1}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Meet-in-the-middle attacks on Feistel ciphers}{Why use a key schedule and not the same key?}
	\begin{columns}[c]
		\begin{column}{0.65\textwidth}
			\begin{itemize}[<+->]
				\item Using the \textbf{same key} for all rounds creates significant vulnerabilities.
				\item A meet-in-the-middle attack can break an $r$-round Feistel cipher with complexity $> \frac{2^{|K|}}{2}$.
				\item The attack works by computing partial encryptions from both ends:
				      \begin{enumerate}[<+->]
					      \item Forward: Compute halfway through encryption.
					      \item Backward: Compute halfway through decryption.
					      \item Look for ``meeting points'' in the middle.
				      \end{enumerate}
				\item With identical round functions, effective security may be only \textbf{half} the number of rounds.
			\end{itemize}
		\end{column}
		\begin{column}{0.35\textwidth}
			\begin{center}
				\sssubroutine{$\mathbb{F}$}{K,\ X_0\|X_1}{
				for $i = 1$ to $r$:\\
				\quad $X_{i+1} \coloneq X_{i-1} \oplus F(K, X_{i})$\\
				return $X_{r}\|X_{r+1}$
				}{1}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Breaking a 2-round Feistel cipher}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{A 2-round Feistel cipher cannot be a secure PRP.}
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sssubroutine{$\mathbb{F}$}{K_1\|K_2,\ X_0\|X_1}{
				$X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
				$X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
				return $X_{2}\|X_{3}$
				}{1}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Breaking a 2-round Feistel cipher}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{itemize}[<+->]
				\item Once again, real or random?
				\item We can indeed produce an adversary \prog{} that can distinguish between these two libraries.
			\end{itemize}
		\end{column}
		\begin{column}{0.6\textwidth}
			\begin{center}
				\sslinked{
				\sslibrary{\mathbb{F}}{prp-real}{
				$K_1\|K_2 \twoheadleftarrow \bits^{2\lambda}$\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				$X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
				$X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
				return $X_{2}\|X_{3}$
				}{1}
				}{0.8}
				}{\cancel{\approxeq}}{
				\sslibrary{\mathbb{F}}{prp-rand}{
				$L \coloneq$ [\ ]\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X}{
				if $L[X]$ undefined:\\
				\quad $Y \twoheadleftarrow \bits^n \ \setminus \ \mathcal{y}$\\
				\quad $\mathcal{y} \coloneq \mathcal{y} \cup \{Y\}$\\
				\quad $L[X] \coloneq Y$\\
				return $L[X]$
				}{1}
				}{0.8}
				}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Breaking a 2-round Feistel cipher}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{itemize}[<+->]
				\item Let's query $(A \| B)$ and $(A' \| B)$ where $A \neq A'$
				      \begin{itemize}
					      \item $Y_1 \| Y_2 = \func{prp.query}{A \| B}$
					      \item $Y_1' \| Y_2' = \func{prp.query}{A' \| B}$
				      \end{itemize}
				\item In a 2-round Feistel cipher:
				      \begin{itemize}
					      \item $Y_1 = A \oplus F(K_1, B)$
					      \item $Y_1' = A' \oplus F(K_1, B)$
					      \item $Y_1 \oplus Y_1' = A \oplus A'$
				      \end{itemize}
				\item In a true PRP, \prob{Y_1 \oplus Y_1' == A \oplus A'} is negligible
			\end{itemize}
		\end{column}
		\begin{column}{0.6\textwidth}
			\begin{center}
				\sslinked{
				\ssprogram{}{
				$Y_1\|Y_2 = \func{prp.query}{A\|B}$\\
				$Y^{'}_1\|Y^{'}_2 = \func{prp.query}{A^{'}\|B}$\\
				return $Y_1 \oplus Y^{'}_1 == A \oplus A^{'}$
				}{0.8}
				}{\link}{
				\sslibrary{\mathbb{F}}{prp-real}{
				$K_1\|K_2 \twoheadleftarrow \bits^{2\lambda}$\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				$X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
				$X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
				return $X_{2}\|X_{3}$
				}{1}
				}{0.8}
				}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{However, a 3+ round Feistel cipher is fine!}
	\begin{center}
		\sslinked{
		\sslinked{
		\ssprogram{}{
		$Y_1\|Y_2 = \func{prp.query}{A\|B}$\\
		$Y^{'}_1\|Y^{'}_2 = \func{prp.query}{A^{'}\|B}$\\
		return $Y_1 \oplus Y^{'}_1 == A \oplus A^{'}$
		}{0.7}
		}{\link}{
		\sslibrary{\mathbb{F}}{prp-real}{
		$K_1\|K_2 \twoheadleftarrow \bits^{2\lambda}$\\[1em]
		\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
		$X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
		$X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
		return $X_{2}\|X_{3}$
		}{1}
		}{0.7}
		}
		}{\cancel{\approxeq}}{
		\sslinked{
		\ssprogram{}{
		$Y_1\|Y_2 = \func{prp.query}{A\|B}$\\
		$Y^{'}_1\|Y^{'}_2 = \func{prp.query}{A^{'}\|B}$\\
		return $Y_1 \oplus Y^{'}_1 == A \oplus A^{'}$
		}{0.7}
		}{\link}{
		\sslibrary{\mathbb{F}}{prp-real}{
		$K_1\|K_2\|K_3 \twoheadleftarrow \bits^{3\lambda}$\\[1em]
		\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
		$X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
		$X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
		$X_{4} \coloneq X_{2} \oplus F(K_3, X_3)$\\
		return $X_{3}\|X_{4}$
		}{1}
		}{0.7}
		}
		}
	\end{center}
\end{frame}

\begin{frame}{However, a 3+ round Feistel cipher is fine!}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{itemize}[<+->]
				\item Luby and Rackoff proved that a 3-round Feistel cipher is indistinguishable from a pseudorandom permutation.\footnote{\url{https://appliedcryptography.page/papers/\#luby-rackoff}}
				\item Can we also prove it using our provable security framework?
			\end{itemize}
		\end{column}
		\begin{column}{0.6\textwidth}
			\begin{center}
				\sslinked{
				\sslibrary{\mathbb{F}}{prp-real}{
				$K_1\|K_2\|K_3 \twoheadleftarrow \bits^{3\lambda}$\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				$X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
				$X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
				$X_{4} \coloneq X_{2} \oplus F(K_3, X_3)$\\
				return $X_{3}\|X_{4}$
				}{1}
				}{0.8}
				}{\approxeq}{
				\sslibrary{\mathbb{F}}{prp-rand}{
				$L \coloneq$ [\ ]\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X}{
				if $L[X]$ undefined:\\
				\quad $Y \twoheadleftarrow \bits^n \ \setminus \ \mathcal{y}$\\
				\quad $\mathcal{y} \coloneq \mathcal{y} \cup \{Y\}$\\
				\quad $L[X] \coloneq Y$\\
				return $L[X]$
				}{1}
				}{0.8}
				}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{The ``bad event'' proof technique}{Reminder}
	\definitionbox{Bad Event Technique}{
		Let \lib{}{1} and \lib{}{2} be libraries that each include a boolean variable named \hl{\texttt{bad}}, and assume that after \texttt{bad} is set to \texttt{true} it remains \texttt{true} forever. We say that the bad event is triggered if the library ever sets \texttt{bad := true}.
		\\[1em]
		If \lib{}{1} and \lib{}{2} have identical source code, except for statements reachable only when \texttt{bad := true}, then:
		\begin{align*}
			\left| \prob{\prog{} \link \lib{}{1} \Rightarrow \texttt{true}} - \prob{\prog{} \link \lib{}{2} \Rightarrow \texttt{true}} \right| \leq \prob{\prog{} \link \lib{}{1} \func{trigger}{\texttt{bad}}}
		\end{align*}
	}
\end{frame}

\begin{frame}{The ``bad event'' proof technique}{Reminder}
	\begin{itemize}[<+->]
		\item \prog{}'s advantage is bounded by \prob{\prog{} \link \lib{}{1} \func{trigger}{\texttt{bad}}}.
		\item Practical application:
		      \begin{itemize}[<+->]
			      \item Define a sequence of hybrid libraries.
			      \item Identify ``bad events'' between consecutive hybrids.
			      \item Show these events occur with negligible probability.
		      \end{itemize}
		\item Enables us to focus on analyzing specific failure cases rather than full behavior.
	\end{itemize}
\end{frame}

\begin{frame}{The ``end-of-time'' strategy for bad events}{Reminder}
	\begin{itemize}[<+->]
		\item Sometimes analyzing bad events can be complex, especially when values are chosen by the adversary.
		\item The end-of-time strategy:
		      \begin{enumerate}[<+->]
			      \item Postpone all bad-event logic to the end of the library execution.
			      \item Collect information during normal execution.
			      \item Check for bad events only at the very end.
		      \end{enumerate}
		\item Advantages:
		      \begin{itemize}[<+->]
			      \item Simplifies analysis by separating normal behavior from bad-event checking.
			      \item Makes it easier to bound the probability of bad events.
			      \item Particularly useful for complex cryptographic proofs.
		      \end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{However, a 3+ round Feistel cipher is fine!}
	\begin{columns}[c]
		\begin{column}{0.4\textwidth}
			\begin{itemize}
				\item Luby and Rackoff proved that a 3-round Feistel cipher is indistinguishable from a pseudorandom permutation.\footnote{\url{https://appliedcryptography.page/papers/\#luby-rackoff}}
				\item Can we also prove it using our provable security framework?
				\item Yes, with the bad events proof technique!
			\end{itemize}
		\end{column}
		\begin{column}{0.6\textwidth}
			\begin{center}
				\sslinked{
				\sslibrary{\mathbb{F}}{prp-real}{
				$K_1\|K_2\|K_3 \twoheadleftarrow \bits^{3\lambda}$\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				$X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
				$X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
				$X_{4} \coloneq X_{2} \oplus F(K_3, X_3)$\\
				return $X_{3}\|X_{4}$
				}{1}
				}{0.8}
				}{\approxeq}{
				\sslibrary{\mathbb{F}}{prp-rand}{
				$L \coloneq$ [\ ]\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X}{
				if $L[X]$ undefined:\\
				\quad $Y \twoheadleftarrow \bits^n \ \setminus \ \mathcal{y}$\\
				\quad $\mathcal{y} \coloneq \mathcal{y} \cup \{Y\}$\\
				\quad $L[X] \coloneq Y$\\
				return $L[X]$
				}{1}
				}{0.8}
				}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 1}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}
				\item We start at \lib{\mathbb{F}}{prp-real}.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				$K_1\|K_2\|K_3 \twoheadleftarrow \bits^{3\lambda}$\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				$X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
				$X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
				$X_{4} \coloneq X_{2} \oplus F(K_3, X_3)$\\
				return $X_{3}\|X_{4}$
				}{1}
				}{0.8}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 2}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}
				\item We add a cache $L[\cdot]$ so that each distinct output is computed only once.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				$K_1\|K_2\|K_3 \twoheadleftarrow \bits^{3\lambda}$\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				\hl{if $L[X_0\|X_1]$ undefined:}\\
				\quad $X_{2} \coloneq X_{0} \oplus F(K_1, X_1)$\\
				\quad $X_{3} \coloneq X_{1} \oplus F(K_2, X_2)$\\
				\quad $X_{4} \coloneq X_{2} \oplus F(K_3, X_3)$\\
				\quad \hl{$L[X_0\|X_1] \coloneq X_3\|X_4$}\\
				return \hl{$L[X_0\|X_1]$}
				}{1}
				}{0.8}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 3}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item We add additional sub-cache $L_i[\cdot]$ for each $F(K_i,\cdot)$
				\item Since we already assume $F$ to be a secure PRF, we can replace it with the ideal PRF and remove $K$.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad \hl{if $L_1[X_1]$ undefined:}\\
				\quad \quad \hl{$L_1[X_1] \twoheadleftarrow \bits^\lambda$}\\
				\quad $X_{2} \coloneq X_{0} \oplus \hl{L_1[X_1]}$\\
				\quad \hl{if $L_2[X_2]$ undefined:}\\
				\quad \quad \hl{$L_2[X_2] \twoheadleftarrow \bits^\lambda$}\\
				\quad $X_{3} \coloneq X_{1} \oplus \hl{L_2[X_2]}$\\
				\quad \hl{if $L_3[X_3]$ undefined:}\\
				\quad \quad \hl{$L_3[X_3] \twoheadleftarrow \bits^\lambda$}\\
				\quad $X_{4} \coloneq X_{2} \oplus \hl{L_3[X_3]}$\\
				\quad $L[X_0\|X_1] \coloneq X_3\|X_4$\\
				return $L[X_0\|X_1]$
				}{1}
				}{0.8}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 4}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item We expect $X_2$ and $X_3$ to never repeat. So, we can trigger the bad event if they do.
				\item Later, we must show that the bad event's probability is negligible.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad if $L_1[X_1]$ undefined:\\
				\quad \quad $L_1[X_1] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{2} \coloneq X_{0} \oplus L_1[X_1]$\\
				\quad if $L_2[X_2]$ \hl{defined: $\texttt{bad} \coloneq \texttt{true}$}\\
				\quad $L_2[X_2] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{3} \coloneq X_{1} \oplus L_2[X_2]$\\
				\quad if $L_3[X_3]$ \hl{defined: $\texttt{bad} \coloneq \texttt{true}$}\\
				\quad $L_3[X_3] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{4} \coloneq X_{2} \oplus L_3[X_3]$\\
				\quad $L[X_0\|X_1] \coloneq X_3\|X_4$\\
				return $L[X_0\|X_1]$
				}{1}
				}{0.8}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 5}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item Instead of sampling $L_2[X_2]$ uniformly and then computing $X_3$, we can sample $X_3$ uniformly and compute $L_2[X_2]$.
				\item Same for $L_3[X_3]$ and $X_4$.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad if $L_1[X_1]$ undefined:\\
				\quad \quad $L_1[X_1] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{2} \coloneq X_{0} \oplus L_1[X_1]$\\
				\quad if $L_2[X_2]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad \hl{$X_3 \twoheadleftarrow \bits^\lambda$}\\
				\quad $L_2[X_2] \hl{\coloneq X_3 \oplus X_1}$\\
				\quad if $L_3[X_3]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad \hl{$X_4 \twoheadleftarrow \bits^\lambda$}\\
				\quad $L_3[X_3] \hl{\coloneq X_4 \oplus X_2}$\\
				\quad $L[X_0\|X_1] \coloneq X_3\|X_4$\\
				return $L[X_0\|X_1]$
				}{1}
				}{0.8}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 6}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item We can move the sampling steps to the top since they're no longer dependent on other variables.
				\item Note how nothing after $L[X_0\|X_1] \coloneq X_3\|X_4$ affects what the adversary sees!
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad \hl{$X_3 \twoheadleftarrow \bits^\lambda$}\\
				\quad \hl{$X_4 \twoheadleftarrow \bits^\lambda$}\\
				\quad \hl{$L[X_0\|X_1] \coloneq X_3\|X_4$}\\
				\quad if $L_1[X_1]$ undefined:\\
				\quad \quad $L_1[X_1] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{2} \coloneq X_{0} \oplus L_1[X_1]$\\
				\quad if $L_2[X_2]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_2[X_2] \coloneq X_3 \oplus X_1$\\
				\quad if $L_3[X_3]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_3[X_3] \coloneq X_4 \oplus X_2$\\
				\hl{return $L[X_0\|X_1]$}
				}{1}
				}{0.8}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 7}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}
				\item We can move the sampling steps to the top since they're no longer dependent on other variables.
				\item Note how nothing after $L[X_0\|X_1] \coloneq X_3\|X_4$ affects what the adversary sees!
				\item So, we can move all bad-event logic to the end of time, without changing the bad event's overall probability.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad \hl{$L[X_0\|X_1] \coloneq \bits^{2\lambda}$}\\
				\quad \hl{$\mathcal{X} \coloneq \mathcal{X} \cup \{X_0\|X_1\}$}\\
				\quad return $L[X_0\|X_1]$
				}{1}\\[1em]
				\sslibrarysubroutine{\hl{end of time}}{}{
				\hl{for each $X_0\|X_1 \in \mathcal{X}:$}\\
				\quad \hl{$X_3\|X_4 \coloneq L[X_0\|X_1]$}\\
				\quad if $L_1[X_1]$ undefined:\\
				\quad \quad $L_1[X_1] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{2} \coloneq X_{0} \oplus L_1[X_1]$\\
				\quad if $L_2[X_2]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_2[X_2] \coloneq X_3 \oplus X_1$\\
				\quad if $L_3[X_3]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_3[X_3] \coloneq X_4 \oplus X_2$
				}{1}
				}{0.7}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 8}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item We need to analyze the probability of the bad event happening.
				\item Let's say the adversary makes $q$ queries.
				\item The bad event happens if:
				      \begin{itemize}[<+->]
					      \item $X_2$ value collides with previous $X_2$.
					      \item $X_3$ value collides with previous $X_3$.
				      \end{itemize}
				\item Recall: $X_2 = X_0 \oplus L_1[X_1]$ where $L_1[X_1]$ is chosen randomly.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad $L[X_0\|X_1] \coloneq \bits^{2\lambda}$\\
				\quad $\mathcal{X} \coloneq \mathcal{X} \cup \{X_0\|X_1\}$\\
				\quad return $L[X_0\|X_1]$
				}{1}\\[1em]
				\sslibrarysubroutine{end of time}{}{
				for each $X_0\|X_1 \in \mathcal{X}:$\\
				\quad $X_3\|X_4 \coloneq L[X_0\|X_1]$\\
				\quad if $L_1[X_1]$ undefined:\\
				\quad \quad $L_1[X_1] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{2} \coloneq X_{0} \oplus L_1[X_1]$\\
				\quad if $L_2[X_2]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_2[X_2] \coloneq X_3 \oplus X_1$\\
				\quad if $L_3[X_3]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_3[X_3] \coloneq X_4 \oplus X_2$
				}{1}
				}{0.7}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 9}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item So, we need to analyze when $X_2$ collisions occur.
				\item If $(X_0, X_1)$ and $(X_0', X_1')$ are two different inputs...
				\item A collision happens when $X_2 = X_2'$:
				      \begin{align*}
					      X_0 \oplus L_1[X_1] = X_0' \oplus L_1[X_1']
				      \end{align*}
				\item If $X_1 \neq X_1'$, then $L_1[X_1]$ and $L_1[X_1']$ are independent random values
				\item The probability of this specific collision is $2^{-\lambda}$
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad $L[X_0\|X_1] \coloneq \bits^{2\lambda}$\\
				\quad $\mathcal{X} \coloneq \mathcal{X} \cup \{X_0\|X_1\}$\\
				\quad return $L[X_0\|X_1]$
				}{1}\\[1em]
				\sslibrarysubroutine{end of time}{}{
				for each $X_0\|X_1 \in \mathcal{X}:$\\
				\quad $X_3\|X_4 \coloneq L[X_0\|X_1]$\\
				\quad if $L_1[X_1]$ undefined:\\
				\quad \quad $L_1[X_1] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{2} \coloneq X_{0} \oplus L_1[X_1]$\\
				\quad if $L_2[X_2]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_2[X_2] \coloneq X_3 \oplus X_1$\\
				\quad if $L_3[X_3]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_3[X_3] \coloneq X_4 \oplus X_2$
				}{1}
				}{0.7}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 10 - Total probability analysis}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item For $q$ queries, we have at most $q(q-1)/2$ pairs of queries
				\item Prob. of any $X_2$ collision across $q$ queries:
				      $q(q-1)/(2 \cdot 2^{\lambda}) \approx q^2/2^{\lambda+1}$
				\item Similarly for $X_3$ values: the probability of any $X_3$ collision is at most $q^2/2^{\lambda+1}$.
				\item Total probability of bad event: at most $q^2/2^{\lambda}$
				\item With $\lambda \gg \log q$, this probability is negligible.
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad $L[X_0\|X_1] \coloneq \bits^{2\lambda}$\\
				\quad $\mathcal{X} \coloneq \mathcal{X} \cup \{X_0\|X_1\}$\\
				\quad return $L[X_0\|X_1]$
				}{1}\\[1em]
				\sslibrarysubroutine{end of time}{}{
				for each $X_0\|X_1 \in \mathcal{X}:$\\
				\quad $X_3\|X_4 \coloneq L[X_0\|X_1]$\\
				\quad if $L_1[X_1]$ undefined:\\
				\quad \quad $L_1[X_1] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{2} \coloneq X_{0} \oplus L_1[X_1]$\\
				\quad if $L_2[X_2]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_2[X_2] \coloneq X_3 \oplus X_1$\\
				\quad if $L_3[X_3]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_3[X_3] \coloneq X_4 \oplus X_2$
				}{1}
				}{0.7}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}{Step 11}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item By the bad event technique, the advantage of any adversary is at most $q^2/2^{\lambda}$.
				\item Without bad events, our last hybrid samples each response randomly.
				\item Since the sampling logic is all that remains visible to the adversary, this is equivalent to the final simplified library.
				\item This is indistinguishable from a truly random permutation for $q \ll 2^{\lambda/2}$ queries.
				\item (The birthday bound tells us that's when collisions become likely)
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\vspace{-1.5cm}
			\begin{center}
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad $L[X_0\|X_1] \coloneq \bits^{2\lambda}$\\
				\quad $\mathcal{X} \coloneq \mathcal{X} \cup \{X_0\|X_1\}$\\
				\quad return $L[X_0\|X_1]$
				}{1}\\[1em]
				\sslibrarysubroutine{end of time}{}{
				for each $X_0\|X_1 \in \mathcal{X}:$\\
				\quad $X_3\|X_4 \coloneq L[X_0\|X_1]$\\
				\quad if $L_1[X_1]$ undefined:\\
				\quad \quad $L_1[X_1] \twoheadleftarrow \bits^\lambda$\\
				\quad $X_{2} \coloneq X_{0} \oplus L_1[X_1]$\\
				\quad if $L_2[X_2]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_2[X_2] \coloneq X_3 \oplus X_1$\\
				\quad if $L_3[X_3]$ defined: $\texttt{bad} \coloneq \texttt{true}$\\
				\quad $L_3[X_3] \coloneq X_4 \oplus X_2$
				}{1}
				}{0.7}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{Proof of security for 3-round Feistel cipher}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}
				\item Rest of the transition steps are trivial. $\qed$
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{center}
				\sslinked{
				\sslibrary{\mathbb{F}}{prp-real}{
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X_0\|X_1}{
				if $L[X_0\|X_1]$ undefined:\\
				\quad $L[X_0\|X_1] \coloneq \bits^{2\lambda}$\\
				\quad return $L[X_0\|X_1]$
				}{1}
				}{0.7}
				}{\approxeq}{
				\sslibrary{\mathbb{F}}{prp-rand}{
				$L \coloneq$ [\ ]\\[1em]
				\sslibrarysubroutine{$\text{prp.query}_{\mathbb{F}}$}{X}{
				if $L[X]$ undefined:\\
				\quad $Y \twoheadleftarrow \bits^n \ \setminus \ \mathcal{y}$\\
				\quad $\mathcal{y} \coloneq \mathcal{y} \cup \{Y\}$\\
				\quad $L[X] \coloneq Y$\\
				return $L[X]$
				}{1}
				}{0.7}
				}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{DES: Feistel in practice}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{Data Encryption Standard (DES)} is a classic real-world implementation of the Feistel structure
				\item Properties:
				      \begin{itemize}
					      \item 16 Feistel rounds.
					      \item 56-bit key (64 bits with parity).
					      \item 64-bit block size.
					      \item Standardized in 1977.
				      \end{itemize}
				\item Problem: By the 1990s, 56-bit keys became too small for security.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item \textbf{Triple DES (3DES)} replaced it:
				      \begin{itemize}
					      \item Uses three DES operations in sequence.
					      \item $C = E_{K3}(D_{K2}(E_{K1}(P)))$
					      \item Effectively doubles the key length.
					      \item Compatible with legacy DES when $K1 = K2 = K3$
				      \end{itemize}
				\item 3DES still used in legacy systems, but largely replaced by AES for performance reasons.
				\item Lesson: Feistel structure made it possible to adapt DES rather than abandon it.
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{EFF's ``Deep Crack''}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item In 1998, the Electronic Frontier Foundation built a special-purpose machine called ``Deep Crack''.\footnote{I'm not responsible for any readings into that name.}
				\item Cost: Only \$250,000 (far less than the NSA budget!)
				\item Purpose: Prove that 56-bit DES keys were insufficient.
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\imagewithcaption{deep_crack_a.jpg}{EFF's ``Deep Crack''}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{EFF's ``Deep Crack''}
	\begin{columns}[c]
		\begin{column}{0.6\textwidth}
			\begin{itemize}[<+->]
				\item July 1998: Deep Crack broke a DES challenge in just 56 hours.
				\item Message revealed: ``It's time for those 128-, 192-, and 256-bit keys.''
				\item Impact:
				      \begin{itemize}
					      \item Publicly demonstrated DES was obsolete.
					      \item Accelerated adoption of AES.
					      \item Made ``it's theoretically breakable'' a practical reality.
					      \item Priceless reaction from government officials!
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.4\textwidth}
			\imagewithcaption{deep_crack_b.jpg}{Paul Kocher. He's still active in cryptography today, insanely productive research career, many crazy attacks}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{AES: a good example of a PRP}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item AES is the most widely used PRP in the world.
				\item It works on fixed-size blocks: 128 bits.
				\item Key sizes: 128, 192, or 256 bits.
				\item Each AES key defines a specific permutation over the space of all 128-bit values.
				\item For each key, AES maps each possible 128-bit input to exactly one 128-bit output.
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item Different keys create different permutations.
				\item AES is efficiently invertible:
				      \begin{itemize}[<+->]
					      \item $\text{Dec}(K, \text{Enc}(K, M)) = M$
				      \end{itemize}
				\item AES is believed to be computationally indistinguishable from a random permutation.
				\item Has withstood extensive cryptanalysis for over 20 years.
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{AES structure}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item Internal structure: substitution-permutation network with multiple rounds.\footnote{Check out this amazing interactive animation of AES's internal structure: \url{https://formaestudio.com/rijndaelinspector/archivos/Rijndael_Animation_v4_eng-html5.html}}
				      \begin{itemize}[<+->]
					      \item SubBytes: non-linear substitution
					      \item ShiftRows: transposition
					      \item MixColumns: mixing operation
					      \item AddRoundKey: XOR with round key
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{flushright}
				\scalebox{0.55}{
					\begin{tikzpicture}[
							block/.style={rectangle, draw, fill=ciphergray!15, minimum width=2cm, minimum height=0.6cm, align=center, font=\footnotesize},
							arrow/.style={-stealth, thick},
							node distance=0.5cm
						]
						% Input
						\node[block] (input) {Plaintext (128 bits)};

						% Initial round (just key addition)
						\node[block, below=0.8cm of input] (addroundkey0) {AddRoundKey};
						\draw[arrow] (input) -- (addroundkey0);
						\node[right=0.3cm of addroundkey0, align=left, font=\scriptsize] (roundkey0) {Round Key 0};
						\draw[arrow] (roundkey0) -- (addroundkey0);

						% Main rounds box
						\draw[rounded corners, dashed] (-2,-2.2) rectangle (2,-5.2);
						\node[align=left, font=\scriptsize] at (-1.7,-2.5) {Rounds 1-9};

						% Main round operations
						\node[block, below=0.8cm of addroundkey0] (subbytes) {SubBytes};
						\draw[arrow] (addroundkey0) -- (subbytes);

						\node[block, below=of subbytes] (shiftrows) {ShiftRows};
						\draw[arrow] (subbytes) -- (shiftrows);

						\node[block, below=of shiftrows] (mixcolumns) {MixColumns};
						\draw[arrow] (shiftrows) -- (mixcolumns);

						\node[block, below=of mixcolumns] (addroundkey) {AddRoundKey};
						\draw[arrow] (mixcolumns) -- (addroundkey);
						\node[right=0.3cm of addroundkey, align=left, font=\scriptsize] (roundkey) {Round Keys 1-9};
						\draw[arrow] (roundkey) -- (addroundkey);

						% Final round box
						\draw[rounded corners, dashed] (-2,-5.8) rectangle (2,-7.8);
						\node[align=left, font=\scriptsize] at (-1.7,-6.1) {Round 10};

						% Final round operations (no MixColumns)
						\node[block, below=0.8cm of addroundkey] (subbytes2) {SubBytes};
						\draw[arrow] (addroundkey) -- (subbytes2);

						\node[block, below=of subbytes2] (shiftrows2) {ShiftRows};
						\draw[arrow] (subbytes2) -- (shiftrows2);

						\node[block, below=of shiftrows2] (addroundkey2) {AddRoundKey};
						\draw[arrow] (shiftrows2) -- (addroundkey2);
						\node[right=0.3cm of addroundkey2, align=left, font=\scriptsize] (roundkey2) {Round Key 10};
						\draw[arrow] (roundkey2) -- (addroundkey2);

						% Output
						\node[block, below=0.8cm of addroundkey2] (output) {Ciphertext (128 bits)};
						\draw[arrow] (addroundkey2) -- (output);

						% Note about final round
						\node[align=center, font=\scriptsize, color=red] at (3.2,-6.8) {No MixColumns\\in final round};
					\end{tikzpicture}
				}
			\end{flushright}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}{AES: security and attacks over time}
	\begin{columns}[c]
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item AES has been heavily analyzed for over 20 years.
				\item Best attacks against full AES have gradually improved:
				      \begin{itemize}[<+->]
					      \item 2011: Biclique attack (Bogdanov et al.) reduced complexity to $2^{126.1}$ for AES-128.
					      \item Various side-channel attacks developed (power analysis, cache timing).\footnote{This is the main way to attack AES in practice. Side-channel attacks will be discussed in more depth later in the course.}
					      \item Advances in meet-in-the-middle and related-key techniques.
				      \end{itemize}
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item Despite these advances:
				      \begin{itemize}[<+->]
					      \item No practical attacks on full AES-128.
					      \item Best attacks still require $\approx 2^{126}$ operations.
					      \item At this complexity, attacks remain purely theoretical.
					      \item Would require resources far exceeding global computing power.
				      \end{itemize}
				\item Even quantum computers offer only modest advantage (Grover's algorithm reduces security to $2^{64}$ operations).\footnote{More on quantum computers and how they affect cryptography later in the course.}
			\end{itemize}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}[plain]
	\titlepage
\end{frame}
\end{document}