crush-course.tex

\input{main.tex}

\title{A Crush Course On Cryptography}
\begin{document}
	\maketitle	
\begin{frame}\frametitle{What cryptography is and is not}
Cryptography is:
\begin{itemize}
\item A tremendous tool
\item The basis for many security mechanisms
\item Secure communication: 
\begin{itemize}
\item web traffic: HTTPS (SSL/TLS)
\item wireless traffic: 802.11i WPA2 (and WEP), GSM, Bluetooth
\item encrypting files on disk: EFS, TrueCrypt
\item content protection: DVD (CSS), Blu-ray (AACS)
\item user authentication
\end{itemize}
\end{itemize}
Cryptography is \textbf{NOT}:
\begin{itemize}
\item The solution to all security problems
\item Reliable unless implemented and used properly
\item Something you should try to invent yourself	
\end{itemize}
\end{frame}
\begin{frame}\frametitle{What cryptography can and can't do}
``No one can guarantee 100\% security. But we can work toward 100\% risk acceptance. $\dots$ Strong cryptography can withstand targeted attacks up to a point--the point at which it becomes easier to get the information some other way. $\dots$ The good news about cryptography is that we already have the algorithms and protocols we need to secure our systems. The bad news is that that was the easy part; implementing the protocols successfully requires considerable expertise. $\dots$  
Security is different from any other design requirement, because functionality does not equal quality.''
\newline

-- By Bruce Schneier 1997
\end{frame}
\begin{frame}\frametitle{Rubber-hose Cryptanalysis}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/rubberhose} 
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Outline}
\begin{itemize}
\item Classic cryptography, Perfect Secrets
\item Private Key Encryption, MAC, Block Cipher, OWF
\item Number Theory, Factoring and Discrete Log
\item Key Management, Public Key, Digital Signature
\item TPD, Random Oracle Model
\item Cryptographic Protocols (Many magics here)
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Syllabus [in Chinese]}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/syllabus} 
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{We will learn from Turing Award recipients}
\begin{itemize}
\item{1995} M. Blum
\item{2000} A. Yao
\item{2002} R. Rivest, A. Shamir, L. Adleman
\item{2012} S. Micali, S. Goldwasser
\item{2013} L. Lamport
\item{2015} M. E. Hellman, W. Diffie
\end{itemize}	
\end{frame}


