%% 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 latest header.tex file from course web page
\input{header}
% VARIABLES
\newcommand{\hwnum}{4}
\newcommand{\duedate}{March 10} % 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[25] \emph{(Authenticated encryption and chosen-ciphertext
security.)}
\begin{parts}
\part[15] Let $\skc = (\skcgen, \skcenc, \skcdec)$ be an
IND-CPA-secure shared-key encryption scheme, and let $\mac =
(\macgen, \mactag, \macver)$ be a SUF-CMA-secure MAC. For each of
the following schemes $\skc' = (\skcgen', \skcenc', \skcdec')$,
consider whether it is a secure \emph{authenticated encryption}
scheme, as defined in class (see the lecture notes for a precise
definition). If it is, then prove it; otherwise, give the
simplest counterexample you can find.
In all of the schemes below, $\skcgen'$ works as follows: let
$k_{a} \gets \mac.\macgen$ and $k_{e} \gets \skc.\skcgen$, and
output $k=(k_{a}, k_{e})$.
\begin{subparts}
\subpart $\skcenc'_{k}(m)$: let $c \gets
\skcenc_{k_{e}}(m)$ and $t \gets \mactag_{k_{a}}(m)$. Output
$c'=(c,t)$.
$\skcdec'_{k}(c'=(c,t))$: let $m \gets
\skcdec_{k_{e}}(c)$. If $\macver_{k_{a}}(m,t)$ rejects, output
$\bot$; else, output $m$.
\begin{solution}
\end{solution}
\subpart $\skcenc'_{k}(m)$: let $t \gets \mactag_{k_{a}}(m)$ and
output $c' \gets \skcenc_{k_{e}}((m,t))$.
$\skcdec'_{k}(c')$: let $(m,t) \gets \skcdec_{k_{e}}(c')$. If
$\macver_{k_{a}}(m,t)$ rejects, output $\bot$; else, output $m$.
\begin{solution}
\end{solution}
\subpart $\skcenc'_{k}(m)$: let $c \gets
\skcenc_{k_{e}}(m)$ and $t \gets \mactag_{k_{a}}(c)$. Output
$c' = (c,t)$.
$\skcdec'_{k}(c' = (c,t))$: if $\macver_{k_{a}}(c,t)$ rejects,
output $\bot$. Otherwise, output $\skcdec_{k_{e}}(c)$.
\begin{solution}
\end{solution}
\end{subparts}
\part[10] Prove that any secure authenticated encryption scheme
$\scheme{AE} = (\skcgen, \skcenc, \skcdec)$ is itself
IND-CCA-secure, as defined in class.
(\emph{Hint}: consider a hybrid IND-CCA experiment in which the
decryption oracle decrypts \emph{only} ciphertexts that were
already returned by the encryption oracle, and answers $\bot$ on
all others. Use $\scheme{AE}$'s unforgeability to prove that this
experiment is indistinguishable from the real IND-CCA attack.
Then show how to simulate the hybrid IND-CCA experiment given only
the ability to mount an IND-CPA attack on $\scheme{AE}$.)
\begin{solution}
\end{solution}
\end{parts}
\question \emph{(Collision-resistance potpourri.)} Prove or
disprove (giving the simplest counterexample you can find) each of
the following statements about collision-resistant hashing.
\begin{parts}
\part[5] A collision-resistant hash function family $\calH =
\set{h_{s} \colon \bit^{2n} \to \bit^{n}}$ is a one-way function
family. (\emph{Hint}: bound the number of inputs to $h_{s}$ that
do not collide with any other input.)
\begin{solution}
\end{solution}
\part[5] Same as the previous part, but with $\calH = \set{h_{s}
\colon \bit^{n+1} \to \bit^{n}}$.
\begin{solution}
\end{solution}
\part[5] Let $G = \langle g \rangle$ be a cyclic group of prime
order $q$, and let fixed $t \geq 2$ be any fixed integer. Define
the hash function family $\calH = \set{h_{g_{1},\ldots,g_{t}}
\colon \Zq^{t} \to G \mid g_{i} \in G}$ as \[
h_{g_{1},\ldots,g_{t}}(x_{1}, \ldots, x_{t}) = \prod_{i \in [t]}
g_{i}^{x_{i}} \in G. \] If solving the discrete logarithm problem
in $G$ is hard, then $\calH$ is a collision-resistant hash
function family. (\emph{Hint}: given a discrete logarithm
challenge $(g,y)$, let $g_{i}=g^{a_{i}} \cdot y^{b_{i}} \in G$ for
uniformly random $a_{i}, b_{i} \gets \Zq$. How does a
collision help you compute $\log_{g}(y)$? Be careful!)
\begin{solution}
\end{solution}
\end{parts}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: