\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\eqdef}{\stackrel{def}{=}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\indist}{\approx}
\newcommand{\dist}{\Delta}
\newtheorem{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newcommand{\Adv}{\ensuremath{\mathsf{Adv}}}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{SAT}}}
\newcommand{\COL}{\ensuremath{\mathsf{3COL}}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\Time}{\cclass{Time}}
\newcommand{\BPP}{\cclass{BPP}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Handout 2: Perfect and Statistical Secrecy, Computational Models}
\author{Boaz Barak}
\date{Exercises due Tuesday September 27, 2005 1:30pm\\
Total of $130$ points.}
\begin{document}
\maketitle
\section{Suggested Reading}
Perfect secrecy is covered in Bellare's and Golwasser-Bellare
lecture notes (see the web site for links). Computational models
such as Boolean circuits and probabilistic computation are covered
in Sipser's book pages 251--260 (Boolean circuits) and 368--375
(probabilistic algorithms).
\section{Perfect security and statistical closeness}
\begin{exercise}[15 points] Show formally that the following schemes do
\emph{not} satisfy the definition of perfect security (you can
choose the most convenient of the 3 equivalent definitions to
demonstrate this).
Notation: we use $\Z_n$ to denote the set of numbers
$\{0,\ldots,26-1\}$. We identify the letters of the English alphabet
with $\Z_{26}$ in the obvious way. We denote by $\ell$ the length of
the plaintext $p$.
\begin{enumerate}
\item Caesar cipher (Key: a random $k \getsr \Z_{26}$. Encryption:
$E_k(p_1,\ldots,p_{\ell}) = (p_1+k,\ldots,p_{\ell}+k) \pmod{26}$)
\item Substitution cipher (key: a random permutation
$\pi:\Z_{26}\To\Z_{26}$, encryption: $E_{\pi}(p_1,\ldots,p_{\ell}) =
(\pi(p_1),\ldots,\pi(p_{\ell})$.
\item ``Two-time pad''. Key: $\getsr \bits^{\ell/2}$ (assume
plaintext are over Binary alphabet and of even length). Encryption
$E_k(p_1,\ldots,p_{\ell}) = (p_1 \oplus k_1, \ldots,
p_{\ell/2}\oplus k_{\ell/2} , p_{\ell/2+1}\oplus k_1,\ldots ,
p_{\ell} \oplus k_{\ell/2})$.
\end{enumerate}
\end{exercise}
\begin{exercise}[15 points] Describe (in words, without proofs) how you could
extend the one-time pad into an encryption with similar security
that allows to encrypt \emph{multiple messages} with the same key,
as long as the total length of all the messages is less than the
length of the key.
You are allowed to use a \emph{stateful encryption}. That is, both
the encryption algorithm and decryption algorithm can maintain a
state variable/register that is updated from encryption to
encryption. Is it possible to do so without using state for the
decryption algorithm? what about the encryption algorithm?
\end{exercise}
\begin{exercise}[20 points] Give examples (with proofs) for
\begin{enumerate}
\item A scheme such that it is possible
to efficiently recover $90\%$ of the bits of the key given the
ciphertext, and yet it is still perfectly secure. Do you think there
is a security issue in using such a scheme in practice?
\item An encryption scheme that is \emph{insecure} but yet it
provably hides the first $20\%$ bits of the key. That is, if the key
is of length $n$ then the probability that a computationally
unbounded adversary guesses the first $n/5$ bits of the key is at
most $2^{-n/5}$.
\end{enumerate}
You can use the results proven in class and above. Also the examples
need not be natural schemes but can be ``contrived'' schemes
specifically tailored to obtain a counter-example.
\end{exercise}
\begin{exercise}[20 points] Recall that we defined the statistical distance
of $X$ and $Y$, $\dist(X,Y)$ as follows: let $U$ denote the union of
the supports of $X$ and $Y$. For every set $T \subseteq U$, denote
$\dist_T(X,Y) = \left| \Pr[ X\in T] - \Pr[ Y\in T] \right|$. Then
$\dist(X,Y) = \max_T \dist_T(X,Y)$. Prove that
\begin{enumerate}
\item $\dist(X,Y) = \frac{1}{2} \sum_{u \in U} \left|
\Pr[ X = u ] - \Pr[ Y = u] \right|$
\item The statistical distance satisfies a
triangle inequality/ transitivity property. That is, for any three
random variables $X,Y,Z$,
\[
\dist(X,Z) \leq \dist(X,Y) + \dist(Y,Z)
\]
\end{enumerate}
\end{exercise}
\begin{exercise}[10 points]
Recall that a scheme is $\e$ statistically indistinguishable if in
the distinguishing between two messages game, the probability
adversary guesses the messages is at most $\tfrac{1}{2} + \e$. A
scheme satisfies $\e$-statistical secrecy if for every $x,x'$ the
distributions $Y_x$ and $Y_{x'}$ (defined to be $E_{U_n}(x)$ and
$E_{U_n}(x')$ respectively) satisfy $\dist(Y_x,Y_{x'}) \leq \e$.
Prove that a scheme $(E,D)$ is $\e$ statistically indistinguishable
if and only if it satisfies $2\e$-statistical secrecy.
\end{exercise}
\begin{exercise}[20 points] Suppose that $(D,E)$ is a valid
encryption scheme with key $100$ bit shorter than the plaintext.
That is, $E:\bits^n \times \bits^{n+100} \To \bits^m$ for some $n,m
\in \N$. Show that the scheme can be completely broken by an
explicit (although not necessarily efficient) \emph{algorithm}. That
is, show that there exist two messages $x_1,x_2$ and an algorithm
$\Adv$ (not necessarily efficient) such that
\[
\Pr_{i\in\{1,2\} \;,\; k\getsr \bits^n} [ \Adv( E_k(x_i)) = i ] >
0.99
\]
In rough terms (up to polynomial accuracy), what is the running time
of your algorithm?
Can you find a stronger attack if the message is of size $100n$?
Suppose that $\P=\NP$. Can you use that to find a faster algorithm?
\end{exercise}
\begin{exercise}[10 points] Read the handout on computational models.
Write down one question you want to know the answer for and is not
explained (or not explained clearly) in the handout.
\end{exercise}
\begin{exercise}[20 points] Consider the following three decision
problems/languages:
\begin{itemize}
\item $\CSAT$ - Circuit Satisfiability. \textbf{Input:} a Boolean circuit $C$ with
$n$ inputs and one output. \textbf{Output:} $1$ iff there exists
$x\in\bits^n$ such that $C(x)=1$.
\item $\SAT$ - satisfiability. \textbf{Input:} a 3CNF formula $\psi$ with inputs $x_1,
\ldots,x_n$. A 3CNF formula is a formula of the form $C_1 \wedge C_2
\wedge \cdots \wedge C_m$ where each of the $C_i$'s (called clauses)
is a disjunction $(l_1 \vee l_2 \vee l_3)$. Each of the $l_j$'s
(called literals) is either a variable $x_k$ or a negation of a
variable $\neg x_{k'}$. \textbf{Output:} $1$ iff there exists inputs
$x_1,\ldots,x_n$ that satisfy the formula.
\item $\COL$ - 3 colorability. \textbf{Input:} an undirected graph $G = (V,E)$
with $n$ vertices. \textbf{Output:} $1$ iff there exists a valid
$3$-coloring of $G$. A $3$-coloring is a function $c:V\To \{1,2,3\}$
such that for every $(u,v) \in E$, $c(u) \neq c(v)$.
\end{itemize}
\begin{enumerate}
\item Prove that all three problems are in $\NP$ (this should be
easy and take at most 1-2 lines for each problem)
\item $\CSAT$ is $\NP$-complete. Use that to prove that $\SAT$ is
$\NP$ complete. (Hint: the formula does not have to use the exact
same number of variables as the circuit - use additional auxiliary
variables that represent the circuit's internal gates.)
\item $\COL$ is $\NP$-complete. (Hint: use the previous item.) Note
that we'll actually use the fact that $\COL$ is $\NP$-complete
(much) later in the course.
\end{enumerate}
\noindent\textbf{Note:} These are classical results and appear in
many textbooks (including Sipser). Do not look at the proofs of
these results while solving this problem. (If you came across these
results earlier in a book/another course this is fine, but you
should not consult the book/your notes while solving this problem
and writing its solution.)
What is the $\NP$-completeness status of $\mathsf{2COL}$? (Same as
$\COL$ but with $2$ instead of $3$ colors, give a short 1-3 line
answer).
\iffalse
if you read this, feel free to solve these problems too :)
What is the $\NP$-completeness status of:
\begin{itemize}
\item $\mathsf{PLANAR-6COL}$ - (same as $\COL$ but with
$6$ colors and the graph is guaranteed to be planar\footnote{A graph
$G$ is \emph{planar} if it can drawn on a (2-dimensional) paper
without any edges crossing one another. Clearly, if you remove a
vertex and all its edges from a planar graph then it remains planar.
Also, it is known that every planar graph has a vertex of degree at
most $5$.}
\item $\mathsf{PLANAR-4COL}$
\end{itemize}
\fi
\end{exercise}
\end{document}