8.1pubkey.tex

\input{main.tex}

\title{Public-Key Encryption Theory}

\begin{document}
\maketitle
\begin{frame}
\frametitle{Outline}
\tableofcontents
\end{frame}
\section{Definitions and Securities of Public-Key Encryption}
\begin{frame}\frametitle{Limitations of Private-Key Cryptography}
\begin{itemize}
\item The key-distribution need physically meeting.
\item The number of keys for $U$ users is $\Theta(U^2)$.
\item Secure communication in open system:
\end{itemize}
\vspace{0.5cm}
Solutions that are based on private-key cryptography are not sufficient to deal with the problem of secure communication in open systems where parties cannot physically meet, or where parties have transient interactions.
\end{frame}
\begin{frame}\frametitle{Needham-Schroeder Protocol}
\begin{itemize}
\item Key Distribution Center (KDC) as Trusted Third Party (TTP).
\item $E_{Bob}(k)$ is a \textbf{ticket} to access $Bob$, $k$ is \textbf{session key}.
\item Used in MIT's Kerberos protocol (in Windows).
\end{itemize}
\begin{columns}[t]
\begin{column}{5cm}
\begin{figure}[t]
\begin{center}
\input{tikz/KDC}
\end{center}
\end{figure}
\end{column}
\begin{column}{5cm}
\textbf{Strength}:
\begin{itemize}
\item each one stores one key
\item no updates
\end{itemize}
\textbf{Weakness}:
\begin{itemize}
\item single-point-of-failure
\end{itemize}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Merkle Puzzles (Key Exchange W/O TTP)}
\begin{itemize}
\item[Alice] prepares $2^{32}$ puzzles $\mathsf{Puzzle}_i$, and sends to Bob.\\
\[\mathsf{Puzzle}_i \gets \mathsf{Enc}_{(0^{96}\|p_i)}(\text{``Puzzle \#''} x_i  \| k_i),\]
where $\mathsf{Enc}$ is 128-bit, $p_i \gets \{0,1\}^{32}$ and $x_i,k_i \gets \{0,1\}^{128}$.
\item[Bob] chooses $\mathsf{Puzzle}_j$ randomly, guesses $p_j$ in $2^{32}$ time, obtains $x_j,k_j$ and sends $x_j$ to Alice.
\item[Alice] lookups puzzle with $x_j$, and uses $k_j$ as secret key.
\item \textbf{Adversary} needs $2^{32+32}$ time.
\end{itemize}
\begin{block}{Better Gap?}
Quadratic gap is best possible if we treat cipher as a black box oracle.
\end{block}
\end{frame}
\begin{frame}\frametitle{Public-Key Revolution}
\begin{itemize}
\item In 1976, Whitfield Diffie and Martin Hellman published ``\emph{New Directions in Cryptography}''.
\item \textbf{Asymmetric} or \textbf{public-key} encryption schemes:
\begin{itemize}
\item \textbf{Public key} as the encryption key.
\item \textbf{Private key} as the decryption key.
\end{itemize}
\item \textbf{Public-key primitives}:
\begin{itemize}
\item Public-key encryption.
\item Digital signatures. (non-repudiation)
\item Interactive key exchange.
\end{itemize}
\item \textbf{Strength}:
\begin{itemize}
\item Key distribution over public channels.
\item Reduce the need to store many keys.
\item Enable security in open system.
\end{itemize}
\item \textbf{Weakness}: slow, active attack on public key distribution.
%\item \textbf{Peoples}: Ralphe Merkle (his advisor at Stanford was Hellman), Michael Rabin, Rivest, Shamir, and Adleman.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Definitions}
\begin{figure}
\begin{center}
\input{tikz/public-key}
\end{center}
\end{figure}
\begin{itemize}
\item \textbf{Key-generation} algorithm: $(pk,sk) \gets \mathsf{Gen}$, key length $\ge n$.
\item  \textbf{Plaintext space} $\mathcal{M}$ is associated with $pk$.
\item \textbf{Encryption} algorithm: $c \gets \mathsf{Enc}_{pk}(m)$.
\item \textbf{Decryption} algorithm: $m:= \mathsf{Dec}_{sk}(c)$, or outputs $\perp$.
\item \textbf{Requirement}: $\Pr[\mathsf{Dec}_{sk}(\mathsf{Enc}_{pk}(m)) = m] \ge 1 - \mathsf{negl}(n)$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Security against Eavesdroppers $=$ CPA}
The eavesdropping indistinguishability experiment $\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
\item $(pk,sk) \gets \mathsf{Gen}(1^n)$.
\item $\mathcal{A}$ \textbf{is given input $\mathbf{pk}$ and so oracle access to $\mathbf{\mathsf{Enc}_{pk}(\cdot)}$}, outputs $m_0, m_1$ of the same length. 
\item $b \gets \{0,1\}$. $c \gets \mathsf{Enc}_{pk}(m_b)$ (challenge) is given to $\mathcal{A}$.
\item $\mathcal{A}$ \textbf{continues to have access to $\mathbf{\mathsf{Enc}_{pk}(\cdot)}$} and outputs $b'$.
\item If $b' = b$, $\mathcal{A}$ succeeded $\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\Pi}=1$, otherwise 0.
\end{enumerate}
\begin{definition}
$\Pi$ is \textbf{CPA-secure} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[ \Pr\left[\mathsf{PubK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n). \]
\end{definition}
\end{frame}
\begin{frame}\frametitle{Security Properties of Public-Key Encryption}
\begin{exampleblock}{} Symmetric ciphers are possible to encrypt a 32-bit message and obtain a 32-bit ciphertext (e.g. with the one time pad). Can the same be done with a public-key system?
\end{exampleblock}
\begin{theorem}
\alert{Q: Would a deterministic public-key encryption scheme be secure in the presence of an eavesdropper?}
\end{theorem}
\begin{proposition}
\alert{Q: If $\Pi$ is secure in the presence of an eavesdropper, is $\Pi$ also CPA-secure? and is it secure for multiple encryptions?}
\end{proposition}
\begin{proposition}
\alert{Q: is perfectly-secret public-key encryption possible?}
\end{proposition}
\end{frame}

\begin{comment}
\begin{frame}\frametitle{Definition of Security of Multiple Encryptions}
The multiple message eavesdropping experiment $\mathsf{PubK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
\item $(pk,sk) \gets \mathsf{Gen}(1^n)$.
\item $\mathcal{A}$ is given input $pk$, outputs $\vec{M}_0=(m_0^1,\dots,m_0^t)$, $\vec{M}_1=(m_1^1,\dots,m_1^t)$ with $\forall i, |m_0^i| = |m_1^i|$. 
\item $b \gets \{0,1\}$. $c^i \gets \mathsf{Enc}_{pk}(m_b^i)$ and $\vec{C}=(c^1,\dots,c^t)$ is given to $\mathcal{A}$. $\mathcal{A}$ outputs $b'$.
\item If $b' = b$, $\mathcal{A}$ succeeded $\mathsf{PrivK}^{\mathsf{mult}}_{\mathcal{A},\Pi}=1$, otherwise 0.
\end{enumerate}
\begin{definition}
$\Pi$ has \textbf{indistinguishable multiple encryption in the presence of an eavesdropper} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[ \Pr\left[\mathsf{PubK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n). \]
\end{definition}
\end{frame}
\begin{frame}\frametitle{Security of Two Encryptions}
Prove: for two encryptions, $\Pr[\mathsf{PubK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)=1] \le \frac{1}{2} + \mathsf{negl}(n)$.\\ Let $c_i^j = \mathsf{Enc}_{pk}(m_i^j)$.
\begin{align*}
\Pr[\mathsf{PubK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)=1] &= \frac{1}{2}\cdot \Pr[\mathcal{A}(\alert{c^1_0},\alert{c^2_0})=\alert{0}] + \frac{1}{2}\cdot \Pr[\mathcal{A}(c^1_1,c^2_1)=1]
\end{align*}
Reduce $\mathcal{A}'$ for a single message to $\mathcal{A}$ for two messages.
\begin{figure}
\begin{center}
\input{tikz/hybrideg}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Proof (Cont.)}
\[\text{Prove}:\;\frac{1}{2}+\mathsf{negl}(n) \ge \frac{1}{2}\cdot \Pr[\mathcal{A}(\alert{c_0^1},\alert{c_0^2})=\alert{0}] + \frac{1}{2}\cdot \Pr[\mathcal{A}(\alert{c_0^1},c_1^2)=1].\]
$\Pr[\mathcal{A}'(\alert{c^2_0})=\alert{0}]=\Pr[\mathcal{A}(\alert{c^1_0},\alert{c^2_0})=\alert{0}]$;
$\Pr[\mathcal{A}'(c^2_1)=1]=\Pr[\mathcal{A}(\alert{c^1_0},c^2_1)=1]$.\\
\begin{align*}
\frac{1}{2}+\mathsf{negl}(n) &\ge \Pr[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A'},\Pi}(n)=1] \\
&= \frac{1}{2}\cdot \Pr[\mathcal{A}'(\alert{c^2_0})=\alert{0}] + \frac{1}{2}\cdot \Pr[\mathcal{A}'(c^2_1)=1]\\
&= \frac{1}{2}\cdot \Pr[\mathcal{A}(\alert{c^1_0},\alert{c^2_0})=\alert{0}] + \frac{1}{2}\cdot \Pr[\mathcal{A}(\alert{c^1_0},c^2_1)=1].
\end{align*}
\[\text{Similarly, }\;\frac{1}{2}+\mathsf{negl}(n) \ge \frac{1}{2}\cdot \Pr[\mathcal{A}(\alert{c_0^1},c_1^2)=\alert{0}] + \frac{1}{2}\cdot \Pr[\mathcal{A}(c_1^1,c_1^2)=1].\]
\end{frame}
\begin{frame}\frametitle{Proof (Cont.)}
\begin{align*}
1+\mathsf{negl}(n) &\ge \frac{1}{2}\cdot \Pr[\mathcal{A}(\alert{c_0^1},\alert{c_0^2})=\alert{0}] + \frac{1}{2}\cdot \Pr[\mathcal{A}(c_1^1,c_1^2)=1]\\
&+ \frac{1}{2}\cdot \left(\Pr[\mathcal{A}(\alert{c_0^1},c_1^2)=1] +  \Pr[\mathcal{A}(\alert{c_0^1},c_1^2)=\alert{0}]\right)\\
&= \frac{1}{2} + \Pr[\mathsf{PubK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)=1]. 
\end{align*}
\end{frame}
\begin{frame}\frametitle{Hybrid Argument}
Proof technique to show that two distributions are computationally indistinguishable.
\begin{enumerate}
\item Define a sequence of polynomially many distributions $D_1,\dotsc,D_t$ (hybrid distributions) as follows:
\begin{itemize}
\item $D_1$ and $D_t$ are to be shown computationally indistinguishable.
\item Any adjacent distributions $D_i$ and $D_{i+1}$ differ by only one application of a cryptographic primitive.
\end{itemize}
\item It is (comparatively) easier to prove that adjacent distributions are computationally indistinguishable.
\item Since computational indistinguishability is transitive across a polynomial number of distributions, we conclude that $D_1$ and $D_t$ are computationally indistinguishable.
\end{enumerate}
\end{frame}
\begin{frame}\frametitle{Security of Multiple Encryptions}
Step 1: define a sequence of distribution:
\[ \vec{C}^{(i)} \overset{\text{def}}{=} \underbrace{c^1_0,\dotsc,c^i_0}_{i\; \text{terms}},\underbrace{c^{i+1}_1,\dotsc,c^t_1}_{t-i\; \text{terms}}.\]
\[
\Pr[\mathsf{PubK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)=1] = \frac{1}{2}\cdot \Pr[\mathcal{A}(\vec{C}^{(t)})=0] + \frac{1}{2}\cdot \Pr[\mathcal{A}(\vec{C}^{(0)})=1]
\]
\end{frame}
\begin{frame}\frametitle{Proof (Cont.)}
Step 2: prove that adjacent distributions are indistinguishable.\\ Reduce $\mathcal{A}'$ for single message to $\mathcal{A}$.
\begin{figure}
\begin{center}
\input{tikz/hybridproof}
\end{center}
\end{figure}
If $\mathcal{A}$ distinguishes between $\vec{C}^{(i)}$ and $\vec{C}^{(i-1)}$, this means that it distinguishes between $c^i_0$ and $c^i_1$ (this is the only difference).
\end{frame}
\begin{frame}\frametitle{Proof (Cont.)}
\begin{align*}
\Pr[\mathcal{A'}=0|b=0] &= \sum^t_{i^*=1}\frac{1}{t}\cdot \Pr[\mathcal{A}(\vec{C}^{(i^*)})=0].\\
\Pr[\mathcal{A'}=1|b=1] &= \sum^t_{i^*=1}\frac{1}{t}\cdot \Pr[\mathcal{A}(\vec{C}^{(i^*-1)})=1]\\
&=\sum^{t-1}_{i^*=0}\frac{1}{t}\cdot \Pr[\mathcal{A}(\vec{C}^{(i^*)})=1].
\end{align*}
\end{frame}
\begin{frame}\frametitle{Proof (Cont.)}
Step 3: conclusion.
\begin{align*}
\frac{1}{2}+\mathsf{negl}(n) &\ge \Pr[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A'},\Pi}(n)=1] \\
&= \frac{1}{2}\cdot \Pr[\mathcal{A'}=0|b=0] + \frac{1}{2}\cdot \Pr[\mathcal{A'}=1|b=1]\\
&= \sum^t_{i^*=1}\frac{1}{2t}\cdot \Pr[\mathcal{A}(\vec{C}^{(i^*)})=0] + \sum^{t-1}_{i^*=0}\frac{1}{2t}\cdot \Pr[\mathcal{A}(\vec{C}^{(i^*)})=1]\\
&= \frac{1}{2t}\cdot \sum^{t-1}_{i^*=1}\left( \Pr[\mathcal{A}(\vec{C}^{(i^*)})=0] + \Pr[\mathcal{A}(\vec{C}^{(i^*)})=1]\right)\\
&+ \frac{1}{2t}\cdot \left( \Pr[\mathcal{A}(\vec{C}^{(t)})=0] + \Pr[\mathcal{A}(\vec{C}^{(0)})=1]\right)\\
&= \frac{t-1}{2t} + \frac{1}{t}\cdot \Pr[\mathsf{PubK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)=1].
\end{align*}
\end{frame}
\begin{frame}\frametitle{Encrypting Arbitrary-Length Messages}
$\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ is an encryption scheme encrypts only 1-bit message.\\
$\Pi'= (\mathsf{Gen}, \mathsf{Enc}', \mathsf{Dec}')$:
\[\mathsf{Enc}'_{pk}(m)=\mathsf{Enc}_{pk}(m_1),\dotsc,\mathsf{Enc}_{pk}(m_t).\]
\begin{proposition}
If $\Pi$ has indistinguishable encryptions in the presence of an eavesdropper, then so does $\Pi'$.
\end{proposition}
\end{frame}
\end{comment}

\begin{frame}\frametitle{Construction of Hybrid Encryption}
To speed up the encryption of long message, use private-key encryption $\Pi'$ in tandem with public-key encryption $\Pi$.
\begin{columns}
\begin{column}{5cm}
\begin{figure}
\begin{center}
\input{tikz/hybrid-encrypt}
\end{center}
\end{figure}
\end{column}
\begin{column}{5cm}
\begin{construction}
$\Pi^{\mathsf{hy}} = (\mathsf{Gen}^{\mathsf{hy}}, \mathsf{Enc}^{\mathsf{hy}}, \mathsf{Dec}^{\mathsf{hy}})$:
\begin{itemize}
\item $\mathsf{Gen}^{\mathsf{hy}}$: $(pk,sk) \gets \mathsf{Gen}(1^n)$.
\item $\mathsf{Enc}^{\mathsf{hy}}$: $pk$ and $m$. 
\begin{enumerate}
\item $k \gets \{0,1\}^n$.
\item $c_1 \gets \mathsf{Enc}_{pk}(k)$, $c_2 \gets \mathsf{Enc}'_{k}(m)$.
\end{enumerate}
\item $\mathsf{Dec}^{\mathsf{hy}}$: $sk$ and $\langle c_1,c_2\rangle$.
\begin{enumerate}
\item $k := \mathsf{Dec}_{sk}(c_1)$.
\item $m := \mathsf{Dec}'_k(c_2)$.
\end{enumerate}
\end{itemize}
\end{construction}
\end{column}
\end{columns}
\alert{Q: is hybrid encryption a public-key enc. or private-key enc. ?}
\end{frame}
\begin{frame}\frametitle{Security of Hybrid Encryption}
\begin{theorem}
If $\Pi$ is a CPA-secure public-key encryption scheme and $\Pi'$ is a private-key encryption scheme that has indistinguishable encryptions in the presence of an eavesdropper, then $\Pi^{\mathsf{hy}}$ is a CPA-secure public-key encryption scheme.
\end{theorem}
\begin{figure}
\begin{center}
\input{tikz/hybrid-enc-proof}
\end{center}
\end{figure}
\end{frame}
\section{Trapdoor Permutations}
\begin{frame}\frametitle{Overview}
\textbf{Trapdoor function}: is easy to compute, yet difficult to find its inverse without special info., the ``trapdoor''. (One Way Function with the ``trapdoor'')
\newline

A public-key encryption scheme can be constructed from any trapdoor permutation. (``\emph{Theory and Applications of Trapdoor Functions}'', [Yao, 1982])
\begin{figure}
\begin{center}
\input{tikz/trapdoor.tex}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Definition of Families of Trapdoor Permutations}
A tuple of polynomial-time algorithms $\Pi = (\mathsf{Gen}, \mathsf{Samp}, f, \mathsf{Inv})$ is a \textbf{family of trapdoor permutations (TDP)} if:
\begin{itemize}
\item \textbf{parameter generation} algorithm $\mathsf{Gen}$, on input $1^n$, outputs $(I,\mathsf{td})$ with $\abs{I} \ge n$. $(I, \mathsf{td})$ defines a set $\mathcal{D}_I = \mathcal{D}_{\mathsf{td}}$.
\item $\mathsf{Gen}_I$ outputs only $I$.
$(\mathsf{Gen}_I, \mathsf{Samp}, f)$ is OWP.
\item deterministic \textbf{inverting algorithm} $\mathsf{Inv}$. $\forall (I,\mathsf{td})$ and $\forall x \in \mathcal{D}_{I}$, 
\[ \mathsf{Inv}_{\mathsf{td}}(f_I(x))=x.\]
\end{itemize}
Deterministic polynomial-time algorithm $\mathsf{hc}$ is a \textbf{hard-core predicate} of $\Pi$ if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[ \Pr[\mathcal{A}(I,f_I(x)) = \mathsf{hc}_I(x)] \le \frac{1}{2} +\mathsf{negl}(n). \]
\end{frame}
\begin{frame}\frametitle{Examples}
\begin{exampleblock}{Let $f$ with $<I, \mathsf{td}>$ be a TDP. Which of the following $f'$ is also a TDP?}
\begin{itemize}
\item $f'(x) = f(x)\| 000$
\item $f'(x) = f(x)\| \mathsf{td}$
\item $f'(x\|x') = f(x)\|\mathsf{Inv}_{\mathsf{td}}(f(x'))$
\item $f'(x\|x') = f(x)\|f(x')$
\item $f'(x) = f(x) \oplus I$
\item $ f'(x) = \left\{
  \begin{array}{l l}
    f(x) & \quad \text{if $x[0,1,2,3] \neq 1010$}\\
    x & \quad \text{otherwise}\\
  \end{array} \right. $
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Public-key Encryption Schemes from TDPs}
\begin{construction}
\begin{itemize}
\item $\mathsf{Gen}$: $(I, \mathsf{td}) \gets \widehat{Gen}$ output \textbf{public key} $I$ and \textbf{private key} $\mathsf{td}$.
\item $\mathsf{Enc}$: on input $I$ and $m \in \{0,1\}$, choose a random $x\gets \mathcal{D}_I$ and output $\langle f_I(x), \mathsf{hc}_I(x)\oplus m \rangle$.
\item $\mathsf{Dec}$: on input $\mathsf{td}$ and $\langle y, m'\rangle$, compute $x:= f^{-1}_I(y)$ and output $\mathsf{hc}_I(x)\oplus m'$.
\end{itemize}
\end{construction}
\begin{theorem}
If $\widehat{\Pi}=(\widehat{Gen},f)$ is TDP, and $\mathsf{hc}$ is HCP for $\widehat{\Pi}$, then Construction $\Pi$ is CPA-secure.
\end{theorem}
\begin{exampleblock}{Is the following scheme is secure?}
$\mathsf{Enc}_{I}(m) = f_I(m)$, $\mathsf{Dec}_{\mathsf{td}}(c) = f^{-1}_I(c)$.
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Proof}
\textbf{Idea}: $\mathsf{hc}_I(x)$ is pseudorandom. Reduce $\mathcal{A}_{\mathsf{hc}}$ for $\mathsf{hc}$ to $\mathcal{A}$ for $\Pi$.
\begin{figure}
\begin{center}
\input{tikz/tdp-pk}
\end{center}
\end{figure}
\[\Pr[\mathcal{A}_{\mathsf{hc}}(I,f_I(x))=\mathsf{hc}_I(x)] = \]
\[\frac{1}{2}\cdot (\Pr[b'=b|z=\mathsf{hc}_I(x)]+\Pr[b'\neq b|z\neq \mathsf{hc}_I(x)]).\]
\end{frame}
\begin{frame}\frametitle{Proof (Cont.)}
\[\Pr[b'=b|z=\mathsf{hc}_I(x)] = \Pr[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1]=\varepsilon(n).\]
If $z \neq \mathsf{hc}_I(x)$, $m' = m_b\oplus \overline{\mathsf{hc}}_I(x) = m_{\overline{b}}\oplus \mathsf{hc}_I(x)$,\\ which means $m_{\overline{b}}$ is encrypted.
\[\Pr[b'=b|z\neq \mathsf{hc}_I(x)] = \Pr[\mathsf{PubK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=0]=1-\varepsilon(n).\]
\[\Pr[b'\neq b|z\neq \mathsf{hc}_I(x)] =\varepsilon(n).\]
\[\Pr[\mathcal{A}_{\mathsf{hc}}(I,f_I(x))=\mathsf{hc}_I(x)] = \frac{1}{2}\cdot (\varepsilon(n)+\varepsilon(n)) = \varepsilon(n).\]
\end{frame}
%\begin{frame}\frametitle{Encrypting Longer Messages}
%\begin{theorem}
%If $\exists$ TDP $\Pi$, then $\exists$ TDP $\widehat{\Pi}$ with a HCP $\mathsf{hc}$ for $\widehat{\Pi}$.
%\end{theorem}
%\textbf{Example}: If RSA assumption holds then the least-significant bit is hard-core for the RSA family of TDP.
%\newline
%
%an $\ell$-it message $m=m_1\cdots m_{\ell}$, the public key $I$, the ciphertext is
%\[\langle f_I(x_1), \mathsf{hc}_I(x_I)\oplus m_1\rangle,\dotsc,\langle f_I(x_{\ell}), \mathsf{hc}_I(x_{\ell})\oplus m_{\ell}\rangle,\]
%with $x_1,\dotsc,x_{\ell}$ chosen independently and \emph{u.r.a} from $\mathcal{D}_I$.
%\newline
%
%An alternative way: $x_1\gets \mathcal{D}_I$ and compute $x_{i+1} := f_I(x_i)$ for $i=1$ to $\ell$. the ciphertext is 
%\[\langle x_{\ell+1},\mathsf{hc}_I(x_1)\oplus m_1,\dotsc,\mathsf{hc}_I(x_{\ell})\oplus m_{\ell}\rangle.\]
%\end{frame}
\section{Security Against Chosen-Ciphertext Attacks}
\begin{frame}\frametitle{Scenarios of CCA in Public-Key Setting}
\begin{enumerate}
\item An adversary $\mathcal{A}$ observes the ciphertext $c$ sent by $\mathcal{S}$ to $\mathcal{R}$.
\item $\mathcal{A}$ send $c'$ to $\mathcal{R}$ in the name of $\mathcal{S}$ or its own.
\item $\mathcal{A}$ infer $m$ from the decryption of $c'$ to $m'$.
\end{enumerate}
\begin{exampleblock}{Scenarios}
\begin{itemize}
\item \textbf{login to on-line bank with the password}: trial-and-error, learn info from the feedback of bank.
\item \textbf{reply an e-mail with the quotation of decrypted text}.
\item \textbf{malleability of ciphertexts}: e.g. doubling others' bids at an auction.
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Definition of Security Against CCA/CCA2}
The CCA/CCA2 indistinguishability experiment $\mathsf{PubK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
\item $(pk,sk) \gets \mathsf{Gen}(1^n)$.
\item $\mathcal{A}$ \textbf{is given input $pk$ and oracle access to $\mathsf{Dec}_{sk}(\cdot)$}, outputs $m_0, m_1$ of the same length. 
\item $b \gets \{0,1\}$. $c \gets \mathsf{Enc}_{pk}(m_b)$ is given to $\mathcal{A}$.
\item $\mathcal{A}$ \textbf{have access to $\mathsf{Dec}_{sk}(\cdot)$ except for $c$ in CCA2}\footnote{CCA is also called Lunchtime attacks; CCA2 is also called Adaptive CCA.} and outputs $b'$.
\item If $b' = b$, $\mathcal{A}$ succeeded $\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}=1$, otherwise 0.
\end{enumerate}
\begin{definition}
$\Pi$ has \textbf{CCA/CCA2-secure} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[ \Pr\left[\mathsf{PubK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n). \]
\end{definition}
\end{frame}
\begin{frame}\frametitle{Examples}
\begin{exampleblock}{Let $(Gen, E, D)$ be CCA-secure on message space $\{0, 1\}^{128}$. Which of the following is also CCA-secure?}
\begin{itemize}
\item $E'(pk, m) = (E(pk, m), 0^{128})$\\
$D'(sk, (c_{1}, c_{2})) = \left\{ 
  \begin{array}{l l}
    D(sk, c_{1}) & \quad \text{if}\ c_{2} = 0^{128}\\
    \bot &  \quad \text{otherwise}\\
  \end{array} \right. $
\item $E'(pk, m)= (E(pk, m), E(pk, 0^{128}))$\\
$D'(sk, (c_{1}, c_{2})) = D(sk, c_{1})$
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}{State of the Art on CCA2-secure Encryption}
\begin{itemize}
\item \textbf{Zero-Knowledge Proof}: complex, and impractical. (e.g., Dolev-Dwork-Naor)
\item \textbf{Random Oracle} model: efficient, but not realistic (to consider CRHF as RO). (e.g., RSA-OAEP and Fujisaki-Okamoto)
\item \textbf{DDH(Decisional Diffie-Hellman assumption) and UOWHF(Universal One-Way Hashs Function)}: x2 expansion in size, but security proved w/o RO or ZKP (e.g., Cramer-Shoup system).
\end{itemize}
\textbf{CCA2-secure implies Plaintext-aware}: an adversary cannot produce a valid ciphertext without ``knowing'' the plaintext.
\begin{block}{Open problem}
Constructing a CCA2-secure scheme based on RSA problem as efficient as ``Textbook RSA''.
\end{block}
\end{frame}
\section{Public-Key Encryption from TDP in ROM}
%\section{The Random Oracle Methodology}
\begin{frame}\frametitle{Random Oracle Model (ROM) -- Overview}
\begin{itemize}
\item \textbf{Random oracle (RO)}: a truly random function $H$ answers every possible query with a random response.
\begin{itemize}
\item \textbf{Consistent}: If $H$ ever outputs $y$ for an input $x$ ``on-the-fly'', then it always outputs the same answer given the same input.
\item No one ``knows'' the entire function $H$.
\end{itemize}
\item \textbf{Random oracle model (ROM)}: the existence of a public RO.
%\item \textbf{Standard Model}: the adversary is only limited by time and computational power.
\item \textbf{Methodology}: for constructing proven security in ROM.
\begin{enumerate}
\item a scheme is designed and proven secure in ROM.
\item Instantiate $H$ with a hash function $\hat{H}$, such as SHA-1.
\end{enumerate}
\item \alert{No one seriously claims that a random oracle exists}.\footnote{There exists schemes that are proven secure in ROM but are insecure no matter how the random oracle is instantiated.}
\end{itemize}
\emph{With ROM, it is easy to achieve proven security, while keeping the efficiency by appropriate instantiation.}
\end{frame}
%\begin{frame}\frametitle{ROM in Detail}
%\begin{itemize}
%\item \textbf{Consistent}: If $H$ ever outputs $y$ for an input $x$ ``on-the-fly'', then it always outputs the same answer given the same input.
%\item No one ``knows'' the entire function $H$.
%\item \textbf{PRF vs. RO}: PRF emulates RO, and has different usage:
%\begin{itemize}
%\item PRF: a way of defining what it means for a concrete keyed function to be pseudorandom.
%\item RO: as part of the construction of the primitive, and so must be instantiated if we want a concrete realization.
%\end{itemize}
%\end{itemize}
%\end{frame}
\begin{frame}\frametitle{Simple Illustrations of ROM}
A RO maps $n_1$-bit inputs to $n_2$-bit outputs.
\begin{itemize}
\item A RO as a OWF, experiment:
\begin{enumerate}
\item A random function $H$ is chosen
\item A random $x \in \{0,1\}^{n_1}$ is chosen, and $y := H(x)$ is evaluated
\item $\mathcal{A}$ is given $y$, and succeeds if it outputs $x'$: $H(x')=y$
\end{enumerate}
\item A RO as a CRHF, experiment:
\begin{enumerate}
\item A random function $H$ is chosen
\item $\mathcal{A}$ succeeds if it outputs $x, x'$ with $H(x)=H(x')$ but $x\neq x'$
\end{enumerate}
\item Constructing a PRF from a RO: $n_1=2n$, $n_2=n$.
$ F_k(x) \overset{\text{def}}{=} H(k\| x),\;\; \abs{k}=\abs{x}=n.$
\end{itemize}
\end{frame}
%\begin{frame}\frametitle{Is the Random Oracle Methodology Sound?}
%\begin{itemize}
%\item \textbf{Pro}:
%\begin{itemize}
%\item enables the design of more efficient schemes.
%\item better than no proof at all.
%\item only possible weaknesses are due to the hash function.
%\item few real-world attacks on ``natural'' secure schemes in ROM.
%\end{itemize}
%\item \textbf{Con}:
%\begin{itemize}
%\item No proof that security in ROM implies real-world security.
%\item The reduction can not see ``queries'' in the real world.
%\item Not well understand what is a ``good'' CRHF/PRF like a RO.
%\end{itemize}
%\end{itemize}
%\begin{itemize}
%\item What does security in the ROM guarantee in the real world?
%\item Are ROM fundamentally different from the standard model?
%\end{itemize}
%\end{frame}
\begin{frame}\frametitle{Security Against CPA}
\textbf{Idea}: PubK CPA = PrivK CPA + (Secret Key = TDP + RO)
\begin{columns}[t]
\begin{column}{5cm}
\begin{figure}[t]
\begin{center}
\input{tikz/tdp-cpa}
\end{center}
\end{figure}\end{column}
\begin{column}{5cm}
\begin{construction}
\begin{itemize}
\item $\mathsf{Gen}$: $pk =  I $, $sk = \mathsf{td} $
\item $\mathsf{Enc}$: $r \gets \{0,1\}^*$, output $\langle c_{1}=f_I(r), c_{2}=H(r)\oplus m\rangle$
\item $\mathsf{Dec}$: $r := f_{\mathsf{td}}^{-1}(c_1)$, output $H(r)\oplus c_2$
\end{itemize}
\end{construction}
\end{column}
\end{columns}
\begin{theorem}
If $f$ is TPD and $H$ is RO, Construction is CPA-secure.
\end{theorem}
\alert{$H$ can not be replaced by PRG, since the partial info on $r$ may be leaked by $c_1$.}
\end{frame}

\begin{frame}\frametitle{CCA-secure based on Private Key Encryption}
\textbf{Idea}: PubK CCA = PrivK CCA + (Secret Key = TPD + RO).  

\begin{columns}[t]
\begin{column}{5cm}
\begin{figure}[t]
\begin{center}
\input{tikz/tdp-cca1}
\end{center}
\end{figure}\end{column}
\begin{column}{5cm}
\begin{construction}
\begin{itemize}
\item $\Pi'$ is PrivK
\item $\mathsf{Gen}$: $pk = I$, $sk = \mathsf{td}$.
\item $\mathsf{Enc}$: $k := H(r), r \gets D_I$, output $\langle c_1= f_I(r), c_2 = \mathsf{Enc}'_k(m)\rangle$.
\item $\mathsf{Dec}$: $r := f^{-1}_{\mathsf{td}}(c_1)$, $k:=H(r)$, output $\mathsf{Dec}'_k(c_2)$.
\end{itemize}
\end{construction}

\end{column}
\end{columns}


\begin{theorem}
If $f$ is TDP, $\Pi'$ is CCA-secure, and $H$ is RO, Construction is CCA-secure.
\end{theorem}
\end{frame}
\begin{frame}\frametitle{CCA-secure based on TPD in ROM}
\textbf{Idea}: PubK CCA = TDP + 2 RO (one for enc, one for mac)
\begin{columns}[t]
\begin{column}{5cm}
\begin{figure}[t]
\begin{center}
\input{tikz/tdp-cca2}
\end{center}
\end{figure}\end{column}
\begin{column}{5cm}
\begin{construction}
\begin{itemize}
\item $\mathsf{Gen}$: $pk = I$, $sk = \mathsf{td}$
\item $\mathsf{Enc}$: $r \gets D_I$, output $\langle c_1=f_I(r), c_2 = H(r)\oplus m, c_3=G(c_2\|m)\rangle$
\item $\mathsf{Dec}$: $r := f^{-1}_{\mathsf{td}}(c_1)$, $m := H(r)\oplus c_2$. If $G(c_2\|m) = c_3$ output $m$, otherwise $\perp$
\end{itemize}
\end{construction}
\end{column}
\end{columns}
\begin{theorem}
If $f$ is TDP, $G,H$ are ROs, Construction is CCA-secure.
\end{theorem}
\end{frame}

\begin{frame}\frametitle{Private Key Encryption vs. Public Key Encryption}
\begin{center}
\begin{tabular}{|c|c|c|} \hline
   & \textbf{Private Key} & \textbf{Public Key}             \\ \hline
\textbf{Secret Key}               & both parties & receiver \\ \hline
\textbf{Weakest Attack}           & Eav          & CPA      \\ \hline
\textbf{Probabilistic}            & CPA/CCA      & always   \\ \hline
\textbf{Assumption against CPA}   & OWF          & TDP      \\ \hline
\textbf{Assumption against CCA}   & OWF          & TDP$+$RO   \\ \hline
\textbf{Efficiency}               & fast         & slow     \\ \hline
\end{tabular}	
\end{center}
\end{frame}
\end{document}