\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage[table]{xcolor}
\usepackage{adjustbox}
\usepackage{dashbox}
\usepackage{cjhebrew}
\usepackage{xspace}
\begin{document}
\input{preamble.tex}
\lecture{1: Introduction}{October 26, 2017}{Nir Bitansky}{Nathan Geier, Oren Renard}
%%%% body goes in here %%%%
\nir{
\section{Administrative}
\begin{itemize}
\item
English?
\item
Nir Bitansky - link to course webpage from my webpage.
\item
See course's webpage for more details.
\item
If you're not listed, and would like to be on the mailing list, email me.
\item
Aim: tools for basic research in crypto.
\item
Those who figure out at the end, or throughout, they would like to do research in crypto, should talk to me.
\item
It is meant for grad students with mathematical maturity (no heavy math, but should feel comfortable with formal proofs and probability). Also, most materials (including the homework) will be in english.
\item
To succeed in the course:
\begin{itemize}
\item
Follow closely. In class, we won't always give all the details. Scribers will fill most of them.
\item
Home assignments are crucial, and require some time.
\item
Those who do the assignments shouldn't have trouble with the exam.
\item
Bonus for participation. I believe in interaction.
\item
Don't be shy to note my errors.
\item
Who's taking scribe notes?
\end{itemize}
\item
We will have a grader. It could be one of you, so those of you who are interested email me asap. Pays of course...
\end{itemize}
}% end of administrative
\section{What is Cryptography?}
\begin{itemize}
\item
{\em According to Wikipedia: Cryptography (from Greek κρυπτός kryptós, "hidden, secret"; and γράφειν graphein, "writing") is the practice and study of techniques for secure communication in the presence of third parties called adversaries.}
\item
Private communication is indeed the oldest and most basic problem in cryptography, it will also be the starting point for this course.
\item
As we shall see the scope of crypto has greatly expanded beyond this problem, addressing a host of problems (in the digital domain).\\
The common goal: "Prevent the adversary from executing his evil bidding."
\end{itemize}
\section{The Crypto Way of Thinking: The Case of Encryption}
The problem of communicating secretly is as old as humanity itself. Today we'll touch snippets of history to demonstrate how it transformed from an art into a well-founded mathematical concept.
\paragraph{The Basic Setting:}
$$
\xrightarrow{\makebox[1cm]{$m$}} \boxed{\text{Alice}(sk)} \xrightarrow{\makebox[3cm]{$\begin{array}{c}\boxed{\text{Eve}}\\\\cipher\end{array}$}} \boxed{Bob(sk)}\xrightarrow{\makebox[1cm]{$m$}}
$$
Main question: can we prevent Eve from learning about $m$.
\paragraph{Solutions from the Old World - Encryption as an Art.} We'll now cover a few examples/anecdotes of ``artistic encryption''.
\begin{itemize}
\item
The ATBASH (\cjRL{'tb/s}) cipher in the book of Jeremiah (circa 600BC):
\begin{center}\includegraphics[width=12cm]{jer.jpg}\end{center}
Who is ``\cjRL{/s/sK}"? How does this cipher work?
\item
Substitution cipher used by queen Mary:
\begin{center}\includegraphics[width=12cm]{mary.jpg}\end{center}
In 1587, Mary the queen of Scots, and the heir to the throne of England, wanted
to arrange the assassination of her cousin, queen Elisabeth I of England, so that
she could ascend to the throne and finally escape the house arrest under which
she has been for the last 18 years. She sent an encrypted letter to Sir Anthony Babington. It is a substitution cipher where each letter is transformed into a different symbol, only that unlike the deterministic ATBASH cipher, the substitution could be arbitrary.
Nevertheless, Elisabeth's spies broke the cipher, and were executed! (An important lesson --- bad crypto seldom goes unpunished.) How did the spies break the cipher?
\item The Vigenère cipher was invented in the 16th century (it was actually invented by Italian cryptographer Bellaso) and lasted for roughly 300 years!!
It (or rather, its English adaptation) works as follows. The secret key consists of an integer $n$ and random numbers $S_1,\dots,S_n \gets [26]$. To encrypt a text $T_1,\dots,T_N$ where each $T_i \in [26]$ is a letter. Let the encrypted letter be $\widetilde T_i = T_i + S_{i \bmod n} \mod 26$.
Harder to apply frequency analysis - the eventual text is ``smoother''. Can you still break it? \scribes{explain how.}
The idea is to find the key length $n$, and then the ciphertext can be divided into $N/n$ sub-texts, where each one actually implement a simple substitution cipher.
\emph{Kasiski examiniation} is a method for finding the key length $n$. The method looks for repetitions of (short) strings in the ciphertext. Such repetitions may correspond to repetitions in the underlying plaintext, in which case the \emph{distance} between each two copies is a multiple of the key length $n$. When finding all of the distances of all sub strings $d_1, ..., d_m$, the most frequent factor among them is the most likely key length $n$.
Now, the ciphertext can be divided into $\ceil{N/n}$ "rows", each row encrypted with the same key $S_1, ..., S_n$, and each column encrypted with substitution cipher with the \emph{same character $S_i$} as shift. Using frequency analysis on each column, one can find the key, character after character.
\item
There are many other famous historical ciphers, which we won't cover, and all have been by now broken. Perhaps the most famous one is the German Enigma (watch The Imitation Game).
\end{itemize}
%
Indeed, throughout most of history, cryptographic systems had limited life spans. They would be invented, broken, fixed, broken, reinvented, and so on.
\begin{center} {\em Is this inherent? Could we have unbreakable crypto?}\end{center}
This is the goal of modern cryptography --- construct cryptographic systems whose security we can mathematically prove. Jumping ahead, sometimes, even most times, we won't be able to give unconditional proofs, and we will rely on certain assumptions. We'll defer this discussion for later.
So, we want {\em provably-secure} encryption. We first need to understand what this means --- we need a definition. Indeed, the first step in designing crypto systems is coming up with ``the right'' definition, which is often challenging on its own.
\begin{definition}[Secret Key Encryption]$ $
\begin{itemize}
\item
{\bf Syntax:} An encryption scheme consists of three (possibly probabilistic) polynomial-time (PPT) algorithms $(G,E,D)$.
\begin{itemize}
\item
$G(1^n)$ is a key generation algorithm that takes as input a key-length, and outputs a key $sk$ of length $n$.\footnote{For secret key encryption, we can assume w.l.o.g that $sk$ is drawn uniformly at random from $\zo^n$, denoted $sk\gets \zo^n$. This is because we can always treat the random coins used by $G$ as the secret key, and apply $G$ as part of the encryption algorithm.}
\item
$E_{sk}(M)$ is an encryption algorithm that takes as input the key $sk$ and a message $m \in \zo^*$, and outputs a ciphertext $ct$.
\item
$D_{sk}(ct)$ is a decryption algorithm that takes as input the key $sk$ and a ciphertext $ct$, and outputs a decrypted $m$.
\end{itemize}
\item
{\bf Correctness:} for any key $sk$ output by $G$, and any message $m$, it is always the case that:
$$
D_{sk}(E_{sk}(m)) = m\enspace.
$$
\item
{\bf Security:} ???
\end{itemize}
\end{definition}
\medskip\noindent
Defining security is usually the more tricky part and requires some more thought. The first thing we need to ask is {\em what does the adversary (in our case, Eve) know?} Clearly, Eve sees the ciphertext $ct$, and does not get the secret key $sk$. What about the algorithms $(G,E,D)$ themselves?
We'll follow the principle saying that the scheme's algorithms themselves are always assumed to be public. This principle was first suggested by Prussian general Kerckhoffs (1883) who rightfully argued that the system/method of encryption could quite easily be stolen by the enemy. So what is secret? and how can we keep using a system that is known to the adversary? The imminent answer is {\em randomness}. In particular, as long as the secret key is chosen at random, we can hope for security. If the key is stolen, we can sample a fresh random key, and we don't have to throw away the entire system!!
\medskip\noindent
With this principle in mind, let's try to define security.
\begin{itemize}
\item
{\bf Security, 1st attempt:} $(G,E,D)$ is secure if no adversary $A$ can recover the key $sk$ better than by guessing --- for all messages $m\in\zo^*$,
$$
\Pr\[A(ct) = sk \pST \begin{array}{l}
sk \gets G(1^n)\\
ct \gets E_{sk}(m)
\end{array}\] \leq 2^{-n}\enspace.
$$
\end{itemize}
Is this a good definition? \scribes{explain the problem} No!
\begin{claim}
The scheme where $sk\gets \zo^n$ is chosen at random, $E_{sk}(m) = m$, and $D$ is the identity is secure according to this definition.
\end{claim}
\begin{itemize}
\item
{\bf Security, 2nd attempt:} $(G,E,D)$ is secure if no adversary $A$ can recover the message $m$ better than by guessing the key --- for all messages $m\in\zo^*$,
$$
\Pr\[A(ct) = m \pST \begin{array}{l}
sk \gets G(1^n)\\
ct \gets E_{sk}(m)
\end{array}\] \leq 2^{-n}\enspace.
$$
\end{itemize}
Is this a good definition?
\begin{claim}
No encryption scheme satisfies this definition.
\end{claim}
%
Clearly, an adversary that outputs some fixed message, for instance $0^n$, guesses $m=0^n$ with probability one. But should this be considered an attack? Does this adversary learn anything about the message that she did not know before?
\paragraph{Shannon's Perfect Secrecy.} In 1949, Shannon formalized the notion of {\em perfectly secret encryption} (this is often viewed is the dawn of modern cryptography). The leading principle was indeed that{\em a ciphertext shouldn't add information about the underlying encrypted messages beyond what is already known.} It turns out that there are several equivalent ways to formulate this, and we can gain different valuable intuitions from them.
\begin{itemize}
\item
{\bf Perfect Secrecy 1:} $(G,E,D)$ is perfectly secure for messages of size $\ell=\ell(n)$ if for any two messages $m_0,m_1 \in \zo^\ell$, no adversary $A$ can distinguish an encryption of one from the other:
$$
\Pr\[A(ct) = m_b \pST \begin{array}{l}
sk \gets G(1^n)\\
b \gets \zo\\
ct \gets E_{sk}(m_b)
\end{array}\] \leq \frac{1}{2}\enspace.
$$
\end{itemize}
\begin{itemize}
\item
{\bf Perfect Secrecy 2:} $(G,E,D)$ is perfectly secure for messages of size $\ell=\ell(n)$ if there exists a fixed distribution $D$ (independent of any specific message), such that for all $m \in \zo^\ell$:
$$
\set{ct\pST \begin{array}{l}
sk \gets G(1^n)\\
ct \gets E_{sk}(m)
\end{array}} \equiv \set{\widetilde{ct} \pST \begin{array}{l}
\widetilde{ct} \gets D
\end{array}}\enspace.
$$
\end{itemize}
The above means that, without the secret key, the ciphertext distribution that the adversary sees is completely independent of the encrypted message up to its length. (Indeed, the definition does allow leaking the length of messages. In fact, some leakage on the length is inherent, think why...)
\begin{claim}
The above two definitions are equivalent.
\end{claim}
\begin{proof}[Proof sketch]
Assume that (1) holds. Define
$$
D := \set{\widetilde{ct} \pST \begin{array}{l}
sk \gets G(1^n)\\
\widetilde{ct} \gets E_{sk}(0^\ell)
\end{array}}\enspace.
$$
We need to show that for all $m\in \zo^\ell$, the above is distributed like $$D(m):=\set{\widetilde{ct} \pST \begin{array}{l}
sk \gets G(1^n)\\
\widetilde{ct} \gets E_{sk}(m)
\end{array}}\enspace.$$
Assume toward contradiction this is not the case, then for some $m^*$, $D \not\equiv D(m^*)$. We will show an adversary $A$ that distinguishes encryptions of $m_0 = 0^\ell$ from ones of $m_1 = m^*$. Let $ct^*$ be such that
$$\varepsilon := \Pr[D =ct^*] - \Pr[D(m^*)=ct^*] > 0 \text{ \hspace{1cm}(why does it exist?).}$$
%
Consider the adversary $A$ that given $ct$ outputs $m_0$ if $ct=ct^*$, and otherwise outputs $m_{1}$.\footnote{Other natural attempts like outputting $m_{b'}$ for a random $b' \gets \zo$ if $ct \neq ct^*$, or an adversary that for each $ct$ outputs the message corresponding to the distribution where $ct$ is more likely (and outputs $m_0$ in case of a tie), would also work.} We now analyze this adversary. In what follows, all the probabilities are over $sk \gets G(1^n), b \gets \zo,ct \gets E_{sk}(m_b)$. Then
\begin{align}
&\Pr\[A(ct) = m_b\]=\\
&\Pr\[b=0\]\Pr\[A(ct) = m_0 \pST
b=0\]+\Pr\[b=1\]\Pr\[A(ct) = m_1 \pST b=1\]\enspace,\nonumber\\\nonumber\\
&\Pr\[b=0\]=\Pr\[b=1\]= \frac{1}{2} \enspace,
\\\nonumber\\
&\Pr\[A(ct) = m_0 \pST
b=0\] = \Pr\[ct=ct^*|b=0\]=\Pr[D = ct^*]\enspace,\\\nonumber\\
&\Pr\[A(ct) = m_1 \pST
b=1\] = \Pr\[ct\neq ct^*|b=1\]= 1-\Pr[D(m^*) = ct^*]\enspace.\\\nonumber
\end{align}
\scribes{complete the proof}
From these four equations, we get that
\begin{equation*}
\begin{split}
\Pr\[A(ct) = m_b\] &=\frac{1}{2} \Pr[D = ct^*]+\frac{1}{2} \left(1-\Pr[D(m^*) = ct^*]\right) \\
&= \frac{1}{2}\left(1+\Pr[D = ct^*]-\Pr[D(m^*)=ct^*]\right) \\
&= \frac{1}{2}\left(1+\varepsilon\right)>\frac{1}{2}\enspace.
\end{split}
\end{equation*}
%
We got that $\Pr\[A(ct) = m_b\]>\frac{1}{2}$, which is a contradiction to our assumption that (1) holds.
\medskip\noindent For the other direction, assume that (2) holds, and we will show that (1) holds. Let $m_0,m_1 \in \zo^\ell$ be two arbitrary messages of length $\ell$. Note that $$\Pr\[A(E_{sk}(m_b))=m_b\]=\Pr\[A(\widetilde{ct})=m_b\pST \widetilde{ct}\gets D\] =1/2 \enspace.$$
Where the first equality follows from the fact that $E_{sk}(m_b)\equiv D$, and the latter by the fact that $A$'s input, and thus also its output, are independent of $b$.
\end{proof}
\medskip\noindent
Another equivalent definition worth baring in mind:
\begin{itemize}
\item
{\bf Perfect Secrecy 3:} $(G,E,D)$ is perfectly secure for messages of size $\ell=\ell(n)$ if for any distribution $M$ on messages in $\zo^\ell$ any ciphertext $ct$ in the support of $E$ and any message $m'\in \zo^\ell$:
$$
\Pr_{m \gets M}\[m=m'\] = \Pr_{m \gets M, sk\gets G(1^n)}\[m=m'\pST E_{sk}(m)=ct\]
$$
\end{itemize}
Here the distribution $M$ should be thought of as partial information that the adversary has regarding encrypted messages. For instance, all German messages in WW2 ended with "Heil Hitler". Of course, we cannot expect to hide this fact, again all that we ask is not to add information --- namely conditioning on an encryption of a message does not change its distribution.
Another useful definition, which may seem less general, but is equivalent:
\begin{itemize}
\item
{\bf Perfect Secrecy 4:} $(G,E,D)$ is perfectly secure for messages of size $\ell=\ell(n)$ if for any set $S\subseteq \zo^\ell$:
$$
\Pr\[A(ct) = m \pST \begin{array}{l}
sk \gets G(1^n)\\
m \gets S\\
ct \gets E_{sk}(m)
\end{array}\] \leq \frac{1}{|S|}\enspace.
$$
\end{itemize}
%
So now that we've defined perfect ciphers, do they exist?
\begin{theorem}[Vernam 1917]
There exists a perfect cipher for messages of size $n$ with keys and ciphertexts sof size $n$.
\end{theorem}
\begin{proof}
The cipher is the {\em one-time pad} (OTP):
\begin{itemize}
\item
$G(1^n)$ outputs a random ``pad'' $p \gets \zo^n$.
\item
$E_p(m)$ is the bitwise Xor $p\oplus m$.
\item
$D_p = E_p$.
\end{itemize}
This is correct as $p \oplus (p \oplus m) = m$.\\
It is perfectly secure since for any $m$, $p\oplus m$ is uniformly random in $\zo^n$, when $p$ is chosen at random.
\end{proof}
\paragraph{Why only one time?} Can we use OTP two times? It's not hard to see that encrypting two messages using the same key, already leaks information about them (their Xor). Indeed, throughout history, misuse of OTP has led to devastating leakage. This makes OTP very hard to use. Imagine that every time you give your credit card online, you first have to go somewhere physically to take your one-time pad.
Perhaps there is a better encryption system where we {\em can} use the same key multiple times? This turns out to be the heart of the matter. Indeed, a main challenge in cryptography is to {\em recycle keys} or more generally {\em recycle randomness}. The first hurdle to cross is that {\em this goal is impossible!} Well, not really... but it is if we insist on perfect secrecy.
\begin{theorem}
A perfect cipher for messages of length $\ell$ must have keys of size $n\geq \ell$.
\end{theorem}
\begin{proof}
Assume $n<\ell$. We will show an adversary $A$ that given a ciphertext of a random message $m\gets \zo^\ell$ guesses the message with probability better than $2^{-\ell}$. $A$ simply guesses the key and attempts to decrypt. We know that it succeeds with probability $2^{-n}>2^{-\ell}$.
\end{proof}
So perfect secrecy is too much to ask for. Still guessing the key does not seem like a realistic attack, assuming its moderately long (e.g., a reasonable choice for a secret key is 256 bits. Look for "how big is $2^{256}$?" on youtube...). However, there are in fact much more devastating attacks.
\begin{claim}
For any cipher for messages of length $\ell$ and keys of length $n<\ell - 6$, there exist two messages $m_0,m_1$ and an attacker $A$ such that
$$
\Pr\[A(ct)=m_b \pST \begin{array}{l} sk \gets G(1^n)\\ b\gets \zo\\ct \gets E_{sk}(m_b)\end{array}\] \geq 1-2^{-7} > 0.99\enspace.
$$
\end{claim}
\begin{proof}
For simplicity, we will assume that $E$ does not use any additional randomness beyond $sk$. Fix a message $m_0$ and consider the set of all of its encryptions $C_0 = \set{E_{sk}(m_0)}$. We will show that there exists a message $m_1$, such that an encryption of $m_1$ (under a random key $sk$) falls in $C_0$ with tiny probability.
Indeed, note that for any key $sk$, if we choose $m_1\gets \zo^\ell$ at random, then the corresponding ciphertext $ct$ falls in $C_0$ with probability at most $|C_0|/2^\ell=2^{n}/2^\ell< 2^{-6}$. \scribes{Explain why...}
This is true because $E_{sk}(\cdot)$ is a bijective function (otherwise decryption would be impossible) and the input is drawn uniformly, so the output also distributes uniformly over the function's image. Since the image size is $2^\ell$, and there are at most $|C_0|$ ciphertexts from $C_0$ there, the probability of the output belonging to $C_0$ is at most $|C_0|/2^\ell$.\\
In particular the above holds for a random key. Formally, because:
$$
\Pr_{sk,m_1}\[ct \in C_0\pST ct\gets E_{sk}(m_1)\] = \bbE_{sk}\Pr_{m_1}\[ct \in C_0\pST ct\gets E_{sk}(m_1)\]\leq 2^{-6} .
$$
Now we can fix such specific $m_1$. Formally, because:
$$
\bbE_{m_1}\Pr_{sk}\[ct \in C_0\pST ct\gets E_{sk}(m_1)\] = \Pr_{sk,m_1}\[ct \in C_0\pST ct\gets E_{sk}(m_1)\] \leq 2^{-6}.
$$
%
So there must be some $m_1$ such that $\Pr_{sk}\[ct \in C_0\pST ct\gets E_{sk}(m_1)\] \leq 2^{-6}$, otherwise the expectation would be greater than $2^{-6}$.
Now, consider the adversary $A$ that given $ct$ outputs $m_0$ if $ct\in C_0$, and otherwise outputs $m_1$. By the definition of $C_0$,
$$\Pr\[A(ct) = m_0 \pST
b=0\]=\Pr_{sk}\[ct \in C_0\pST ct\gets E_{sk}(m_0)\]=1\enspace.$$
By the definition of $m_1$, we have that
$$\Pr\[A(ct) = m_0 \pST
b=1\]=\Pr_{sk}\[ct \in C_0\pST ct\gets E_{sk}(m_1)\]\leq 2^{-6}\enspace.$$
Overall, it holds that
\begin{equation*}
\begin{split}
\Pr\[A(ct) = m_b\] &= \Pr\[b=0\]\Pr\[A(ct) = m_0 \pST b=0\]+\Pr\[b=1\]\Pr\[A(ct) = m_1 \pST b=1\] \\
&=\frac{1}{2}\left(\Pr\[A(ct) = m_0 \pST b=0\] + 1 - \Pr\[A(ct) = m_0 \pST b=1\]\right) \\
&\geq\frac{1}{2}\left(1 + 1 - 2^{-6}\right)>0.99\enspace.
\end{split}
\end{equation*}
%The following two lines were edited out
%This gives the required adversary $A$ --- %it simply checks whether $ct\in C_0$.
\scribes{complete the details}
\end{proof}
Does this mean that there's no hope to reuse keys? How realistic is the described attack? The point is that this attack takes a very long time, roughly as long as $|C_0| \approx 2^n$ steps. Our salvation comes from the fact that
\begin{center}
{\em actual adversaries are computationally bounded}.
\end{center}
Most of modern cryptography, and accordingly this course, will rely on this premise. Indeed, as we shall see, there's (almost) no cryptography without computational hardness. This also means that cryptographic theory strongly relies on complexity theory.
One major implication of this is that our lack of understanding of major open questions, \P vs \NP above them all, translate to cryptography --- we cannot prove security unconditionally, but only under computational assumptions. In fact, as we shall see, we will need to assume much beyond $\P\neq \NP$, and minimizing the assumptions made will of course be a major goal.
\iffalse
\section{The Layers of Crypto and the Importance of Abstractions}
{\center
Hard Problems\\
$\Downarrow$\\
Reductions\\
$\Downarrow$\\
\begin{adjustbox}{minipage=0.1\textwidth,precode=\dbox}
\center
Primitives
\end{adjustbox}
$\Rightarrow$
Reductions
$\Rightarrow$
\begin{adjustbox}{minipage=0.1\textwidth,precode=\dbox}
\center
Primitives
\end{adjustbox}
$\Rightarrow$
Reductions
$\Rightarrow$
\begin{adjustbox}{minipage=0.1\textwidth,precode=\dbox}
\center
Primitives
\end{adjustbox}\\
$\Downarrow$\\
Deployment\\
}
\paragraph{Layer 1: Hard Problems.} These are concrete problems that we assume to be hard (e.g., the hardness of satisfying CNF formulas, solving discrete logs, or factoring integers). Such problems come from many different areas in different flavors:
\begin{itemize}
\item
Number theory
\item
Algebra
\item
Combinatorics
\item
Engineered hardness (e.g., AES)
\end{itemize}
Different assumptions may have different evidence for their hardness. Assumptions also differ in the “level of confidence” we have in their hardness: relations to other assumed-to-be-hard problems, etc, amount of time spent on trying to break them. Indeed, the complementing area for this layer (which we won't touch in the course but is very important) is {\em cryptanalysis}.
\paragraph{Layer 2: Primitives.} These are cryptographic abstractions that obtain specific well-defined properties (e.g., secret-key encryption, one-way functions, fully homomorphic encryption, etc.) Such primitives are usually constructed and proven secure by {\em a reduction} to a hard problem. Primitives may also be reduced to one another.
\paragraph{Layer 3: Cryptographic systems.} Deploying cryptographic schemes in the real world to guarantee security for the user. This involves many issues and is often the bottleneck in achieving actual security:
\begin{itemize}
\item
Verifying correctness of the implementation (naive software bugs can be disastrous).
\item
Integration within existing systems.
\item
Side channel attacks (e.g., measuring the power consumption of a device).
\item
Human interface pitfalls (e.g., phishing, weak passwords, etc.).
\end{itemize}
\bigskip\noindent In this course we will mostly focus on Layers 2 and 1. Our ultimate goal is to base all of cryptography on the simplest possible primitives, and be able to base each such primitive on a variety of hard problems.
\fi
\end{document}