\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}
\usepackage{url}
\usepackage{hyperref}
% packages for the graphs:
%\usepackage{tikz}
%\usepackage{tikz-qtree}
\begin{document}
\input{preamble.tex}
\lecture{7: {\large Public-Key Encryption}}{December 7, 2017}{Nir Bitansky}{Yotam Dvir, Inbar Oren, and Michal Shagam}
%%%% body goes in here %%%%
\section{Previously on Foundations of Crypto}
We've seen that starting from one-way functions, we can go a long way. We've constructed PRGs, PRFs, secret-key encryption, authentication and even digital signatures.
\scribes{add picture 1}
\begin{center}
\includegraphics[scale=0.4]{pic1.png}
\end{center}
Today, we will move beyond into the world of public-key encryption.
\section{Privately Communicating without a Secret Key?}
From the dawn of cryptography it was evident that {\em to communicate secretly, parties have to share a secret}, and this perception dominated for centuries. In the 70's, People had begun to challenge this perception, suggesting that secret communication may be achievable without the parties ever meeting! Curiously, these ideas emerged both publicly within the scientific community, and (a few years before that) behind closed doors within the British intelligence agency (you can read more about this fascinating story in \href{http://www.boazbarak.org/cs127/chap10_public_key_intro.pdf}{Barak's notes}).
One of the first to challenge the need for a secret key was Ralph Merkle, then an undergrad at Berkeley. He both conjectured that this is possible, and gave some evidence for this possibility (he demonstrated a public key encryption system where the attacker has to work quadratically, rather than super-polynomially, harder than the honest parties). The paper that officially started the age of public-key cryptography was published in '76 by Diffie and Hellman, and was titled ``New Directions in Cryptography" \cite{DH76}. It describes the concepts of public key-exchange, public-key encryption, and digital signatures, and suggested generic approaches and concrete constructions.
We will now start to explore these concepts.
\section{Public-Key Encryption}
In the setting of public key encryption, Alice shares (say, on her webpage) with the world a {\em public encryption key} $pk$ and keeps a corresponding secret key $sk$. Then any person, Bob, in hold of $pk$ can encrypt messages to Alice. While she can decrypt, any eavesdropper Eve that doesn't know the secret key (but does know the public key) learns nothing.
\scribes{add picture 2}
\begin{center}
\includegraphics{pic2.png}
\end{center}
\begin{definition}[Public-Key Encryption (PKE) against Chosen Plaintext Attacks (CPA)]
A public-key encryption scheme consists of polynomial-time algorithms $(Gen,Enc,Dec)$ with the following properties.
\begin{itemize}
\item {\bf Syntax:}
\begin{itemize}
\item
$Gen(1^n)$ is a randomized algorithm that takes as input a security parameter $n$ and outputs a secret key $sk$ and a public encryption key $pk$.
\item
$Enc_{pk}(m)$ is a randomized algorithm that takes as input the public key $pk$ and message $m\in \zo^*$, and outputs a ciphertext $ct$.
\item
$Dec_{sk}(ct)$ is a deterministic algorithm that takes as input the secret key $sk$ and ciphertext $ct$, and outputs a decrypted message.
\end{itemize}
\item
{\bf Correctness:} for any message $m \in \zo^*$,
$$
\Pr\[Dec_{sk}(Enc_{pk}(m))=m\pST (sk,pk)\gets Gen(1^n)\]=1\enspace.
$$
\item
{\bf Indistinguishability against Chosen Plaintext Attack:} For any (interactive) n.u. PPT $A=\set{A_n}$ there is a negligible $\mu$ such that $A$ wins the following CPA game with probability at most $1/2+\mu(n)$.
\smallskip\noindent The CPA Game:
\begin{itemize}
\item $Gen(1^n)$ samples $sk,pk$.
\item $A_n$ is given $pk$, and chooses two equal-length messages $m_0,m_1$.
\item $A_n$ is then given an encryption $Enc_{pk}(m_b)$ for a random $b\gets \zo$.
\item $A_n$ wins if it guesses $b$ correctly.
\end{itemize}\end{itemize}
\end{definition}
\paragraph{Remarks:}
\begin{itemize}
\item
{\bf Encryption Queries:} Typically, in a chosen plaintext attack, the adversary may also get oracle access to the encryption algorithm, allowing her to adaptively compute encryptions of messages of her choice and choose the challenge messages $m_0,m_1$ accordingly. In the case of public-key encryption, the above definition (without an explicit oracle) is equivalent (make sure you understand why).
\item
{\bf Multi-Message Security:} The definition addresses a single challenge ciphertext. In the homework, you will show that it, in fact, implies multi-message security.
\item
{\bf Public-Key Encryption vs Key Exchange:} A relaxation of the notion of public-key encryption is that of {\em key exchange}. Here two parties may run an {\em interactive protocol} at the end of which they agree on a secret key $sk$, such that an external observer that sees the transcript of the protocol cannot recover $sk$. It is not hard to show that PKE is equivalent to two-message key exchange. However, key exchange protocols with more than two rounds are not known to imply PKE.
\end{itemize}
\paragraph{Why Would PKE Exist?} One has to ask what made Diffie, Hellman and the other co-discoverers of public-key encryption believe that such a thing is even possible. It seems that one intuition they had is the following. Imagine that parties can not only send messages but also {\em magic boxes}. A sender party can lock a computer program $\Pi$ in such a box so that the receiver can provide inputs $x$to the program and get the outputs $\Pi(x)$, but the box is otherwise opaque, and does not allow to see the contents of $\Pi$ itself.
\scribes{add picture 3}
\begin{center}
\includegraphics[scale=0.5]{pic3.png}
\end{center}
In this case, public key encryption can be done as follows. The public key $pk$ can be a ``publicly-verifiable puzzle'', say $f(x)$ for a OWF $f$, and the secret key $sk$ would be the solution $x$. Then to encrypt $m$, we will simply create a magic box and lock inside it the program $\Pi_{f(x),m}$ that returns $m$ only when given the solution $x$. Another natural idea is to publish such a box as the public key and put inside the encryption algorithm of a secret key encryption algorithm (and say derandomize the encryption algorithm using a PRF).
Diffie and Hellman believed that it might be possible to digitally realize such a magic box, by simply {\em rewriting} $\Pi$ in a way that will make it hard to read, e.g. by writing it in some low-level assembly-like language (or asking an undergrad to code it). Indeed, in general, reverse engineering is a notoriously hard problem. This idea is known today as {\em program obfuscation}. Diffie and Hellman didn't give any formal definitions or constructions, but rather used it as intuition to why PKE is conceivable. (In time, it had turned out that obfuscation is a fascinating concept beyond the context of PKE. It is also very challenging to define and construct. In fact, currently, there is still no satisfying solution to the problem. Hopefully, we will return to it toward the end of the course.)
\section{Basing PKE on Hard Problems}
The question now is how to fulfill Diffie and Hellman's intuition based on reasonable computational assumptions. So far in the course we've been lucky enough to manage to construct everything from OWFs. It would be great if we could also prove:
\begin{theorem}[In Our Dreams]
If OWFs exist so do public-key encryption schemes.
\end{theorem}
%
Unfortunately, we're very far from being able to prove such a theorem, and the common belief today is that public-key encryption requires considerably more structure than OWFs.
%To get some (perhaps vague) intuition on the difference, recall that one-way functions were equivalent to being able to sample hard (on-average) problems with a solution. In the public-key setting, we'd like to decouple the generation of the hard problem and the generation of the solution --- we need to {\em sample a sampler of hard problems together with one universal solver.}
Trying to capture the structure required for PKE, Diffie and Hellman suggested the following generalization of one-way functions to trapdoor one-way functions. Here, a function is associated with a public key and a secret {\em trapdoor key}. Using the public key, anyone could compute the function forward, and using the secret key it can also be computed backwards (we'll assume for now that such functions are injective). However, for a random public key, and without the secret key, the function is one way.
\scribes{add picture 4}
\begin{center}
\includegraphics[scale=0.5]{pic4.png}
\end{center}
\begin{definition}[Trapdoor Function (TDF)]
A
trapdoor function is given by polynomial time algorithms $(Gen,F,F^{-1})$ with the following properties:
\begin{itemize}
\item {\bf Syntax:}
\begin{itemize}
\item $Gen(1^n)$ is a probabilistic algorithm that given a security parameter $1^n$ outputs a secret key (also called the trapdoor) and a public key $(sk,pk)$.
\item $F_{pk}(x)$ is a deterministic algorithm that given a public key $pk$ and input $x\in\zo^n$, outputs an image $y$.
\item $F^{-1}_{sk}(y)$ is a deterministic algorithm that given a secret key $sk$ and $y\in\zo^*$, outputs $x\in\zo^n$.
\end{itemize}
\item {\bf Correctness:} for any $x\in \zo^n$,
$$
\Pr\[F_{sk}^{-1}(F_{pk}(x))=x\pST (sk,pk)\gets Gen(1^n)\]=1\enspace.
$$
\item {\bf One-Wayness:} for any n.u. PPT $A=\set{A_n}$, there exists a negligible $\mu$ such that for all $n\in\Nat$,
$$
\Pr\[A_n(pk,F_{pk}(x))=x\pST \begin{array}{r}(sk,pk)\gets Gen(1^n)\\x\gets \zo^n\end{array}\]\leq \mu(n)\enspace.
$$
\end{itemize}
\end{definition}
On the surface, TDFs seem like a simpler object than PKE. In particular, they only guarantee that random messages $x$ are hard to fully recover, but they certainly don't guarantee to fully hide any input $x$. In fact, for any two messages $x,x'$ you can always easily tell $F_{pk}(x)$ and $F_{pk}(x')$, as $F_{pk}$ is deterministic. Historically, this is still how people imagined using TDFs for several years, until the work of Goldwasser and Micali \cite{GM82} who introduced {\em probabilistic encryption} and the requirement that encryption leaks nothing about plaintexts, which later became the gold standard.\footnote{This requirement, which we have so far formalized as indistinguishability, also has an alternative formulation known as semantic security, which we might mention later on.}
Formally, however, public-key encryption is not known to be stronger than TDFs --- they are not known to imply TDFs (think why a PKE scheme isn't already a TDF by itself). In contrast, the other direction is true.
\begin{theorem}
TDFs imply PKE.
\end{theorem}
\begin{proof}[Proof Sketch]
Let $(Gen,F,F^{-1})$ be a TDF. We define a PKE $(Gen,E,D)$ for one-bit messages.
\begin{itemize}
\item The $Gen$ algorithms are the same (as suggested by our notation).
\item $E_{pk}(m)$ samples $x,r \gets \zo^n$, and outputs
$$
F_{pk}(x),r,\langle x,r\rangle \oplus m\enspace.
$$
\item
$D_{sk}(y,r,b)$ outputs $\langle F_{sk}^{-1}(y),r \rangle \oplus b$.
\end{itemize}
%
The correctness of the scheme is obvious. As for security, by the Goldreich-Levin theorem, we know that
$$
pk,F_{pk}(x),r,\langle x,r\rangle \approx_c pk,F_{pk}(x),r,u\enspace,
$$
where $pk\gets Gen(1^n), x,r\gets\zo^n, u\gets \zo$.
The above already implies that
$$
pk,E_{pk}(0) \approx_c pk,E_{pk}(1)\enspace.
$$
In the homework, you will prove that in the case of PKE, the above is equivalent to CPA security:
\begin{claim}\label{clm:bitcpa}
A bitwise PKE is CPA secure if and only if $pk,E_{pk}(0) \approx_c pk,E_{pk}(1)$.
\end{claim}
\end{proof}
\medskip\noindent
Diffie and Hellman defined trapdoor functions and demonstrated how to use them for encryption (although, in a deterministic fashion. This is before Goldwasser-Micali and Goldreich-Levin). However, they did not provide a candidate for such functions (they did provide a direct construction of PKE, which we'll touch in a bit).
\paragraph{RSA.} The first trapdoor function that (publicly) emerged to the world in 1977 was suggested by Rivest, Shamir, and Adleman \cite{RSA78}, which became to be known as the RSA function. The trapdoor function, or actually permutation (TDP), is based on a number-theoretic problem related to factoring. We'll briefly present it, just to get a sense of how it looks, without getting too much into details.
\def \ZZ {\mathbb{Z}}
\begin{itemize}
\item
Let $p