\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\else % if luatex or xelatex
\ifxetex
\usepackage{mathspec}
\else
\usepackage{fontspec}
\fi
\defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\PassOptionsToPackage{hyphens}{url} % url is loaded by hyperref
\usepackage[unicode=true]{hyperref}
\hypersetup{
pdfborder={0 0 0},
breaklinks=true}
\urlstyle{same} % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother
\date{}
\begin{document}
\section{CS 127 Spring 2018 - Homework
Zero}\label{cs-127-spring-2018---homework-zero}
Due on \textbf{Thursday January 25 at midnight} but I recommend you do
this homework even before the first lecture.
Please write the names of yourself and your collaborators below: (this
page does not contain any solutions, and so is not viewed by the people
grading your problems on gradescope.)
\textbf{Collaboration policy for homework zero:} You can work on this
problem set and submit it in \textbf{groups of one or two students}. In
addition you can discuss these problems with other students that are
considering taking this course. However, each pair needs to write up
their solution on their own, and you need to write down the names of
your collaborators below.
\textbf{Submitters:} (List your names and HUIDs here)
\textbf{Collaborators:} (List here anyone you discussed problems or
ideas for solutions with)
If submitting late, for every pair member add a sentence of the form
\textbf{``Submitting X days late, Y has used (including this time) Z
days out of the 6 total late days''}
For any questions or clarifications, please see the Piazza board. See
the \href{https://www.boazbarak.org/cs127/syllabus/}{course syllabus} for
policies.
This homework needs to be submitted as a PDF document. The PDF can be
generated using either markdown or LaTeX. The Markdown source for this
homework is posted online.
\newpage
\subsection{Probability questions}\label{probability-questions}
As we'll see in the first lecture, much of cryptography relies on
probability theory, and so basic knowledge of probability will be
essential. The
\href{http://www.introtcs.org/public/lec_15_probability.pdf}{CS 121
probability review} is one source for the probability theory we will
need. During the course I will assume you are familiar with (or can pick
on your own) all notions presented there. However, if you find these
questions unfamiliar or difficult you should not despair! There are
plenty of sources on probability on the web, and in particular Harvard
STAT 110 and its textbook are of course wonderful resources. If any of
the notation is unfamiliar, looking at the lecture notes might help, and
otherwise feel free to ask questions on Piazza, even before the semester
starts!
\textbf{Notation:} While often in probability theory people use the name
``random variable'' for a distribution over the set \(\mathbb{R}\) of
real numbers, it will be convenient for us to generalize this to
arbitrary sets, and hence we will use the following notation. We define
a \emph{random variable} or \emph{distribution} \(X\) over a finite set
\(S\) to correspond to the probabilistic experiment where we draw an
element \(x\) from \(S\) with some probability, which we denote by
\(\Pr[ X=x]\). All we need from these probabilities is that they are
non-negative and sum up to one. (One can also consider distributions
over infinite sets, though almost always in this course we will restrict
ourselves to the finite case.) We use \(x \leftarrow_R X\) as shorthand
for saying that \(x\) is drawn accoring to the distribution \(X\). If
\(f:S \rightarrow T\) is a function, then the random variable \(f(X)\)
corresponds to the probabilistic experiment where we draw
\(x \leftarrow_R X\) and output \(f(x)\).
\textbf{Question 0.} Join the course Piazza board at
\url{http://piazza.com/harvard/spring2018/cs127}.
\newpage
In this question we will study the notion known as
\href{https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures}{Total
Variation} or statistical distance. It is a basic notion of distance
between probability distribution, and its computational analog is
fundamental for cryptography.
\textbf{Question 1.1:} If \(X\) and \(Y\) are two distributions over the
same set \(S\), we define \(\Delta(X,Y)\) (also known as the
\emph{statistical} or \emph{total variation} distance of \(X\) and
\(Y\)) to be \(\sum_{x\in S} | \Pr[X=x]- \Pr[Y=x] |\). Prove that for
every function \(f:S \rightarrow [0,1]\),
\(| \mathbb{E}[f(X)] - \mathbb{E}[f(Y)] | \leq \Delta(X,Y)\).
\textbf{Solution 1.1:}
\textbf{Question 1.2:} Prove that the statistical distance satisfies the
\emph{triangle inequality}: For every three distributions \(X,Y,Z\) over
the same set \(S\), \(\Delta(X,Z) \leq \Delta(X,Y)+ \Delta(Y,Z)\).
\textbf{Solution 1.2:}
\newpage
We will now use the notion of statistical distance to study one of the
most basic questions in probability theory: if we are given a coin that
is either completely unbiased, or has bias \(\epsilon>0\) towards
``heads'', how many tosses will it take for us to distinguish between
the two cases.
\textbf{Question 2:} Prove that this can be done in at most
\(O(1/\epsilon^2)\) coin tosses. Specifically prove that if
\(k>100/\epsilon^2\), then there exists some function
\(f:\{0,1\}^k \rightarrow \{0,1\}\) such that if \(X\) is the uniform
distribution over \(\{0,1\}^k\) and \(Y\) is the distribution obtained
by tossing \(k\) independent coins, each equalling \(1\) with
probability \(1/2+\epsilon\) and equalling \(0\) with probability
\(1/2-\epsilon\), then \(\Pr[ f(X)=0 ] > 0.9\) and
\(\Pr[ f(Y) = 1 ] > 0.9\), and hence \(f\) can distinguish between \(X\)
and \(Y\).\footnote{\textbf{Hint:} Use the Chernoff bound.}
\textbf{Solution 3:}
\newpage
We now study the converse problem: showing a \emph{lower bound} on the
number of coin tosses needed.
\textbf{Question 3.1:} (This problem involves some notation, so take
your time reading it carefully and parsing what it means.) For every
\(k \in \mathbb{N}\), \(0 \leq i \leq k\), and \(\epsilon>0\), let
\(X^{k,\epsilon}_i\) be the following distribution over \(\{0,1\}^k\):
the first \(i\) bits of \(X^{k,\epsilon}_i\) are chosen independently
and uniformly at random, and the last \(k-i\) bits are chosen
independently at random with but each is equal to \(1\) with probability
\(1/2+\epsilon\) and equal to \(0\) with probability \(1/2-\epsilon\).
Prove that for very \(k\), \(i 0.9\)
and \(\Pr[ f(Y) = 1 ] > 0.9\). Use your solution for Question 3.1 (this
is a special case of the
\href{https://en.wikipedia.org/wiki/Hybrid_argument_(Cryptography)}{Hybrid
Argument} which is used time and again in cryptography).
\textbf{Solution 3.2:}
\newpage
\textbf{Question 4 (bonus problem: optional and more challenging):}
Prove that in fact \(\Delta(X,Y) \leq O(\sqrt{k}\epsilon)\).\footnote{\textbf{Hint:}
One way to prove this is to use the notion of KL divergence which is
another notion of distance between the distributions that satisfies
the triangle inequality. You can show that the KL divergence of
\(X^{k,\epsilon}_i\) and \(X^{k,\epsilon}_{i+1}\) is \(O(\epsilon^2)\)
and then use the Pinsker Inequality that shows that the statistical
distance between two distributions is at most the square root of their
KL divergence. You can read about both KL divergence and the Pinsker
Inequality in Wikipedia as well in several other sources.} Conclude
that the method of Question 2 is essentially \emph{optimal} in the sense
that there exist some absolute constant \(\delta\) (independent of
\(\epsilon\)) such that for every \(\epsilon\) and distribution \(X,Y\)
as in Question 2, if \(k< \delta/\epsilon^2\) then there does not exists
a function \(f:\{0,1\}^k \rightarrow \{0,1\}\) such that
\(\Pr[ f(X)=0 ] > 0.9\) and \(\Pr[ f(Y) = 1 ] > 0.9\).
\textbf{Solution 4:}
\newpage
\subsection{And now for a little
crypto}\label{and-now-for-a-little-crypto}
\textbf{Question 5 (very important! but no grades :) ):} Read the
lecture notes for
\href{http://www.intensecrypto.org/public/lec_01_introduction.pdf}{lecture
1: introduction}.
\textbf{Solution 5:} Write here ``I solemnly swear that I read every
word of the lecture notes''. (Just kidding, I trust you, and in any case
I expect you to read every word \emph{twice}.)
\textbf{Question 6:} Prove that an encryption scheme \((E,D)\) with
messages of length \(\ell\) and keys of length \(n\) is \emph{perfectly
secret} if and only for every \(x,x' \in \{0,1\}^\ell\),
\(\Delta(Y^x,Y^{x'})=0\), where \(Y^x\) is the distribution obtained by
choosing a random \(k \leftarrow_R \{0,1\}^n\) and outputting
\(E_k(x)\).
\textbf{Solution 6:}
\end{document}