\begin{frame}\frametitle{Securing Key vs Obscuring Algorithm}
\begin{itemize}
\item Easier to maintain secrecy of a short key
\item In case the key is exposed, easier for the honest parties to change the key
\item In case many pairs of people, easier to use the same algorithm, but different keys
\end{itemize}
\begin{alertblock}{Kerckhoffs's principle}
\begin{quote}
The cipher method must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience.
\end{quote}	
\end{alertblock}
\end{frame}

\begin{frame}\frametitle{The Syntax of Encryption}
\begin{figure}
\begin{center}
\input{tikz/private-key}
\end{center}
\end{figure}
\begin{itemize}
\item key $k \in \mathcal{K}$, plaintext (or message) $m \in \mathcal{M}$, ciphertext $c \in \mathcal{C}$
\item \textbf{Key-generation} algorithm~$k \gets \mathsf{Gen}$
\item \textbf{Encryption} algorithm~$c:= \mathsf{Enc}_k(m)$
\item \textbf{Decryption} algorithm~$m:= \mathsf{Dec}_k(c)$
\item \textbf{Encryption scheme}: $\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$
\item \textbf{Basic correctness requirement}: $\mathsf{Dec}_k(\mathsf{Enc}_k(m)) = m$
\end{itemize}
\end{frame}

\begin{frame}\frametitle{One-Time Pad (Vernam's Cipher)}

\begin{itemize}
	\item $\mathcal{M} = \mathcal{K} = \mathcal{C} = \{0,1\}^{\ell}$.
	\item $\mathsf{Gen}$ chooses a $k$ randomly with probability exactly $2^{-\ell}$.
	\item $c := \mathsf{Enc}_k(m) = k \oplus m$. 
	\item $m := \mathsf{Dec}_k(c) = k \oplus c$. 
\end{itemize}
\begin{theorem}
The one-time pad encryption scheme is perfectly-secret.
\end{theorem}
\end{frame}

\begin{frame}\frametitle{Definition of `Perfect Secrecy'}
\textbf{Intuition}: An adversary knows the probability distribution over $\mathcal{M}$. $c$ should have no effect on the knowledge of the adversary; the a \emph{posteriori} likelihood that some $m$ was sent should be no different from the a \emph{priori} probability that $m$ would be sent. 
\begin{definition}
$\Pi$ over $\mathcal{M}$ is \textbf{perfectly secret} if for every probability distribution over $\mathcal{M}$, $\forall m \in \mathcal{M}$ and $\forall c \in \mathcal{C}$ for which $\Pr[C = c] > 0$:
\[ \Pr[M=m | C=c] = \Pr[M=m].\]
\end{definition}
\textbf{Simplify}: non-zero probabilities for $\forall m \in \mathcal{M}$ and $\forall c \in \mathcal{C}$.\\

\begin{exampleblock}{Is the below scheme perfectly secret?}{ For $\mathcal{M}=\mathcal{K} = \{ 0,1 \} , \mathsf{Enc}_k(m)= m \oplus k$.}\end{exampleblock}
\end{frame}

\begin{frame}\frametitle{Two Time Pad: Real World Cases}
Only used once for the same key, otherwise
\[c\oplus c'=(m\oplus k)\oplus (m'\oplus k)=m\oplus m'.\]
Learn $m$ from $m\oplus m'$ due to the redundancy of language.
\begin{exampleblock}{MS-PPTP (Win NT)}
\begin{figure}
\begin{center}
\input{tikz/MS-PPTP.tex}
\end{center}
\end{figure}
Improvement: use two keys for C-to-S and S-to-C separately.
\end{exampleblock}
\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{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{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{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{Secure Multiple Encryptions Using a Stream Cipher}
\begin{figure}
\begin{center}
\input{tikz/synchronizedmode}
\end{center}
\end{figure}
Initial vector $IV$ is chosen \emph{u.a.r} and public\\
\alert{Q: which mode is better in your opinion?}
\end{frame}
\begin{frame}\frametitle{Related Keys: Real World Cases}
Keys (the $IV$-key pair) for multiple enc. must be independent
\begin{exampleblock}{Attacks on 802.11b WEP}
Unsynchronized mode: $\mathsf{Enc}(m_i) := \left< IV_i, G(IV_i\|k) \oplus m_i\right>$\\
\begin{itemize}
\item Length of $IV$ is 24 bits, repeat $IV$ after $2^{24} \approx$ 16M frames
\item On some WiFi cards, $IV$ resets to $0$ after power cycle
\item $IV_i = IV_{i-1} + 1$. For RC4, recover $k$ after 40,000 frames
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Chosen-Plaintext Attacks (CPA)}
\textbf{CPA}: the adversary has the ability to obtain the encryption of plaintexts of its choice
\begin{exampleblock}{A story in WWII}
\begin{itemize}
\item Navy cryptanalysts believe the ciphertext ``AF'' means ``Midway island'' in Japanese messages
\item But the general did not believe that Midway island would be attacked
\item Navy cryptanalysts sent a plaintext that the freshwater supplies at Midway island were low
\item Japanese intercepted the plaintext and sent a ciphertext that ``AF'' was low in water
\item The US forces dispatched three aircraft carriers and won
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Security Against CPA}
The CPA indistinguishability experiment $\mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
	\item $k \gets \mathsf{Gen}(1^n)$
	\item $\mathcal{A}$ is given input $1^n$ and \textbf{oracle access} $\mathcal{A}^{\mathsf{Enc}_k(\cdot)}$ to $\mathsf{Enc}_k(\cdot)$, outputs $m_0, m_1$ of the same length
	\item $b \gets \{0,1\}$. Then $c \gets \mathsf{Enc}_k(m_b)$ is given to $\mathcal{A}$
	\item $\mathcal{A}$ \textbf{continues to have oracle access} to $\mathsf{Enc}_k(\cdot)$, outputs $b'$
	\item If $b' = b$, $\mathcal{A}$ succeeded $\mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}=1$, otherwise 0
\end{enumerate}
\begin{figure}
\begin{center}
\input{tikz/pri-cpa-exp.tex}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Concepts on Pseudorandom Functions}
\begin{figure}
\begin{center}
\input{tikz/keyed-func.tex}
\end{center}
\end{figure}
\begin{itemize}
\item \textbf{Keyed function} $F : \{0,1\}^* \times \{0,1\}^* \to \{0,1\}^*$ \\
$F_k : \{0,1\}^* \to \{0,1\}^*$, $F_k(x) \overset{\text{def}}{=} F(k,x)$
\item \textbf{Look-up table $f$}: $\{0,1\}^n \to \{0,1\}^n$ with size \alert{ = ? bits} %$n\cdot2^n$.
\item \textbf{Function family $\mathsf{Func}_n$}: all functions $\{0,1\}^n \to \{0,1\}^n$. $|\mathsf{Func}_n| = 2^{n\cdot2^n}$
\item \textbf{Length Preserving}: $\ell_{key}(n) = \ell_{in}(n) = \ell_{out}(n)$
\end{itemize}
\end{frame}
\begin{frame}\frametitle{CPA-Security from Pseudorandom Function}
\begin{columns}[t]
\begin{column}{4cm}
\begin{figure}
\begin{center}
\input{tikz/encryptionwithpf}
\end{center}
\end{figure}
\end{column}
\begin{column}{6cm}
\begin{construction}\label{thm:cpa}
\begin{itemize}
\item Fresh random string $r$.
\item $F_k(r)$: $\abs{k} = \abs{m} = \abs{r} = n$.
\item $\mathsf{Gen}$: $k \in \{0,1\}^n$.
\item $\mathsf{Enc}$: $s := F_k(r)\oplus m$, $c := \left<r, s\right>$.
\item $\mathsf{Dec}$: $m := F_k(r)\oplus s$.
\end{itemize}
\end{construction}
\begin{theorem}\label{thm:prf}
If $F$ is a PRF, this fixed-length encryption scheme $\Pi$ is CPA-secure.
\end{theorem}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Pseudorandom Permutations}
\begin{itemize}
\item \textbf{Bijection}: $F$ is one-to-one and onto
\item \textbf{Permutation}: A bijective function from a set to itself
\item \textbf{Keyed permutation}: $\forall k, F_k(\cdot)$ is permutation
\item $F$ is a bijection $\iff F^{-1}$ is a bijection
\end{itemize}
\begin{definition}
An efficient, keyed permutation $F$ is a \textbf{strong pseudorandom permutation (PRP)} if
$\forall\;$ \textsc{ppt} distinguishers $D$,
\[ \left|\Pr[D^{F_k(\cdot),F_k^{-1}(\cdot)}(1^n)=1] - \Pr[D^{f(\cdot),f^{-1}(\cdot)}(1^n)=1]\right| \le \mathsf{negl}(n),
\]
where $f$ is chosen \emph{u.a.r} from the set of permutations on $n$-bit strings.
\end{definition}
\begin{alertblock}{If $F$ is a pseudorandom permutation then is it a PRF?}
\end{alertblock}
\end{frame}
\begin{frame}\frametitle{Electronic Code Book (ECB) Mode}
\begin{figure}
\begin{center}
\input{tikz/ECB}
\end{center}
\end{figure}
\begin{itemize}
\item \alert{Q: is it indistinguishable in the presence of an eavesdropper?}
\item \alert{Q: can $F$ be any PRF?}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Attack on ECB mode}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/ecb} 
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Cipher Block Chaining (CBC) Mode}
\begin{figure}
\begin{center}
\input{tikz/CBC}
\end{center}
\end{figure}
\begin{itemize}
\item $IV$: initial vector, a fresh random string.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Output Feedback (OFB) Mode}
\begin{figure}
\begin{center}
\input{tikz/OFB}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Counter (CTR) Mode}
\begin{figure}
\begin{center}
\input{tikz/CTR}
\end{center}
\end{figure}
\end{frame}

\begin{frame}[fragile]\frametitle{$IV$ Should Not Be Predictable}
If $IV$ is predictable, then CBC/OFB/CTR mode is not CPA-secure.\\
\begin{exampleblock}{Bug in SSL/TLS 1.0}
$IV$ for record $\#i$ is last CT block of record $\#(i-1)$.
\end{exampleblock}
\begin{exampleblock}{API in OpenSSL}
\verb#void AES_cbc_encrypt (# \\
\verb#    const unsigned char *in,# \\
\verb#    unsigned char       *out,# \\
\verb#    size_t              length,# \\
\verb#    const AES_KEY       *key,# \\
\verb#    unsigned char       *ivec,   #  \alert{\textbf{User supplies $IV$}} \\
\verb#    AES_ENCRYPT or AES_DECRYPT);# \\
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Security Against CCA}
The CCA indistinguishability experiment $\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
	\item $k \gets \mathsf{Gen}(1^n)$.
	\item $\mathcal{A}$ is given input $1^n$ and oracle access $\mathcal{A}^{\mathsf{Enc}_k(\cdot)}$ and $\mathcal{A}^{\mathsf{Dec}_k(\cdot)}$, outputs $m_0, m_1$ of the same length.
	\item $b \gets \{0,1\}$. $c \gets \mathsf{Enc}_k(m_b)$ is given to $\mathcal{A}$.
	\item $\mathcal{A}$ continues to have oracle access \alert{\textbf{except for $c$}}, outputs $b'$.
	\item If $b' = b$, $\mathcal{A}$ succeeded $\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}=1$, otherwise 0.
\end{enumerate}
\begin{itemize}
\item In real world, the adversary might conduct CCA by influencing what gets decrypted
\begin{itemize}
\item If the communication is not authenticated, then an adversary may send certain ciphertexts on behalf of the honest party
\end{itemize}
\item CCA-security implies ``\textbf{non-malleability}''
\item None of the above scheme is CCA-secure
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Padding-Oracle Attacks} 
\begin{itemize}
\item In a one-block CBC, by modifying the 1st byte of $IV$, attacker can learn whether $m$ is NULL. If yes, error will occur. 
\end{itemize}
\begin{columns}[c]
\column{.5\textwidth}
\begin{figure}
\begin{center}
\input{tikz/CBC-small}
\end{center}
\end{figure}
\column{.5\textwidth}
\begin{itemize}
\item append $\{b\}^b$ as a dummy block if $m$ is NULL
\item change the 1st byte of $IV$ from $x$ to $y$, get decrypted block $(x \oplus y \oplus b) \| \{b\}^{b-1}$, and trigger an error
\end{itemize}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Padding-Oracle Attacks (Cont.)}
\begin{figure}
\begin{center}
\input{tikz/CBC-small}
\end{center}
\end{figure}
\begin{itemize}
\item If no error, then learn whether $m$ is 1 byte by modifying the 2nd byte of $IV$ and so on (changing the ciphertext)
\item Once learn the length of $m$, learn the last byte of $m$ ($s$) by modifying the one before the last block in the ciphertext
\item $m_{last} = \cdots s \| \{b\}^{b}$, $c_{last-1} = \cdots t \| \{\cdot \}^{b} $
\item modify $c_{last-1}$ to $c_{last-1}' = \cdots u \| (\{\cdot \}^{b} \oplus \{b\}^{b} \oplus \{b+1\}^{b}) $
\item \alert{Q: If no padding error, then $s$ = ?}
% s ^ t = u  ^ (b+1),  s= u ^ (b+1) ^ t
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Padding-Oracle Attacks: Real-world Case}
CAPTCHA server will return an error when deciphering the CT of a CAPTCHA text received from a user.
\begin{figure}
\begin{center}
\input{tikz/padding-oracle}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Comics on S-box [xkcd:153]}
If you got a big keyspace, let me search it.
\begin{figure}
\begin{center}
\includegraphics[width=70mm]{pic/sbox-talk} 
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Chronology of DES}
\begin{description}
\item[1973] NBS (NIST) publishes a call for a standard.
\item[1974] DES is published in the Federal Register.
\item[1977] DES is published as FIPS PUB 46.
\item[1990] Differential cryptanalysis with CPA of $2^{47}$ plaintexts. 
\item[1997] DESCHALL Project breaks DES in public.
\item[1998] EFF's Deep Crack breaks DES in 56hr at \$250,000.
\item[1999] Triple DES.
\item[2001] AES is published in FIPS PUB 197.
\item[2004] FIPS PUB 46-3 is withdrawn.
\item[2006] COPACOBANA breaks DES in 9 days at \$10,000.
\item[2008] RIVYERA breaks DES within one day.
\end{description}
\end{frame}
\begin{frame}\frametitle{AES -- The Advanced Encryption Standard}
\begin{itemize}
\item In 1997, NIST calls for AES.
\item In 2001, Rijndael [J. Daemen \& V. Rijmen] becomes AES.
\item The first publicly accessible cipher for top secret information.
\item Not only security, also efficiency and flexibility, etc.
\item 128-bit block length and 128-, 192-, or 256-bit keys.
\item Not a Feistel structure, but a SPN.
\item Only non-trivial attacks are for reduced-round variants.
\begin{itemize}
\item $2^{27}$ on 6-round of 10-round for 128-bit keys.
\item $2^{188}$ on 8-round of 12-round for 192-bit keys.
\item $2^{204}$ on 8-round of 14-round for 256-bit keys. 
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Remarks on Block Ciphers}
\begin{itemize}
\item \textbf{Block length} should be sufficiently large
\item \textbf{Message tampering} is not with message confidentiality
\item \textbf{Padding}: TLS: For $n>0$, $n$ byte pad is $n,n,\dots,n$
If no pad needed, add a dummy block
\item \textbf{Stream ciphers vs. block ciphers}: 
\begin{itemize}
\item Steam ciphers are faster but have lower security
\item It is possible to use block ciphers in ``stream-cipher mode''
\end{itemize}
\end{itemize}
\begin{exampleblock}{Performance: Crypto++ 5.6, AMD Opetron 2.2GHz}
\begin{center}
\begin{tabular}{|c|c|c|} \hline
                      & \textbf{Block/key size} & \textbf{Speed MB/sec} \\ \hline
\textbf{RC4}          &         & 126 \\  
\textbf{Salsa20/12}   &         & 643 \\ 
\textbf{Sosemanuk}    &         & 727 \\ 
\textbf{3DES}	      & 64/168  & 13  \\
\textbf{AES-128}      & 128/128 & 109 \\ \hline 
\end{tabular}	
\end{center}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{One-Way Functions (OWF)}
\begin{figure}
\begin{center}
\input{tikz/OWF}
\end{center}
\end{figure}
The inverting experiment $\mathsf{Invert}_{\mathcal{A},f}(n)$:
\begin{enumerate}
\item Choose input $x \gets \{0,1\}^n$. Compute $y := f(x)$.
\item $\mathcal{A}$ is given $1^n$ and $y$ as input, and outputs $x'$.
\item $\mathsf{Invert}_{\mathcal{A},f}(n) = 1$ if $f(x')=y$, otherwise 0.
\end{enumerate}
\end{frame}
\begin{frame}\frametitle{Candidate One-Way Function}
\begin{itemize}
\item \textbf{Multiplication and factoring}:\\
$f_{\mathsf{mult}}(x,y)=(xy,\|x\|,\|y\|)$, $x$ and $y$ are equal-length primes.
\item \textbf{Modular squaring and square roots}:\\
$f_{\mathsf{square}}(x)=x^2\bmod N$.
\item \textbf{Discrete exponential and logarithm}:\\
$f_{g,p}(x)=g^x\bmod p$.
\item \textbf{Subset sum problem}:\\
$f(x_1,\dotsc,x_n,J)=(x_1,\dotsc,x_n,\sum_{j \in J} x_j)$.
\item \textbf{Cryptographically secure hash functions}:\\
Practical solutions for one-way computation.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Theoretical Constructions of Pseudorandom Objects}
\begin{figure}
\begin{center}
\input{tikz/owfover}
\end{center}
\end{figure}
\begin{alertblock}{One of contributions of modern cryptography}
The existence of one-way functions is equivalent to the existence of all (non-trivial) private-key cryptography.
\end{alertblock}
\end{frame}
\begin{frame}\frametitle{Integrity and Authentication}
\begin{figure}
\begin{center}
\input{tikz/integrity}
\input{tikz/authentication}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{The Syntax of MAC}
\begin{figure}
\begin{center}
\input{tikz/mac}
\end{center}
\end{figure}
\begin{itemize}
\item key $k$, tag $t$, a bit $b$ means $\mathsf{valid}$ if $b=1$; $\mathsf{invalid}$ if $b=0$.
\item \textbf{Key-generation} algorithm~$k \gets \mathsf{Gen}(1^n), \abs{k} \ge n$.
\item \textbf{Tag-generation} algorithm~$t \gets \mathsf{Mac}_k(m)$.
\item \textbf{Verification} algorithm~$b:= \mathsf{Vrfy}_k(m,t)$.
\item \textbf{Message authentication code}: $\Pi = (\mathsf{Gen}, \mathsf{Mac}, \mathsf{Vrfy})$.
\item \textbf{Basic correctness requirement}: $\mathsf{Vrfy}_k(m,\mathsf{Mac}_k(m)) = 1$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Security of MAC}
\begin{itemize}
\item \textbf{Intuition}: No adversary should be able to generate a \textbf{valid} tag on any ``\textbf{new}'' message\footnote{A stronger requirement is concerning \emph{new message/tag pair}.} that was not previously sent.
\item \textbf{Replay attack}: Copy a message and tag previously sent. (\textbf{excluded by only considering ``new'' message})
\begin{itemize}
\item Sequence numbers: receiver must store the previous ones.
\item Time-Stamps: sender/receiver maintain synchronized clocks.
\end{itemize}
\item \textbf{Existential unforgeability}: \textbf{Not} be able to forge a valid tag on \textbf{any} message.
\begin{itemize}
\item \textbf{Existential forgery}: \emph{at least one} message.
\item \textbf{Selective forgery}: message chosen \emph{prior} to the attack.
\item \textbf{Universal forgery}: \emph{any} given message.
\end{itemize}
\item \textbf{Adaptive chosen-message attack (CMA)}: be able to obtain tags on \emph{any} message chosen adaptively \emph{during} its attack.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Definition of MAC Security}
The message authentication experiment $\mathsf{Macforge}_{\mathcal{A},\Pi }(n)$:
\begin{enumerate}
\item $k \gets \mathsf{Gen}(1^n)$.
\item $\mathcal{A}$ is given input $1^n$ and oracle access to $\mathsf{Mac}_k(\cdot)$, and outputs $(m,t)$. $\mathcal{Q}$ is the set of queries to its oracle.
\item $\mathsf{Macforge}_{\mathcal{A},\Pi }(n)=1 \iff$ $\mathsf{Vrfy}_k(m,t)=1$ $\land$ $m \notin \mathcal{Q}$. 
\end{enumerate}
\begin{figure}
\begin{center}
\input{tikz/macforge-exp.tex}
\end{center}
\end{figure}
\begin{definition}
A MAC $\Pi$ is \textbf{existentially unforgeable under an adaptive CMA} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that:
\[ \Pr [\mathsf{Macforge}_{\mathcal{A},\Pi }(n)=1] \le \mathsf{negl}(n).
\]
\end{definition}
\end{frame}
\begin{frame}\frametitle{Constructing Fixed-Length CBC-MAC}
\begin{columns}[c]
\column{.5\textwidth}
\begin{figure}
\begin{center}
\input{tikz/CBC-small}
\end{center}
\end{figure}
\column{.5\textwidth}
\begin{figure}
\begin{center}
\input{tikz/CBC-MAC}
\end{center}
\end{figure}
\end{columns}
Modify CBC encryption into CBC-MAC:
\begin{itemize}
\item Change random $IV$ to encrypted fixed $0^{n}$,\emph{otherwise}:\\
\alert{Q: query $m_1$ and get $(IV, t_1)$; output $m_1' = IV' \oplus  IV \oplus m_{1}$ and $t' =$ \underline{$\qquad $}.} %(IV',t_1)$.
\item Tag only includes the output of the final block,\emph{otherwise}:\\
\alert{Q: query $m_i$ and get $t_i$; output $m_i' = t_{i-1}' \oplus t_{i-1} \oplus m_{i}$ and $t_{i}' = $ \underline{$\qquad$}.}%$t_i$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Secure Variable-Length MAC}
\begin{itemize}
\item \textbf{Input-length key separation}: $k_{\ell} := F_k(\ell)$, use $k_{\ell}$ for CBC-MAC.
\item \textbf{Length-prepending}: Prepend $m$ with $|m|$, then use CBC-MAC.
\begin{figure}
\begin{center}
\input{tikz/VCBC-MAC}
\end{center}
\end{figure}
\item \textbf{Encrypt last block (ECBC-MAC)}: Use two keys $k_1, k_2$. Get $t$ with $k_1$ by CBC-MAC, then output $\hat{t} := F_{k_2}(t)$.
\end{itemize}
\alert{Q: To authenticate a voice stream, which approach do you prefer?}
\end{frame}
\begin{frame}\frametitle{Weaker Notions of Security for Hash Functions}
\begin{figure}
\begin{center}
\input{tikz/collision}
\end{center}
\end{figure}
\begin{itemize}
\item \textbf{Collision resistance}: It is hard to find $(x, x'), x' \ne x$ such that $H(x) = H(x')$.
\item \textbf{Second pre-image resistance}: Given $s$ and $x$, it is hard to find $x' \ne x$ such that $H^s(x') = H^s(x)$.
\item \textbf{Pre-image resistance}: Given $s$ and $y = H^s(x)$, it is hard to find $x'$ such that $H^s(x')=y$.
\end{itemize}
\end{frame}
\begin{frame}{Applications of Hash Functions}
\begin{itemize}
\item \textbf{Fingerprinting and Deduplication}: $H(alargefile)$ for virus fingerprinting, deduplication, P2P file sharing
\item \textbf{Merkle Trees}: $H(H(H(file1), H(file2)), H(H(file3), H(file4)))$ fingerprinting multiple files / parts of a file
\item \textbf{Passward Hashing}: $(salt, H(salt, pw))$ mitigating the risk of leaking password stored in the clear 
\item \textbf{Key Derivation}: $H(secret)$ deriving a key from a high-entropy (but not necessarily uniform) shared secret
\item \textbf{Commitment Schemes}: $H(info)$ hiding the commited info; binding the commitment to a info
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Hash-based MAC (HMAC)}
\begin{figure}
\begin{center}
\input{tikz/HMAC}
\end{center}
\end{figure}
\begin{construction}
$(\widetilde{\mathsf{Gen}}, h)$ is a fixed-length CRHF. $(\widetilde{\mathsf{Gen}}, H)$ is the Merkle-Damg\r{a}rd transform.
$IV$, $\mathsf{opad}$ (0x36), $\mathsf{ipad}$ (0x5C) are fixed constants of length $n$.
HMAC:
\begin{itemize}
\item $\mathsf{Gen}(1^n)$: Output $(s, k)$. $s \gets \widetilde{\mathsf{Gen}}, k \gets \{0,1\}^n$ \emph{u.a.r}
\item $\mathsf{Mac}_{s,k}(m)$: $t := H_{IV}^s\Big((k \oplus \mathsf{opad}) \| H_{IV}^s\big((k \oplus \mathsf{ipad}) \| m\big)\Big)$
\item $\mathsf{Vrfy}_{s,k}(m,t)$: $1 \iff t \overset{?}{=} \mathsf{Mac}_{s,k}(m)$
\end{itemize}
\end{construction}
\end{frame}
\begin{frame}\frametitle{Security of HMAC}
\begin{theorem}
\[ G(k) \overset{\text{def}}{=} h^s(IV\| (k\oplus \mathsf{opad})) \| 
h^s(IV\| (k\oplus \mathsf{ipad})) = k_1\| k_2
\]
$(\widetilde{\mathsf{Gen}}, h)$ is CRHF. If $G$ is a PRG, then HMAC is secure.
\end{theorem}
\begin{itemize}
\item HMAC is an industry standard (RFC2104)
\item HMAC is faster than CBC-MAC
\item Before HMAC, a common mistake was to use $H^s(k\| x)$
\item \alert{Verification timing attacks: (Keyczar crypto library (Python))} \\
def Verify(key, msg, sig\underline{\ }bytes): \\
$\qquad$ return HMAC(key, msg) == sig\underline{\ }bytes \\
The problem:  implemented as a byte-by-byte comparison
\item \alert{\emph{Don't implement it yourself}}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Combining Encryption and Authentication}
\begin{figure}
\begin{center}
\input{tikz/combination}
\end{center}
\end{figure}
\begin{itemize}
\item \textbf{Encrypt-and-authenticate} (e.g., SSH):\[ c \gets \mathsf{Enc}_{k_1}(m),\; t \gets \mathsf{Mac}_{k_2}(m).\]
\item \textbf{Authenticate-then-encrypt} (e.g, SSL):\[ t \gets \mathsf{Mac}_{k_2}(m),\; c \gets \mathsf{Enc}_{k_1}(m\| t).\]
\item \textbf{Encrypt-then-authenticate} (e.g, IPsec):\[ c \gets \mathsf{Enc}_{k_1}(m),\; t \gets \mathsf{Mac}_{k_2}(c). \]
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Analyzing Security of Combinations}
\textbf{All-or-nothing}: Reject any combination for which there exists even a single counterexample is insecure.
\begin{itemize}
\item \textbf{Encrypt-and-authenticate}: $\mathsf{Mac}'_k(m) = (m, \mathsf{Mac}_k(m))$.
\item \textbf{Authenticate-then-encrypt}: 
\begin{itemize}
\item $\mathsf{Trans}: 0 \to 00; 1 \to 10/01$; $\mathsf{Enc}'$ uses CTR mode; $c = \mathsf{Enc}'(\mathsf{Trans}(m\| \mathsf{Mac}(m)))$.
\item Flip the first two bits of $c$ and verify whether the ciphertext is valid.
$10/01 \to 01/10 \to 1$, $00 \to 11 \to \bot$.
\item If valid, the first bit of message is 1; otherwise 0.\\
\item For any MAC, this is not CCA-secure.
\end{itemize}
\item \textbf{Encrypt-then-authenticate}: \\
Decryption: If $\mathsf{Vrfy}(\cdot) = 1$, then $\mathsf{Dec}(\cdot)$; otherwise output $\bot$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Authenticated Encryption Theory and Practice}
\begin{theorem}
$\Pi_E$ is CPA-secure and $\Pi_E$ is a secure MAC with unique tages, $\Pi'$ deriving from encrypt-then-authenticate approach is secure.
\end{theorem}
\textbf{GCM(Galois/Counter Mode)}: CTR encryption then Galois MAC. (RFC4106/4543/5647/5288 on IPsec/SSH/TLS)\\
\textbf{EAX}: CTR encryption then CMAC.
\begin{proposition}
Authenticate-then-encrypt approach is secure if $\Pi_E$ is rand-CTR mode or rand-CBC mode.
\end{proposition}
\textbf{CCM (Counter with CBC-MAC)}: CBC-MAC then CTR encryption. (802.11i, RFC3610)\\
\textbf{OCB (Offset Codebook Mode)}: integrating MAC into ENC. (two times fast as CCM, EAX)\\
\textbf{All support AEAD (A.E. with associated data):} part of message is in clear, and all is authenticated
\end{frame}
\begin{frame}\frametitle{Remarks on Secure Message Transmission}
\begin{itemize}
\item Authentication may leak the message.
\item Secure message transmission implies CCA-security. The opposite direction is not necessarily true.
\item Different security goals should always use different keys.
\begin{itemize}
\item otherwise, the message may be leaked if $\mathsf{Mac}_k(c)=\mathsf{Dec}_k(c)$.
\end{itemize}
\item Implementation may destroy the security proved by theory.
\begin{itemize}
\item \textbf{Attack with padding oracle} (in TLS 1.0): \\
\textbf{Dec} return two types of error: padding error, MAC error. \\
\textbf{Adv.} learns last bytes if no padding error with guessed bytes. 
\item \textbf{Attack non-atomic dec.} (in SSH Binary Packet Protocol):\\
\textbf{Dec} (1)decrypt length field; (2)read packets as specified by the length; (3)check MAC. \\
\textbf{Adv.} (1)send $c$; (2)send $l$ packets until ``MAC error'' occurs; (3)learn $l = \mathsf{Dec}(c)$. 
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{ Password-Based KDF (PBKDF)}
\textbf{Key stretching} increases the time of testing key (with slow hash function).
\newline

\textbf{Key strengthening} increases the length/randomness of key (with salt).
\newline

\textbf{PKCS\#5 (PBKDF1)}: $H^{(c)}(pwd\|salt)$, iterate hash function $c$ times.
\newline

\textbf{Attack}: either try the enhanced key (larger key space), or else try the initial key (longer time per key).
\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{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{Trapdoor Permutations}
\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{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{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}{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}
\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}
\begin{frame}\frametitle{RSA Overview}
\begin{itemize}
\item \textbf{RSA}: Ron Rivest, Adi Shamir and Leonard Adleman, in 1977
\item \textbf{RSA problem}: Given $N = pq$ (two distinct big prime numbers) and $y \in \mathbb{Z}^*_N$, compute $y^{-e}$, $e^{\text{th}}$-root of $y$ modulo $N$
\item \alert{Open problem}:RSA problem is easier than factoring $N$?
\item \textbf{Certification}: PKCS\#1 (RFC3447), ANSI X9.31, IEEE 1363
\item \textbf{Key sizes}: 1,024 to 4,096 bit
\item \textbf{Best public cryptanalysis}: a 768 bit key has been broken
\item \textbf{RSA Challenge}: break RSA-2048 to win \$200,000 USD
\end{itemize}
\textbf{Key lengths} with comparable security :
\begin{center}
\begin{tabular}{|c|c|} \hline
Symmetric & RSA  \\ \hline
80 bits & 1024 bits   \\
128 bits & 3072 bits  \\
256 bits & 15360 bits \\ \hline
\end{tabular}	
\end{center}
\end{frame}
\begin{frame}\frametitle{``Textbook RSA''}
\begin{construction}
\begin{itemize}
\item $\mathsf{Gen}$: on input $1^n$ run $\mathsf{GenRSA}(1^n)$ to obtain $N,e,d$. $pk = \langle N,e \rangle$ and $sk = \langle N,d \rangle$.
\item $\mathsf{Enc}$: on input $pk$ and $m \in \mathbb{Z}^*_N$, $c:= [m^e \bmod N]$.
\item $\mathsf{Dec}$: on input $sk$ and $m \in \mathbb{Z}^*_N$, $m:= [c^d \bmod N]$.
\end{itemize}
\end{construction}
\begin{alertblock}{Insecurity}
Since the ``textbook RSA'' is deterministic, it is insecure with respect to any of the definitions of security we have proposed. 
\end{alertblock}
\end{frame}
\begin{frame}\frametitle{PKCK \#1 v2.1 (RSAES-OAEP) (Cont.)}
RSA-OAEP is CCA-secure in Random Oracle model. \footnote{It may not be secure when RO is instantiated.} [RFC 3447]
\begin{figure}
\begin{center}
\input{tikz/OAEP}
\end{center}
\end{figure}
CPA: To learn $r$, attacker has to learn $\hat{m}_1$ from $(\hat{m}_1\|\hat{m})^e$\\

CCA: Effective decryption query is disabled by checking "00...0" in the plaintext before the response\\

\end{frame}

\begin{frame}\frametitle{OAEP Improvements}
\begin{columns}
\begin{column}{5cm}
\begin{figure}
\begin{center}
\input{tikz/OAEP-plus}
\input{tikz/SAEP-plus}
\end{center}
\end{figure}
\end{column}
\begin{column}{5cm}
\textbf{OAEP+}: $\forall $ trap-door permutation F, F-OAEP+ is CCA-secure.\newline

\textbf{SAEP+}: RSA (e=3) is a trap-door permutation, RSA-SAEP+ is CCA-secure.\newline

$W, G, H$ are Random Oracles.
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Implementation Attacks on RSA}
\begin{exampleblock}{Simplified CCA on PKCS1 v1.5 in HTTPS [Bleichenbacher]}
Server tells if the MSB of plaintext (Version Number) = `1' for a given ciphertext. Attacker sends $c' = (2^{r})^{e}\cdot c$. If receiving $Yes$, then \alert{$(r+1)$-th $MSB(m)$ = ?}
\begin{figure}
\begin{center}
\input{tikz/CCA-PKCS.tex}
\end{center}
\end{figure}
\end{exampleblock}
\textbf{Defense}: treating incorrectly formatted message blocks in a manner indistinguishable from correctly formatted blocks. See [RFC 5246]
\end{frame}
\begin{frame}\frametitle{Implementation Attacks on RSA (Cont.) }
\textbf{Timing attack}: [Kocher et al. 1997] 
The time it takes to compute $c^d$ can expose $d$. (require a high-resolution clock)\\
\textbf{Power attack}: [Kocher et al. 1999]
The power consumption of a smartcard while it is computing $c^d$ can expose $d$.\\
\textbf{Defense}: \textbf{Blinding} by choosing a random $r$ and deciphering $r^{e}\cdot c$. 
\newline

\textbf{Key generation trouble} (in OpenSSL RSA key generation):\\
Same $p$ will be generated by multiple devices (due to poor entropy at startup), but different $q$ (due to additional randomness).\\
\alert{Q: $N_1,N_2$ from different devices, $\gcd(N_1,N_2) = ?$}\\
Experiment result: factor 0.4\% of public HTTPS keys.
\end{frame}
\begin{frame}\frametitle{Faults Attack on RSA}
\textbf{Faults attack}:
A computer error during $c^d\bmod N$ can expose $d$.\newline

Using Chinese Remainder Theory to speed up the decryption:
\[ [c^d \bmod N] \leftrightarrow ([m_p \equiv c^d \pmod p],[m_q \equiv c^d \pmod q]).\]
\textbf{Suppose error occurs when computing $m_q$, but no error in $m_p$.}\newline

Then output $m' \equiv c^d \pmod p$, $m' \not \equiv c^d \pmod q$.\\
So $(m')^e \equiv c \pmod p$, $(m')^e \not \equiv c \pmod q$.\\
\alert{\[\gcd((m')^e-c, N)=\ ?\]}

\textbf{Defense}: check output. (but 10\% slowdown)
\end{frame}
\begin{frame}\frametitle{Diffie-Hellman Assumptions}
\begin{itemize}
\item \textbf{Computational Diffie-Hellman (CDH)} problem:
\[ \mathsf{DH}_g(h_1,h_2) \overset{\text{def}}{=} g^{\log_gh_1\cdot \log_gh_2}\]
\item \textbf{Decisional Diffie-Hellman (DDH)} problem:	\\
Distinguish $\mathsf{DH}_g(h_1,h_2)$ from a random group element $h'$.
\end{itemize}
\begin{definition}
DDH problem is hard relative to $\mathcal{G}$ if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[  \abs{\Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^z)=1] - \Pr[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]}\]
\[ \le \mathsf{negl}(n). \]
\end{definition}
\begin{alertblock}{Intractability of DL, CDH and DDH}
DDH is easier than CDH and DL.
\end{alertblock}
\end{frame}
\begin{frame}\frametitle{Diffie-Hellman Key-Exchange Protocol}
\begin{columns}[]
\begin{column}{5cm}
\begin{figure}
\begin{center}
\input{tikz/DHkey}
\end{center}
\end{figure}
\end{column}
\begin{column}{6cm}
\alert{Q: $k_A = k_B = k = ?$}
\newline
	
$\widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi}$ denote an experiment where if $b=0$ the adversary is given $\hat{k} \gets \mathbb{G}$.
\begin{theorem}
If DDH problem is hard relative to $\mathcal{G}$, then DH key-exchange protocol $\Pi$ is secure in the presence of an eavesdropper (with respect to the modified experiment $\widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi}$). 
\end{theorem}
\end{column}
\end{columns}
\begin{alertblock}{Security}
Insecurity against active adversaries (Man-In-The-Middle).
\end{alertblock}
\end{frame}
\begin{frame}{Digital Signatures -- An Overview}
\begin{itemize}
\item \textbf{Digital signature scheme} is a mathematical scheme for demonstrating the authenticity/integrity of a digital message
\item allow a \textbf{signer} $S$ to ``\textbf{sign}'' a message with its own $sk$, anyone who knows $S$'s $pk$ can \textbf{verify} the authenticity/integrity
\item (Comparing to MAC) digital signature is:
\begin{itemize}
\item publicly verifiable
\item transferable
\item non-repudiation
\item but slow
\end{itemize}
\item \alert{Q: What are the differences between digital signatures and handwritten signatures?}
\item Digital signature is NOT the ``inverse'' of public-key encryption
\end{itemize}
\end{frame}
\begin{frame}\frametitle{The Syntax of Digital Signature Scheme}
\begin{figure}
\begin{center}
\input{tikz/digitalsignature}
\end{center}
\end{figure}
\begin{itemize}
\item signature $\sigma$, a bit $b$ means $\mathsf{valid}$ if $b=1$; $\mathsf{invalid}$ if $b=0$.
\item \textbf{Key-generation} algorithm~$(pk,sk) \gets \mathsf{Gen}(1^n), \abs{pk},\abs{sk} \ge n$.
\item \textbf{Signing} algorithm~$\sigma \gets \mathsf{Sign}_{sk}(m)$.
\item \textbf{Verification} algorithm~$b:= \mathsf{Vrfy}_{pk}(m,\sigma)$.
\item \textbf{Basic correctness requirement}: $\mathsf{Vrfy}_{pk}(m,\mathsf{Sign}_{sk}(m)) = 1$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Defining of Signature Security}
The signature experiment $\mathsf{Sigforge}_{\mathcal{A},\Pi }(n)$:
\begin{enumerate}
\item $(pk,sk) \gets \mathsf{Gen}(1^n)$.
\item $\mathcal{A}$ is given input $1^n$ and oracle access to $\mathsf{Sign}_{sk}(\cdot)$, and outputs $(m,\sigma)$. $\mathcal{Q}$ is the set of queries to its oracle.
\item $\mathsf{Sigforge}_{\mathcal{A},\Pi }(n)=1 \iff$ $\mathsf{Vrfy}_{pk}(m,\sigma)=1$ $\land$ $m \notin \mathcal{Q}$. 
\end{enumerate}
\begin{definition}
A signature scheme $\Pi$ is \textbf{existentially unforgeable under an adaptive CMA} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that:
\[ \Pr [\mathsf{Sigforge}_{\mathcal{A},\Pi }(n)=1] \le \mathsf{negl}(n).
\]
\end{definition}
\begin{exampleblock}{Q: What's the difference on the ability of adversary between MAC and digital signature? What if an adversary is not limited to PPT?}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{The ``Hash-and-Sign'' Paradigm}
\begin{construction}
$\Pi = (\mathsf{Gen}_S, \mathsf{Sign}, \mathsf{Vrfy})$, $\Pi_H = (\mathsf{Gen}_H, H)$. A signature scheme $\Pi'$:
\begin{itemize}
\item $\mathsf{Gen}'$: on input $1^n$ run $\mathsf{Gen}_S(1^n)$ to obtain $(pk,sk)$, and run $\mathsf{Gen}_H(1^n)$ to obtain $s$. The public key is $pk'=\langle pk,s\rangle$ and the private key is $sk' = \langle sk,s\rangle$.
\item $\mathsf{Sign}'$: on input $sk'$ and $m \in \{0,1\}^*$, $\sigma \gets \mathsf{Sign}_{sk}(H^s(m))$.
\item $\mathsf{Vrfy}'$: on input $pk'$, $m \in \{0,1\}^*$ and $\sigma$, output 1 $\iff$ $\mathsf{Vrfy}_{pk}(H^s(m),\sigma)=1$.
\end{itemize}
\end{construction}
\begin{theorem}
If $\Pi$ is existentially unforgeable under an adaptive CMA and $\Pi_H$ is collision resistant, then Construction is existentially unforgeable under an adaptive CMA.
\end{theorem}
\end{frame}
\begin{frame}\frametitle{One-Time Signature (OTS)}
\textbf{One-Time Signature (OTS)}: Under a weaker attack scenario, sign only one message with one secret.\\
The OTS experiment $\mathsf{Sigforge}_{\mathcal{A},\Pi }^{\text{1-time}}(n)$:
\begin{enumerate}
\item $(pk,sk) \gets \mathsf{Gen}(1^n)$.
\item $\mathcal{A}$ is given input $1^n$ and a \alert{single query} $m'$ to $\mathsf{Sign}_{sk}(\cdot)$, and outputs $(m,\sigma)$, $m \neq m'$.
\item $\mathsf{Sigforge}_{\mathcal{A},\Pi }^{\text{1-time}}(n)=1 \iff \mathsf{Vrfy}_{pk}(m,\sigma)=1$. 
\end{enumerate}
\begin{definition}
A signature scheme $\Pi$ is \textbf{existentially unforgeable under a single-message attack} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that:
\[ \Pr [\mathsf{Sigforge}_{\mathcal{A},\Pi }^{\text{1-time}}(n)=1] \le \mathsf{negl}(n).
\]
\end{definition}
\end{frame}
\begin{frame}\frametitle{Lamport's OTS}
\textbf{Idea}: OTS from OWF; one mapping per bit.
\begin{construction}
$f$ is a one-way function.
\begin{itemize}
\item $\mathsf{Gen}$: on input $1^n$, for $i \in \{1,\dotsc, \ell\}$:
\begin{enumerate}
\item choose random $x_{i,0}, x_{i,1} \gets \{0,1\}^n$.
\item compute $y_{i,0} := f(x_{i,0})$ and $y_{i,1} := f(x_{i,1})$.
\end{enumerate}
\[ pk = \begin{pmatrix} y_{1,0} & y_{2,0} & \cdots & y_{\ell,0} \\
y_{1,1} & y_{2,1} & \cdots & y_{\ell,1} \end{pmatrix}\;\;\; sk = \begin{pmatrix} x_{1,0} & x_{2,0} & \cdots & x_{\ell,0} \\
x_{1,1} & x_{2,1} & \cdots & x_{\ell,1} \end{pmatrix}. \]
\item $\mathsf{Sign}$: $m = m_1\cdots m_{\ell}$, output $\sigma = (x_{1,m_1},\dotsc,x_{\ell,m_{\ell}})$.
\item $\mathsf{Vrfy}$:  $\sigma = (x_1,\dotsc,x_{\ell})$, output $1 \iff f(x_i) = y_{i,m_i}$, for all $i$. 
\end{itemize}
\end{construction}
\begin{theorem}
If $f$ is OWF, $\Pi$ is OTS for messages of length polynomial $\ell$.
\end{theorem}
\end{frame}
\begin{frame}\frametitle{Certificates}
\begin{figure}
\begin{center}
\input{tikz/certificates}
\end{center}
\end{figure}
\[\text{\bf Certificates}\;\; \mathsf{cert}_{C\to B} \overset{\text{def}}{=} \mathsf{Sign}_{sk_C}(\text{`Bob's key is } pk_B\text{'}).\]
\end{frame}
\begin{frame}\frametitle{Public-Key Infrastructure (PKI)}
\begin{itemize}
\item \textbf{A single CA}: is trusted by everybody.
\begin{itemize}
\item Strength: simple
\item Weakness: single-point-of-failure
\end{itemize}
\item \textbf{Multiple CAs}: are trusted by everybody.
\begin{itemize}
\item Strength: robust
\item Weakness: cannikin law
\end{itemize}
\item \textbf{Delegation and certificate chains}: The trust is transitive.
\begin{itemize}
\item Strength: ease the burden on the root CA. 
\item Weakness: difficult for management, cannikin law. 
\end{itemize}
\item \textbf{``Web of trust''}: No central points of trust, e.g., PGP.
\begin{itemize}
\item Strength: robust, work at ``grass-roots'' level. 
\item Weakness: difficult to manage/give a guarantee on trust.
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Invalidating Certificates}
\begin{itemize}
\item \textbf{Expiration}: include an \emph{expiry date} in the certificate.
\[\mathsf{cert}_{C \to B} \overset{\text{def}}{=} \mathsf{Sign}_{sk_C}(\text{`bob's key is}\; pk_B \text{'},\; \text{date}). \]
\item \textbf{Revocation}: explicitly revoke the certificate.
\[\mathsf{cert}_{C \to B} \overset{\text{def}}{=} \mathsf{Sign}_{sk_C}(\text{`bob's key is}\; pk_B \text{'},\; \text{\#\#\#}).  \]
``\#\#\#'' represents the serial number of this certificate.\\
\textbf{Cumulated Revocation}: CA generates \emph{certificate revocation list} (CRL) containing the serial numbers of all revoked certificates, signs CRL with the current date. 
\end{itemize}
\end{frame}

\begin{frame}\frametitle{Simplified SSL/TLS Handshaking}
\textbf{Purpose}: generate 4 secret keys with authenticated server\\
\textbf{Requirement}: the client has the public key of Trusted Third Party\\
the server has the certificate of its own $pk$ issued by TTP
\begin{figure}
\begin{center}
\input{tikz/ssl}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Three-Pass Protocol}
\textbf{Purpose}: communication without shared keys\\
\textbf{Requirement}: $\mathsf{Dec}_{k_1}(\mathsf{Enc}_{k_2}(\mathsf{Enc}_{k_1}(m))) = \mathsf{Enc}_{k_2}(m)$\\
\textbf{Shamir Protocol}: $p$ is a prime, find $e,d$ with $\gcd(e,p-1)=1$ and $ed \equiv 1 \pmod{p-1}$
\begin{figure}
\begin{center}
\input{tikz/threepass}
\end{center}
\end{figure}
$c_2^{d_B} = c_1^{d_A\cdot d_B} = c^{e_B\cdot d_A\cdot d_B} = m^{e_A\cdot e_B\cdot d_A\cdot d_B} = m^{e_Ad_A\cdot e_Bd_B} = m$
\textbf{Weakness}: insecurity under the man-in-the-middle attack
\end{frame}
\begin{frame}\frametitle{Blind Signature}
\textbf{Blind signature} is a form of digital signature in which the message is blinded before it is signed.\\
Alice asks for Signer to sign $m$ blindly and then sends to Bob
\begin{figure}
\begin{center}
\input{tikz/blindsignature}
\end{center}
\end{figure}
\[s \equiv s'r^{-1} \equiv m'^dr^{-1} \equiv (mr^e)^dr^{-1} \equiv m^d.\]
\end{frame}
\begin{frame}\frametitle{Group Signature}
\textbf{Group Signature}: allowing a member of a group to anonymously sign a message on behalf of the group (with a group manager)
\begin{itemize}
\item \textbf{Soundness}: valid sigs by members verify correctly
\item \textbf{Unforaeable}: only members can create valid sigs
\item \textbf{Anonymity}: signer can be determined only by manager
\item \textbf{Traceability}: manager can trace which member signed
\item \textbf{Unlinkability}: cannot tell if two sigs were from same signer
\item \textbf{Exculpability}: cannot forge a sig for other/non members
\end{itemize}
\textbf{A trivial group signature with trusted manager GM}:\\
\begin{itemize}
\item \textbf{KeyGen}: GM generates a secret key list for each member and publishes all of public keys
\item \textbf{Sign}: sign with an unused secret key
\item \textbf{Verify}: try all of public keys
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Secret Sharing}
\textbf{Purpose}: distribute a secret amongst a group of $n$ participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares $t$ are combined together. It is called $(t, n)$-\textbf{threshold scheme}.
\newline

\textbf{Blakley's scheme}: any $n$ nonparallel $n$-dimensional hyperplanes intersect at a specific point.

  \begin{minipage}[t]{0.32\linewidth} 
    \centering 
    \includegraphics[width=30mm]{pic/Secretsharing-1} 
  \end{minipage}% 
  \begin{minipage}[t]{0.32\linewidth} 
    \centering 
    \includegraphics[width=30mm]{pic/Secretsharing-2} 
  \end{minipage}
  \begin{minipage}[t]{0.32\linewidth} 
    \centering 
    \includegraphics[width=30mm]{pic/Secretsharing-3}  
  \end{minipage} 

\textbf{Chinese remainder theorem}: the shares of secret are generated by reduction modulo some relatively prime integers, and the secret is recovered by solving the system of congruences using the CRT.
\end{frame}
\begin{frame}\frametitle{Threshold Cryptography}
\textbf{$(t,n)$-threshold scheme}: at least $t$ of parties can efficiently decrypt/sign the ciphertext, while less than $t$ have no useful information\\

\textbf{Threshold Elgamal Cryptosystem}:
\begin{itemize}
\item \textbf{Key sharing}: $sk = s, pk=h=g^s$. Party $i$ obtains a share $s_i$ with Shamir's scheme  ($(t, n)$-threshold secret sharing) such that $s = \Sigma_i s_i\cdot \lambda_i$ with public info $\lambda_i$ and publishes $h_i = g^{s_i}$
\item \textbf{Enc}: $y \gets \mathbb{Z}_q$, $\left<c_1,c_2\right>=\left<g^y,h^y\cdot m\right>$
\item \textbf{Dec}: Party $i$ outputs $d_i = c_1^{s_i}$ and ZKP of $\log_gh_i = \log_{c_1} d_i$
\[ m = c_2/\Pi_i d_i^{\lambda_i} \]
$c_2/\Pi_i d_i^{\lambda_i} = c_2/\Pi_i c_1^{s_i\cdot \lambda_i} = c_2/c_1^{\Sigma_i s_i\cdot \lambda_i} = c_2/c_1^s=m$
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Commitment Scheme}
\textbf{Commitment scheme} allows one to commit to a value while keeping it hidden, with the ability to reveal the committed value
\newline

\textbf{Coin flipping over Internet}: Alice flips the coin, Bob guesses
\begin{figure}
\begin{center}
\input{tikz/coinflipping}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Zero-Knowledge Proof}
\begin{itemize}
\item \textbf{Interactive proof system} is an abstract machine that models computation as the exchange of messages between two parties: verifier and prover
\item \textbf{Proof of knowledge}: an interactive proof in which \textbf{prover} succeeds convincing \textbf{verifier} that it knows something
\item \textbf{Zero-knowledge proof (ZKP)}: an interactive proof \emph{without revealing anything other than the veracity of the statement}
\begin{itemize}
\item \textbf{Completeness}: if the statement is true, the honest ``verifier'' will be convinced by an honest prover
\item \textbf{Soundness}: if the statement is false, no cheating prover can convince the honest verifier
\item \textbf{Existence}: If OWF exists, ZKP exists for any NP-set
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{A Toy Example of ZKP}
Alice {\color{red} \LARGE \Ladiesroom} proves to Bob {\color{blue} \LARGE \Gentsroom} that she knows the secret word used to open a magic door in a cave
\begin{figure}
\begin{center}
\input{tikz/zkp}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Schnorr Protocol}
\textbf{Schnorr protocol}: Alice proves to Bob the knowledge of $x=\log_gy$ in the discrete log problem
\begin{figure}
\begin{center}
\input{tikz/schnorr}
\end{center}
\end{figure}
If Alice can foresee $c$, Alice can cheat with $t=g^s/y$ when $c=1$.
\end{frame}
\begin{frame}\frametitle{ZKP of the Ability to Break RSA}
\textbf{Purpose}: Alice convinces Bob that she knows Charlie's private key $d$ for RSA problem $\langle N,e,d \rangle$, but she doesn't want to tell Bob $d$
\begin{figure}
\begin{center}
\input{tikz/zkp-rsa}
\end{center}
\end{figure}
If Alice can manipulate $c$, Alice can cheat with $c = m^e$.
\end{frame}
\begin{frame}\frametitle{Oblivious Transfer}
\textbf{Oblivious transfer (OT)} protocol: a sender remains oblivious as to whether or which info has been transferred.\\

\textbf{Rabin's OT protocol}: RSA problem $\langle N, e, d\rangle $
\begin{figure}
\begin{center}
\input{tikz/rabinOT}
\end{center}
\end{figure}
If $y \neq \pm x$, then Bob can factorize $N$ with $\gcd(y-x,N)$ and find $d$. Since every quadratic residue modulo $N$ has four square roots, Bob can learn $m$ with probability $\frac{1}{2}$.
\end{frame}
\begin{frame}\frametitle{Secure Multi-Party Computation}
\textbf{Secure multi-party computation (MPC)}: enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private\\
\textbf{Dining Cryptographers Problem}: how to perform a secure MPC of the boolean-OR function
\begin{columns}
\begin{column}{4cm}
\begin{figure}
\begin{center}
\input{tikz/dining}
\end{center}
\end{figure}
\end{column}
\begin{column}{6cm}
\begin{itemize}
\item at most one {\color{red} \LARGE \Gentsroom} (1), other {\color{blue} \LARGE \Gentsroom} (0)
\item every two adjacent people establish a shared one-bit secret
\item everyone shouts the XOR of two shared secrets and its own bit
\item output the XOR of all of what everyone shouts. If $1$, there is a {\color{red} \LARGE \Gentsroom}, otherwise there is none
\end{itemize}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Why Quantum Cryptography?}
Quantum cryptography taps the natural uncertainty of the quantum world
\begin{itemize}
\item \textbf{Superposition}: object doesn't have definite properties (location, speed) but has probabilities over them
\item \textbf{Interference}: probabilities can be negative
\item \textbf{Entanglement}: properties of many particles can be correlated
\item \textbf{Measurement}: object's properties collapse to definite value when measured, collapsing also properties of other entangled objects
\end{itemize}
\end{frame}
\begin{frame}\frametitle{State-of-the-Art of Quantum Cryptography}
\begin{itemize}
\item (Unsurprisingly) there is \textbf{no proof} that quantum computers are more powerful than classical computers/Boolean circuits/Turing machines
\item There are \textbf{polynomial} algorithms for quantum computers solving problems unknown to be solvable classically in poly-time: factoring and discrete logs
\item There are \textbf{hard} problem with no quantum poly-time algorithm: NPC, inverting many candidate OWF, private key encryption and signature schemes
\end{itemize}
\end{frame}
\begin{frame}[fragile]\frametitle{Quantum Key Distribution}
\textbf{Purpose}: Using photon polarization states to transmit the information in a public channel against eavesdroppers

\begin{exampleblock}{BB84 protocol: C. H. Bennett and G. Brassard (1984)}
{\centering	
\begin{tabular}{|c|c|c|} \hline
Basis & \verb#0# & \verb#1# \\ \hline
\verb#+# & \verb#|# & \verb#-# \\ \hline
\verb#x# & \verb#/# & \verb#\# \\ \hline
\end{tabular}	
\begin{tabular}{|r|c|} \hline
Alice's random bits & \verb#01101001# \\ \hline
Alice's random sending basis & \verb#++x+xxx+# \\ \hline
Photon polarization Alice sends & \verb#|-\|\//-# \\ \hline
Bob's random measuring basis & \verb#+xxx+x++# \\ \hline
Photon polarization Bob measures & \verb#|/\/-/--# \\ \hline
Shared secret key & \verb#0 1  0 1# \\ \hline
\end{tabular}
}
\begin{itemize}
\item Two bases are public
\item Eavesdropping would change the photon polarization states
\item Check for the presence of eavesdropping by comparing a subset of shared bit string
\end{itemize}
\end{exampleblock}
\end{frame}

\begin{frame}\frametitle{Provable Security}
\begin{itemize}
\item A proof of security never proves security in an absolute sense, it relates security to an unproven assumption that some computational problem is hard.
\item The quality of a security reduction should not be ignored -- it matters how tight it is, and how strong the underlying assumption is.
\item A security reduction only proves something in a particular model specifying what the adversary has access to and can do.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Crypto Pitfalls}
Crypto deceptively simple
\begin{itemize}
\item Why does it so often fail?
\end{itemize}
Important to distinguish various issues:
\begin{enumerate}
\item Bad cryptography/implementations/design, etc.
\item Good cryptography can be `circumvented' by adversaries operating `outside the model'
\item Even the best cryptography only shifts the weakest point of failure to elsewhere in your system
\item Systems are complex: key management; social engineering; insider attacks
\end{enumerate}
Avoid the first; be aware of 2-4.
\end{frame}
\begin{frame}\frametitle{Bad Implementation Example: Heartbleed}
  \begin{minipage}[t]{0.49\linewidth} 
    \centering 
    \includegraphics[width=50mm]{pic/heartbleed1} 
  \end{minipage}% 
  \begin{minipage}[t]{0.49\linewidth} 
    \centering 
    \includegraphics[width=50mm]{pic/heartbleed2} 
  \end{minipage}
\end{frame}
\begin{frame}\frametitle{Crypto is difficult to get right}
\begin{itemize}
\item Must be implemented correctly
\item Must be integrated from the beginning, not added on ``after the fact''
\item Need expertise; ``a little knowledge can be a dangerous thing''
\item Can't be secured by Q/A, only (at best) through penetration testing and dedicated review of the code by security experts
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Beware of Snake Oil}
\textbf{Snake Oil}: bogus commercial cryptographic products.
\begin{itemize}
\item \textbf{Secret system}: security through obscurity
\item \textbf{Technobabble}: since cryptography is complicated
\item \textbf{Unbreakable}: a sure sign of snake oil
\item \textbf{One-time pads}: a flawed implementation
\item \textbf{Unsubstantiated ``bit'' claims}: key lengths are not directly comparable
\end{itemize}
\end{frame}
\begin{frame}\frametitle{General Recommendation}
\begin{itemize}
\item Use only standardized algorithms and protocols
\item No security through obscurity!
\item Use primitives for their intended purpose
\item Don't implement your own crypto
\item If your system cannot use ``off-the-shelf'' crypto components, re-think your system
\item If you really need something new, have it designed and/or evaluated by an expert
\item Don't use the same key for multiple purposes
\item Use good random-number generation
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Crypto Libraries}
\begin{itemize}
\item Use existing, high-level crypto libraries: 
cryptlib, NaCl, Google's Keyczar, Mozilla's NSS, OpenSSL 
\item Avoid low-level libraries (like JCE, crypto++, GnuPG, OpenPGP) - too much possibility of mis-use
\item Avoid writing your own low-level crypto
\end{itemize}
\end{frame}
\end{document}