%% 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
%% head.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
%% head.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}
\usepackage{mathtools}
% 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{microtype}
\usepackage[svgnames]{xcolor}
\usepackage{tikz}
\hypersetup{%
colorlinks=true,% hyperlinks will be colored
}
% required macros -- get head.tex file from course web page
\input{head}
% VARIABLES
\newcommand{\hwnum}{4}
\newcommand{\duedate}{November 23} % 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{}{course
Canvas page}. 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.
\bigskip
\begin{questions}
\question Let $\matA \in \Zq^{n \times m}$ be a parity-check matrix
specifying the $q$-ary lattice
$\lat^{\perp}(\matA) = \set{\vecz \in \Z^{m} : \matA \vecz =
\veczero \in \Zq^{n}}$.
If you wish, throughout this problem you may assume that~$q$ is
prime (though this is not necessary hypothesis for any of the
conclusions).
\begin{parts}
\part Describe an efficient algorithm that finds an invertible
$n$-by-$n$ submatrix of $\matA$ which is invertible over $\Zq$, if
one exists. (For uniformly random $\matA$ and typically used $m$,
it can be shown that such a submatrix exists with high
probability.) Also argue that this invertible submatrix can be
moved to the first~$n$ columns of $\matA$, without essentially
changing the lattice.
\begin{solution}
\end{solution}
\part Prove that the invertible submatrix can be replaced by the
identity matrix $\matI_{n}$, possibly changing the rest of $\matA$
as well, without changing the lattice.
\begin{solution}
\end{solution}
\part Using the previous parts, describe how to efficiently
compute a basis of $\lat^{\perp}(\matA)$.
\emph{Hint:} if $\matA = [\matI_{n} \mid \bar{\matA}]$, then the
$n$ columns of $\left[
\begin{smallmatrix}
q\matI_{n} \\ \matzero
\end{smallmatrix} \right]$ are vectors in $\lat^{\perp}(\matA)$.
Find $m-n$ more columns, and prove that all $m$ columns together
form a basis $\matB$ of $\lat^{\perp}(\matA)$, i.e., $\matB \cdot
\Z^{m} = \lat^{\perp}(\matA)$.
\begin{solution}
\end{solution}
\part Recall that the SIS problem is to find a short nonzero
solution to $\matA \vecz = \veczero$ for uniformly random~$\matA$.
Using the previous parts, prove that the following problem is at
leas as hard as SIS: given uniformly random $\matA'$, find a short
nonzero solution to $\matA' \vecz = \vece \bmod q$, where
$\vece \in \Z^{n}$ is \emph{any} short vector of the attacker's
choice. \emph{Hint:} the number of columns need not be the same
in $\matA$ and $\matA'$.
\begin{solution}
\end{solution}
\end{parts}
\question Assume that decision-LWE is hard for some parameters $n$,
$q$ and error distribution $\chi$. That is, pairs of the form
\[ (\veca_{i}, b_{i} = \inner{\vecs, \veca_{i}} + e_{i}), \]
where $\vecs \gets \Zq^{n}$ is chosen once and for all and all the
$\veca_{i} \gets \Zq^{n}$ and $e_{i} \gets \chi$ are independent,
are pseudorandom (i.e., indistinguishable from uniformly random).
Prove that the ``multi-secret'' form of decision-LWE is also hard,
i.e., for any polynomially bounded~$t$, tuples of the following form
are pseudorandom:
\[ (\veca_{i}, b_{i,1} = \inner{\vecs_{1}, \veca} + e_{i,1}, \ldots,
b_{i,t} = \inner{\vecs_{t}, \veca} + e_{i,t}) \in \Zq^{n} \times
\Zq^{t}, \]
where each $\vecs_{j} \gets \Zq^{n}$ is chosen once and for all, and
the $\veca_{i} \gets \Zq^{n}$ and $e_{i,j} \gets \chi$ are
independent.
\emph{Hint:} use a ``hybrid'' argument: define a sequence of~$t+1$
distributions, where the first is the multi-secret LWE distribution
and the last is uniformly random. Show that distinguishing any pair
of adjacent distributions in the sequence is as hard as
decision-LWE.
\begin{solution}
\end{solution}
\question The public-key cryptosystems described in class encrypts a
single message bit using a ciphertext of $n \log q$ bits or more,
and a public key of $n^{2} \log q$ bits or more. This is quite a
large overhead! Extend at least one of those systems to securely
encrypt (say) $n$ message bits while preserving the ciphertext and
public key sizes, up to small constant factors. \emph{Hint:} use
the result from the previous question.
\begin{solution}
\end{solution}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: