%% HOW TO USE THIS TEMPLATE:
%%
%% Ensure that you replace "YOUR NAME HERE" with your own name, in the
%% \studentname command below. Also ensure that the "answers" option
%% appears within the square brackets of the \documentclass command,
%% otherwise latex will suppress your solutions when compiling.
%%
%% Type your solution to each problem part within
%% the \begin{solution} \end{solution} environment immediately
%% following it. Use any of the macros or notation from the
%% header.tex that you need, or use your own (but try to stay
%% consistent with the notation used in the problem).
%%
%% If you have problems compiling this file, you may lack the
%% header.tex file (available on the course web page), or your system
%% may lack some LaTeX packages. The "exam" package (required) is
%% available at:
%%
%% http://mirror.ctan.org/macros/latex/contrib/exam/exam.cls
%%
%% Other packages can be found at ctan.org, or you may just comment
%% them out (only the exam and ams* packages are absolutely required).
% the "answers" option causes the solutions to be printed
\documentclass[11pt,addpoints]{exam}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
% any of the following packages may be safely omitted if they are not
% available on your system (but they should be)
\usepackage{fullpage}
\usepackage{times}
\usepackage{hyperref}
\usepackage{pdfsync}
\usepackage{microtype}
% required macros -- get header.tex file from course web page
\input{header}
% VARIABLES
\newcommand{\hwnum}{1}
\newcommand{\duedate}{January 27} % changing this does not change the
% actual due date :)
\newcommand{\studentname}{YOUR NAME HERE}
% END OF SUPPLIED VARIABLES
\hwheader % execute homework commands
\begin{document}
\pagestyle{head} % put header on every page
\noindent This homework is due by the \textbf{start of class on
\duedate} via the
\href{https://t-square.gatech.edu/portal/site/29001.201102/}{course
page on T-Square}. Start early!
\medskip
\noindent \textbf{Instructions.} Solutions must be typeset in \LaTeX\
(a template for this homework is available on the course web page).
Your work will be graded on \emph{correctness}, \emph{clarity}, and
\emph{conciseness}. You should only submit work that you believe to
be correct; if you cannot solve a problem completely, you will get
significantly more partial credit if you clearly identify the gap(s)
in your solution. It is good practice to start any long solution with
an informal (but accurate) ``proof summary'' that describes the main
idea.
\medskip
\noindent You may collaborate with others on this problem set and
consult external sources. However, you must \textbf{\emph{write your
own solutions}} and \textbf{\emph{list your
collaborators/sources}} for each problem.
% QUESTIONS START HERE. PROVIDE SOLUTIONS WITHIN THE "solution"
% ENVIRONMENTS FOLLOWING EACH QUESTION.
\begin{questions}
\question[5] \emph{(Due by mid-day on Wed, Jan 19.)} Send email to
Chris (\texttt{cpeikert@cc.gatech.edu}) with subject \texttt{8803TFC
student} containing (1) a few sentences about yourself and your
background (including your department and graduate program), (2)
what you hope to get out of this course, and (3) your comfort level
with the following: mathematical proofs, elementary probability
theory, big-O notation and analysis of algorithms, Turing machines,
and $\P$, $\BPP$, $\NP$, and $\NP$-completeness. Please also
mention any courses you've taken covering these topics.
\question \emph{(Perfect secrecy.)} Prove or disprove (giving the
simplest counterexample you can find) the following statements about
perfect secrecy for shared-key encryption. You may use any of the
facts from class.
\begin{parts}
\part[2\half] There is a perfectly secret encryption scheme for
which the ciphertext always reveals 99\% of the bits of the key
$k$ to the adversary.
\begin{solution}
\end{solution}
\part[2\half] In a perfectly secret encryption scheme, the
ciphertext is uniformly random. That is, for every $m \in
\msgspace$, the probability $\Pr_{k \gets \skcgen}[\skcenc_{k}(m)
= \bar{c}]$ is the same for every ciphertext $\bar{c} \in
\ctspace$.
\begin{solution}
\end{solution}
\part[5] Perfect secrecy is equivalent to the following
definition, which says that the adversary cannot determine which
of two messages was encrypted any better than by random guessing.
Formally, for any $m_{0}, m_{1} \in \msgspace$, and any function
$\Adv : \ctspace \to \bit$,
\[ \Pr_{k \gets \skcgen,\; b \gets \bit}[\Adv(\skcenc_{k}(m_{b}))
= b] = \frac{1}{2}. \]
\begin{solution}
\end{solution}
\part[5] Perfect secrecy is equivalent to the following
definition, which says that the ciphertext and message are
independent (as random variables). Formally, for any probability
distribution $\calD$ over the message space $\msgspace$ and any
$\bar{m} \in \msgspace$ and $\bar{c} \in \ctspace$,
\[ \Pr_{m \gets \calD,\; k \gets \skcgen}[ m = \bar{m} \wedge
\skcenc_{k}(m) = \bar{c}] = \Pr_{m \gets \calD}[m = \bar{m}] \cdot
\Pr_{m \gets \calD,\; k \gets \skcgen}[\skcenc_{k}(m) =
\bar{c}]. \]
\begin{solution}
\end{solution}
\end{parts}
\question \emph{(Working with negligible functions.)} Recall that a
non-negative function $\nu : \N \to \R$ is \emph{negligible} if it
decreases faster than the inverse of any polynomial (otherwise, we
say that $\nu$ is \emph{non-negligible}). More precisely, $\nu(n) =
o(n^{-c})$ for every fixed constant $c > 0$, or equivalently,
$\lim_{n \to \infty} \nu(n) \cdot n^{c} = 0$.
State whether each of the following functions is negligible or
non-negligible, and give a brief justification. In the following,
$\negl(n)$ denotes some arbitrary negligible function, and
$\poly(n)$ denotes some arbitrary polynomial in $n$.
\begin{parts}
\part[1] $\nu(n) = 1/2^{100 \log n}$.
\begin{solution}
\end{solution}
\part[1] $\nu(n) = n^{-\log \log \log n}$. \hfill {\small
(Compare with the previous item for ``reasonable'' values of
$n$.)}
\begin{solution}
\end{solution}
\part[1] $\nu(n) = \poly(n) \cdot \negl(n)$. \hfill {\small (State
whether $\nu$ is \emph{always} negligible, or not necessarily.)}
\begin{solution}
\end{solution}
\part[1] $\nu(n) = (\negl(n))^{1/\poly(n)}$. \hfill {\small (Same
instructions as previous item.)}
\begin{solution}
\end{solution}
\part[1] \[ \nu(n) =
\begin{cases}
2^{-n} & \text{if $n$ is composite} \\
100^{-100} & \text{if $n$ is prime.}
\end{cases}
\]
\begin{solution}
\end{solution}
\end{parts}
\question \emph{(Working with one-way functions.)}
\begin{parts}
\part[5] Suppose that $f : \bit^{*} \to \bit^{*}$ is such that
$\len{f(x)} \leq c \log \len{x}$ for every $x \in \bit^{*}$, where
$c > 0$ is some fixed constant. (Here $\len{\cdot}$ denotes the
length of a string.)
Prove that $f$ is \emph{not} a one-way function. (You may use a
\emph{non-uniform} inverter in your solution; for one bonus point,
use a uniform one.)
\begin{solution}
\end{solution}
\part[5] Finish the proof of the hardness amplification theorem
from the lecture, i.e., define and analyze the algorithm $\Adv$
that uses $\Adv'$. You may use any of the ideas and facts from
the lecture notes.
\begin{solution}
\end{solution}
\part[5] Prove that there exists a collection $\set{f_{i}}$ of
one-way functions if and only if there exists a one-way function
$f$. (\emph{Hint}: incorporate the collection's generation
algorithm $\algo{Gen}$, and its randomness, into the definition of
$f$.)
\begin{solution}
\end{solution}
\end{parts}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: