%% 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}{3}
\newcommand{\duedate}{February 24} % 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[10] Recall that multi-message \emph{non-adaptive} security
for a symmetric-key encryption scheme $(\skcgen,\skcenc,\skcdec)$
says that for any $q=\poly(n)$ and any tuples $(m_{1}, \ldots,
m_{q}), (m'_{1}, \ldots, m'_{q}) \in \msgspace^{q}$, it should be
the case that
\[ \left\{ k \gets \skcgen :
(\skcenc_{k}(m_{1}),\ldots,\skcenc_{k}(m_{q})) \right\} \compind
\left\{ k \gets \skcgen :
(\skcenc_{k}(m'_{1}),\ldots,\skcenc_{k}(m'_{q})) \right\}. \] In
contrast, \emph{adaptive} security says that the following two
oracles are indistinguishable:
\[ \left\langle k \gets \skcgen : \skcenc^{0}_{k}(\cdot,\cdot)
\right\rangle \compind \left\langle k \gets \skcgen :
\skcenc^{1}_{k}(\cdot,\cdot) \right\rangle, \] where
$\skcenc^{b}_{k}(m_{0},m_{1})$ outputs $\skcenc_{k}(m_{b})$. Give a
separation between these two definitions, i.e., construct a
(possibly contrived) scheme and prove it secure according to the
former definition (under some standard assumption), while showing
that it is definitely insecure according to the latter definition.
\question In a network where all communication is via broadcast
(e.g., wi-fi), we might want communication to be \emph{anonymous}.
That is, the adversary should not be able to learn, given an
(encrypted) message, anything about who the sender and intended
receiver are.
\begin{parts}
\part[5] Give a simple but formal definition of \emph{anonymity}
under adaptive chosen-plaintext attack for a symmetric-key
encryption scheme $(\skcgen, \skcenc, \skcdec)$. The syntax of
your definition should capture \emph{only} the intuition that it
is hard to distinguish which key was used to produce the queried
ciphertexts.
\part[5] Does your anonymity definition imply our standard
security notion of IND-CPA (indistinguishability under adaptive
chosen-plaintext attack)? If so, prove it; otherwise, give the
simplest counterexample you can find, \emph{and} provide a
definition that captures both anonymity and IND-CPA. (In
constructing your counterexample, you may rely on any reasonable
cryptographic assumption).
\part[5] Does the PRF-based encryption scheme from class satisfy
your definition of anonymity? If so, prove it; otherwise,
describe a PRF family for which the encryption scheme is not
anonymous. (As usual, your counterexample may use any reasonable
cryptographic assumption.)
\end{parts}
\question[15] \emph{(The power of Decision Diffie-Hellman.)} In
class we saw that the DDH assumption can be used for public-key
encryption; here you will show that it is very useful for
\emph{symmetric} primitives too.
For a cyclic group $G = \langle g \rangle$ of \emph{prime} order
$q$, the DDH assumption says that \[ (g, g^{a}, g^{b}, g^{ab})
\compind (g, g^{a}, g^{b}, g^{c}), \] where $a, b, c \gets \Zq$ are
uniformly random and independent. By grouping the elements
appropriately, we can view this assumption in matrix form:
\[ g^{
\begin{pmatrix}
1 & a \\ 1 \cdot b & a \cdot b
\end{pmatrix}} \compind
g^{
\begin{pmatrix}
1 & a \\ b & c
\end{pmatrix}
}, \] where $g^{M}$ (for a matrix $M$ over $\Zq$) is the matrix over
$G$ obtained by raising $g$ to each entry of $M$. Observe that in
the left-hand matrix, the two rows are linearly dependent (over
$\Zq$), while in the right-hand matrix they are very likely not to
be.
\begin{parts}
\part[7] Prove that the DDH assumption implies that, for any
positive integer $w=\poly(n)$,
\[ g^{
\begin{pmatrix}
a_{1} & a_{2} & \cdots & a_{w} \\
a_{1} \cdot b & a_{2} \cdot b & \cdots & a_{w} \cdot b
\end{pmatrix}
} \compind
g^{
\begin{pmatrix}
a_{1} & a_{2} & \cdots & a_{w} \\
c_{1} & c_{2} & \cdots & c_{w}
\end{pmatrix}
}, \] where $a_{i}, b, c_{i} \gets \Zq$ are all uniformly random
and independent.
\begin{solution}
% In your solution, you can delete the lead-in to this problem
\end{solution}
\part[4] Using the previous part, prove that the DDH assumption
implies that, for any positive integers $w, h = \poly(n)$,
\[ g^{
\begin{pmatrix}
a_{i} \cdot b_{j}
\end{pmatrix}_{i \in [h],j \in [w]}
} \compind g^{
\begin{pmatrix}
c_{i,j}
\end{pmatrix}_{i \in [h], j \in [w]} }, \] where $a_{i}, b_{j},
c_{i,j} \gets \Zq$ are all uniformly random and independent. Note
that the left-hand matrix (in the exponent) has rank $1$, while
the right-hand matrix is very likely to be full-rank.
\begin{solution}
\end{solution}
\part[4] Conclude that under the DDH assumption, there is a PRG
family expanding about $2n \lg q$ bits to about $n^{2} \lg q$
bits. (The output need not literally be made up of bits, though.)
For the same input and output lengths, why might we prefer this
PRG to the one from class based on a OWP?
\begin{solution}
\end{solution}
\part[0] \emph{(Challenge question.)} Generalize the above to
design a pseudorandom \emph{function} based on DDH. (\emph{Hint}:
extend to $2 \times 2 \times \cdots \times 2$ matrices.)
\begin{solution}
\end{solution}
\end{parts}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: