3.1privatekey.tex

\input{main.tex}

\title{Private-Key Encryption and Pseudorandomness (Part I)}

\begin{document}
\maketitle
\begin{frame}
\frametitle{Outline}
\tableofcontents
\end{frame}
\section{A Computational Approach to Cryptography}
\begin{frame}\frametitle{Idea of Computational Security}
Computational security vs. Information-theoretical security
\begin{alertblock}{Kerckhoffs's Another Principle}
A [cipher] must be practically, if not mathematically, indecipherable.
\end{alertblock}
\begin{itemize}
	\item Information-theoretical security: Perfect secrecy. \\
	\alert{Q: what's the limitation of perfect secrecy?}
	\item Computational security: 
\begin{itemize}
	\item Only preserved against adversaries that run in a \textbf{feasible amount of time}.
	\item Adversaries can succeed with some \textbf{very small probability}.
\end{itemize}
\end{itemize} 
\end{frame}
\begin{frame}\frametitle{Necessity of the Relaxations}
Limit the power of adversary (against brute force with pr. 1 in time linear in $|\mathcal{K}|$) and allow a negligible probability (against random guess with pr. $1/|\mathcal{K}|$).
\begin{figure}
\begin{center}
\input{tikz/compute-sec.tex}
\end{center}
\end{figure}
\end{frame}
%\begin{frame}\frametitle{Concrete Approach}
%A scheme is $(t,\varepsilon)$-\textbf{secure} if every adversary running for time at most $t$ succeeds in breaking the scheme with probability at most $\varepsilon$.
%\begin{exampleblock}{Example}
%\textbf{Optimal security}: when the key has length $n$, an adversary running in time $t$ can succeed with probability at most $t/2^n$.
%\begin{tabular}{ll}
%$t=2^{80}$ & $2^{20}$ 1GHz CPUs run 35 years. \\
%$n=128$   & $2^{170}$ atoms in the planet. \\
%$\varepsilon=2^{-48}$  & once every 100 years with probability $2^{-30}/\text{sec}$. \\
%\end{tabular}
%\end{exampleblock}
%\begin{itemize}
%\item But one may ask: What type of computing power? What if under Moore's Law? Which kind of  implementation? What is the success probability of running for 10 years? Does the key length matter? 
%\end{itemize}
%\end{frame}
\begin{frame}\frametitle{$\mathcal{P} = \mathcal{NP}$ ?}
\begin{figure}
\begin{center}
\input{tikz/pnp}
\end{center}
\end{figure}
\centerline{The majority of computer scientists believe $\mathcal{P} \ne \mathcal{NP}$.}
\centerline{\alert{\emph{This is very dangerous!}}} 
\end{frame}
\begin{frame}[fragile]\frametitle{Efficient Computation}
\begin{itemize}
\item An algorithm $A$ runs in \textbf{polynomial time} if there exists a polynomial $p(\cdot)$ such that,
 for every input $x \in {0,1}^*$, $A(x)$ terminates within at most $p(|x|)$ steps. \\
 \alert{Q: is $n!$ polynomial? is $\log n$ polynomial?}
\item $A$ can run another \textsc{ppt} $A'$ as a sub-routine in polynomial-time.\\
 \alert{Q: $f(x) = x^{2} $, is $g(x) =  \frac{x^{3}}{f(x)}$ polynomial?}
\item A \textbf{probabilistic} algorithm has the capability of ``tossing coins''.\\
Random number generators should be designed for cryptographic use, not \verb|random()| in C. 
\item Open question: Does probabilistic adversaries are more powerful than deterministic ones? 
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Negligible Success Probability}
\begin{itemize}
\item A function $f$ is \textbf{negligible} if for every polynomial $p(\cdot)$
there exists an $N$ such that for all integers $n > N$ it holds that $f(n) < \frac{1}{p(n)}$.
\item \alert{Q: is $\left( \frac{3}{n} \right)^{9}$ negligible? is $\frac{n^{2}}{2^{n}}$ negligible?}
\item \alert{Q: is $ \mathsf{negl}_1(n)+\mathsf{negl}_2(n)$ negligible?}
\item \alert{Q: is $ poly(n)\cdot\mathsf{negl}(n)$ negligible?}
%\item Problem $\mathsf{X}$ is \emph{hard} if $\mathsf{X}$ cannot be solved by any polynomial-time algorithm except with negligible probability.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Asymptotic Approach}
Problem $\mathsf{X}$ (breaking the scheme) is \emph{hard} if $\mathsf{X}$ cannot be solved by any polynomial-time algorithm for time $t$ except with negligible probability $\varepsilon$.
\begin{itemize}
\item $t, \varepsilon$ are described as functions of \textbf{security parameter} $n$ (usually, the length of key).%\item Probability is \textbf{negligible}: smaller than any inverse polynomial $n^{-b}$ for constant $b$.
\item \alert{Caution}: `Security' for large enough values of $n$.
\end{itemize}
\begin{exampleblock}{Example}
``Breaking the scheme'' with probability $2^{40}\cdot 2^{-n}$ in $n^3$ minutes.
\begin{tabular}{ll}
$n \le 40$ & 6 weeks with probability 1. \\
$n=50$   & 3 months with probability $1/1000$. \\
$n=500$  & more than 200 years with probability $2^{-500}$. \\
\end{tabular}\\

\alert{Q: What if under Moore's Law?} 
\end{exampleblock}
\end{frame}

%\begin{frame}\frametitle{Remarks on The Asymptotic Approach}
%\begin{itemize}
%\item The longer the key, the higher the security.
%\item Increasing $n$ to defend against increases in computing power.
%\item Convention: algorithm input is $1^n$. (a string of $n$ 1's)
%\end{itemize}
%\begin{exampleblock}{Example}
%\begin{tabular}{r|r|rr}
% & Honest party & \multicolumn{2}{|c}{Adversary} \\	\hline
%& $10^6 \cdot n^2$ & $10^8 \cdot n^4$ & $2^{20-n}$ \\
%1GHz $n=50$ & 2.5 sec.   & 1 week & $2^{-30}$ \\
%16GHz $n=500$ & 0.625 sec. & 16 week & $2^{-80}$ \\
%\end{tabular}
%
%\alert{Q: For a bigger $n$, is it harder or easier to break the cipher?}
%\end{exampleblock}
%\end{frame}
\section{Defining Computationally-Secure Encryption}
\begin{frame}\frametitle{Defining Private-key Encryption Scheme}
\begin{figure}
\begin{center}
\input{tikz/private-key}
\end{center}
\end{figure}
A \textbf{Private-key encryption scheme} $\Pi$ is a tuple of \textsc{ppt} $(\mathsf{Gen, Enc, Dec})$
\begin{itemize}
\item $k \gets \mathsf{Gen}(1^n), |k|\ge n$ (security parameter). \\
      $\mathsf{Gen}(1^n)$ chooses $k \gets \{0,1\}^n$ uniformly at random (\textbf{\emph{u.a.r}})
\item $c \gets \mathsf{Enc}_k(m), m \in \{0,1\}^*$ (all finite-length binary strings). \\
      \textbf{Fixed-length} if $m \in \{0,1\}^{\ell(n)}$
\item $m := \mathsf{Dec}_k(c)$
\item $\mathsf{Dec}_k(\mathsf{Enc}_k(m)) = m$
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Eavesdropping Indistinguishability Experiment}
The eavesdropping indistinguishability experiment $\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
	\item $\mathcal{A}$ is given input $1^n$, outputs $m_0, m_1$ of the same length
	\item $k \gets \mathsf{Gen}(1^n)$, a random bit $b \gets \{0,1\}$ is chosen. Then $c \gets \mathsf{Enc}_k(m_b)$ (challenge ciphertext) is given to $\mathcal{A}$
	\item $\mathcal{A}$ outputs $b'$. If $b' = b$, $\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\Pi}=1$, otherwise 0
\end{enumerate}
\begin{figure}
\begin{center}
\input{tikz/pri-eav-exp.tex}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Defining Private-key Encryption Security}
\begin{definition}\label{def:ind}
$\Pi$ has \textbf{indistinguishable encryptions in the presence of an eavesdropper} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ a negligible function $\mathsf{negl}$ such that
\[ \Pr\left[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n),
\]
where the probability it taken over the random coins used by $\mathcal{A}$.
\end{definition}
\end{frame}
\begin{frame}\frametitle{Understanding Definition of Indistinguishability}
\begin{exampleblock}{Is the OTP scheme indistinguishable in the presence of an eavesdropper?}
\end{exampleblock}
\begin{exampleblock}{If an adversary always fails in the experiments, is the scheme secure?}
\end{exampleblock}
\begin{exampleblock}{What's the probability of using the same key in two successive eavesdropping indistinguishability experiments?}
\end{exampleblock}
\begin{exampleblock}{If the lowest bit of message can be guessed from the ciphertext with probability $\frac{3}{4}$, is the scheme secure?}
%Q: what are two messages provided by the adversary?\\
%Q: what is the probability of success in this indistinguishability experiment?
\end{exampleblock}
\begin{exampleblock}{If the lowest 3 bits of message can be guessed from the ciphertext with probability $\frac{3}{8}$, is the scheme secure?}
\end{exampleblock}
%\begin{enumerate}
%\item \textbf{No single bit} can be guessed in a randomly-chosen plaintext with probability significantly better than $1/2$.
%\[ \Pr[\mathcal{A}(1^n,\mathsf{Enc}_k(m))=m^i] \le \frac{1}{2} + \mathsf{negl}(n).
%\]
%where $m^i$ is the $i$th bit of $m$, $\mathcal{A}(\cdot)$ outputs the guess.
%\item \textbf{No function of plaintext} can be learned regardless of the \emph{a priori} distribution over the plaintext. \\
%$\forall\;\mathcal{A}$, $\exists\;\mathcal{A'}$, $\forall\;f$ and $\forall\;S \in \{0,1\}^*$,
%\[ \left| \Pr[\mathcal{A}(1^n,\mathsf{Enc}_k(m)) = f(m)] - \Pr[\mathcal{A}'(1^n) = f(m)] \right| \le \mathsf{negl}(n),
%\]
%where $m \in S_n \overset{\text{def}}{=} S \cap \{0,1\}^n$.
%\end{enumerate}
\end{frame}
\begin{frame}\frametitle{Semantic Security}
\textbf{Intuition}: No partial information leaks.
\begin{definition}
$\Pi$ is \textbf{semantically secure in the presence of an eavesdropper} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists \mathcal{A'}$ such that $\forall$ distribution $X = (X_1, \dots)$ and $\forall f, h$,
\[ \left|\Pr[\mathcal{A}(1^n,\mathsf{Enc}_k(m),h(m))=f(m)]-\Pr[\mathcal{A}'(1^n,h(m))=f(m)]\right| 
\]
\[ \le \mathsf{negl}(n).
\]
where $m$ is chosen according to $X_n$, $h(m)$ is external information.
\end{definition}
\begin{theorem}
A private-key encryption scheme has \textbf{indistinguishable} encryptions in the presence of an eavesdropper $\iff$ it is \textbf{semantically secure} in the presence of an eavesdropper.
\end{theorem}
\end{frame}
\section{Pseudorandomness}
\begin{frame}\frametitle{Conceptual Points of Pseudorandomness}
\begin{itemize}
\item True randomness can not be generated by a describable mechanism
\item Pseudorandom looks truly random for the observers who don't know the mechanism 
\item No fixed string can be ``pseudorandom'' which refers to a distribution
\item \alert{Q: is it possible to definitively prove randomness?}
\end{itemize}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/random-color} 
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Distinguisher: Statistical Tests}
The pragmatic approach is to take many sequences of random numbers from a given generator and subject them to a battery of statistical tests.\footnote{State-of-the-art: NIST Special Publication 800-22 ``\emph{A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications}''}
\begin{exampleblock}{}
\begin{itemize}
\item $D(x)=0$ if $\left| \#0(x) - \#1(x)\right| \le 10\cdot \sqrt{n}$
\item $D(x)=0$ if $\left| \#00(x) - n/4\right| \le 10\cdot \sqrt{n}$
\item $D(x)=0$ if $\text{max-run-of-}0(x) \le 10\cdot \log{n}$
\end{itemize}
\end{exampleblock}
How many tests shall we need?
\end{frame}
\begin{frame}\frametitle{Intuition for Defining Pseudorandom}
\textbf{Intuition}: Generate a long string from a short truly random seed, and the pseudorandom string is indistinguishable from truly random strings.
\begin{figure}
\begin{center}
\input{tikz/prg-distinguisher.tex}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Definition of Pseudorandom Generators}
\begin{definition}\label{def:pg}
A deterministic polynomial-time algorithm $G : \{0,1\}^n \to \{0,1\}^{\ell(n)}$ is a \textbf{pseudorandom generator (PRG)} if
\begin{enumerate}
\item (Expansion:) $\forall n, \ell(n) > n$.
\item (Pseudorandomness): $\forall\;$ \textsc{ppt} distinguishers $D$,
\[ \left|\Pr[D(r)=1] - \Pr[D(G(s))=1]\right| \le \mathsf{negl}(n),
\]
where $r$ is chosen \emph{u.a.r} from $\{0,1\}^{\ell(n)}$, the \textbf{seed} $s$ is chosen \emph{u.a.r} from $\{0,1\}^n$. $\ell(\cdot)$ is the \textbf{expansion factor} of $G$.
\end{enumerate}
\end{definition}
\begin{itemize}
\item Pseudorandomness means being \textbf{next-bit unpredictable},\\
$G$ passes all next bit tests $\iff$ $G$ passes all statistical tests.
\item \textbf{Existence}: Under the weak assumption that \emph{one-way functions} exists, or $\mathcal{P} \ne \mathcal{NP}$
\end{itemize}
\end{frame}

\begin{frame}\frametitle{Problems on PRG}
\begin{exampleblock}{Is $G$ PRG?}
\begin{itemize}
\item $G: s \to \{0,1\}^n$ is such that for all $s$: $XOR(G(s)) = 1$
\item glibc random(): $r[i] = (r[i-3] + r[i-31])\%2^{32}$
\end{itemize}
\end{exampleblock}
\begin{exampleblock}{$F$ is PRG. Is $G$ PRG?}
\begin{itemize}
\item $G(s)=F(s)\oplus 1^{n}$
\item $G(s)=F(0)$
\item $G(s)=F(s)\| 0$
\item $G(s)=F(s\oplus 1^{\abs{s}})$
\item $G(s)=F(s)\| F(s)$
\item $G(s\| s')=F(s)\| F(s')$
\item $G: s \gets \{0,1\}^{20}, G(s) = F(s)$ (see next slide)
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Sufficient seed space}
\begin{itemize}
\item \textbf{Sparse outputs}: In the case of $\ell(n)=2n$, only $2^{-n}$ of strings of length $2n$ occurs.
\item \textbf{Brute force attack}: Given an unlimited amount of time, one can distinguish $G(s)$ from $r$ with a high probability by generating all strings with all seeds.
\[  \left|\Pr[D(r)=1] - \Pr[D(G(s))=1]\right| \ge 1-2^{-n} \]
\item \textbf{Sufficient seed space}: $s$ must be long enough against brute force attack.
\end{itemize}
\end{frame}
\section{Constructing Secure Encryption Schemes}
\begin{frame}\frametitle{A Secure Fixed-Length Encryption Scheme}
\begin{columns}[t]
\begin{column}{4cm}
\begin{figure}
\begin{center}
\input{tikz/encryptionwithpg}
\end{center}
\end{figure}
\end{column}
\begin{column}{6cm}
\begin{construction}\label{con:fl}
\begin{itemize}
\item $|G(k)| = \ell(|k|)$, $m \in \{0,1\}^{\ell(n)}$.
\item $\mathsf{Gen}$: $k \in \{0,1\}^n$.
\item $\mathsf{Enc}$: $c := G(k)\oplus m$.
\item $\mathsf{Dec}$: $m := G(k)\oplus c$.
\end{itemize}
\end{construction}
\begin{theorem}\label{the:flt}
This fixed-length encryption scheme has indistinguishable encryptions in the presence of an eavesdropper.
\end{theorem}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Reduction (Complexity)}
A \textbf{reduction} is a transformation of one problem $A$ into another problem $B$.
\newline

\textbf{Reduction} $A \le_m B$ \footnote{$m$ means the mapping reduction.} : $A$ is \textbf{reducible} to $B$ if solutions to $B$ exist and whenever given the solutions $A$ can be solved. \newline

Solving $A$ \textbf{cannot be harder} than solving $B$.
\begin{exampleblock}{Example}
\begin{itemize}
\item ``measure the area of a rectangle'' $\le_m$ ``measure the length and width of rectangle''
\item ``calculate $x^2$'' $\le_m$ ``calculate $x \times y$''
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Proofs of Reduction}
\begin{figure}
\begin{center}
\input{tikz/reduction}
\end{center}
\end{figure}
\begin{itemize}
\item A \textsc{ppt} $\mathcal{A}$ can break $\Pi$ with probability $\varepsilon(n)$.
\item \textbf{Assumption}: Problem $\mathsf{X}$ is \emph{hard} to solve.
\item \textbf{Reduction}: Reduce $\mathcal{A}'$ to $\mathcal{A}$. $\mathcal{A'}$ solves $\mathsf{x}$ efficiently with probability $1/p(n)$, running $\mathcal{A}$ as a sub-routine. 
\item \textbf{Contradiction}: If $\varepsilon(n)$ is non-negligible, then $\mathcal{A'}$ solves $\mathsf{X}$ efficiently with non-negligible probability $\varepsilon(n)/p(n)$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Proof of Indistinguishable Encryptions}
\textbf{Idea}: Use $\mathcal{A}$ to construct $D$ for $G$, so that $D$ distinguishes $G$ when $\mathcal{A}$ breaks $\tilde{\Pi}$. Since $D$ cannot distinguish $G$, so that $\mathcal{A}$ cannot break $\tilde{\Pi}$.
\begin{proof}
\begin{figure}
\begin{center}
\input{tikz/constructD}
\end{center}
\end{figure}
\[ \Pr[D(w)=1] = \Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\tilde{\Pi}}(n)=1] \]
\end{proof}
\end{frame}
\begin{frame}\frametitle{Proof of Indistinguishable Encryptions (Cont.)}
\begin{proof}
To prove $ \varepsilon(n) \overset{\text{def}}{=} \Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1] - \frac{1}{2} $ is negligible.\\
(1) If $w$ is $r$ chosen \emph{u.a.r}, then $\tilde{\Pi}$ is OTP. \[\Pr[D(r)=1] = \Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\tilde{\Pi}}(n)=1]=\frac{1}{2};\] \\
(2) If $w$ is $G(k)$, then $\tilde{\Pi} = \Pi$. 
\[ \Pr[D(G(k))=1] = \Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1] = \frac{1}{2} + \varepsilon(n). \]\\
Use Definition \ref{def:pg}: 
\[ \left|\Pr[D(r)=1] - \Pr[D(G(k))=1]\right| = \varepsilon(n) \le \mathsf{negl}(n).
\] 
\end{proof}
\end{frame}
\begin{frame}\frametitle{Handling Variable-Length Messages (homework)}
\begin{definition}\label{def:vlpg}
A \textbf{deterministic} polynomial-time algorithm $G$ is a \textbf{variable output-length pseudorandom generator} if
\begin{enumerate}
\item $G(s, 1^{\ell})$ outputs a string of length $\ell > 0$, where $s$ is a string.
\item $G(s, 1^{\ell})$ is a prefix of $G(s, 1^{\ell'})$, $\ell' > \ell$.\footnote{for technical reasons to prove security.}
\item $G_{\ell}(s) \overset{\text{def}}{=} G(s,1^{\ell(|s|)})$. Then $\forall \ell(\cdot)$, $G_{\ell}$ is a PRG with expansion factor $\ell$.
\end{enumerate}
\end{definition}
Both Construction \ref{con:fl} and Theorem \ref{the:flt} hold here.
\end{frame}
\begin{frame}\frametitle{Computational Security vs. Info.-theoretical Security}
\begin{center}
\begin{tabular}{|c|c|c|} \hline
                      & \textbf{Computational} & \textbf{Info.-theoretical} \\ \hline
\textbf{Adversary}    & \textsc{ppt} & no limited \\ 
                      & eavesdropping & eavesdropping\\ \hline 
\textbf{Definition}   & indistinguishable & indistinguishable \\ 
                      & $\frac{1}{2} + \mathsf{negl}$ & $\frac{1}{2}$ \\ \hline
\textbf{Assumption}   & pseudorandom & random   \\ \hline
\textbf{Key}	      & short random str. & long random str.\\ \hline
\textbf{Construction} & XOR pad & XOR pad \\ \hline 
\textbf{Prove}        & reduction & prob. theory  \\ \hline
\end{tabular}	
\end{center}
\end{frame}
\end{document}