%% 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}{2}
\newcommand{\duedate}{October 7} % 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} and \emph{clarity}.
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 and/or sources}} for each problem.
% QUESTIONS START HERE. PROVIDE SOLUTIONS WITHIN THE "solution"
% ENVIRONMENTS FOLLOWING EACH QUESTION.
\begin{questions}
\question Show that an LLL-reduced basis $\matB$ of a lattice $\lat$
satisfies the following properties:
\begin{parts}
\part $\length{\vecb_{1}} \leq 2^{(n-1)/4} \det(\lat)^{1/n}$.
\begin{solution}
\end{solution}
\part $\length{\vecb_{2}} \leq 2^{n/4} \cdot
(\det(\lat)/\length{\vecb_{1}})^{1/(n-1)}$
\begin{solution}
\end{solution}
\part There exists a shortest nonzero vector in $\lat$ whose
coefficients with respect to $\matB$ all have magnitudes at most
$2^{cn}$ for some constant $c$.\footnote{In particular, this lets
us solve SVP in time $2^{O(n^{2})} \cdot \poly(\len{\matB})$, by
running LLL and then enumerating coefficient vectors.}
\begin{solution}
\end{solution}
\end{parts}
\question The \emph{covering radius} $\mu(\lat)$ of an
$n$-dimensional lattice $\lat$ is the smallest radius $r$ such that
balls of radius~$r$ centered at lattice points cover all of
$\R^{n}$, i.e., $\R^{n} = \cup_{\vecv \in \lat} (\vecv + r \ball)$.
Equivalently, it is the maximum possible distance that a point in
$\R^{n}$ can be from the lattice.
\begin{parts}
\part Prove that $\mu(\lat) \geq
\lambda_{1}(\lat)/2$.\label{item:mu-lower}
\begin{solution}
\end{solution}
\part Demonstrate a lattice whose ratio of covering radius to
minimum distance is $\mu(\lat)/\lambda_{1}(\lat) =
\Omega(\sqrt{n})$.
\begin{solution}
\end{solution}
\part Prove that if $\matB$ is a basis of $\lat$, then $\mu(\lat)
\leq \frac12 \sqrt{\sum_{i} \length{\gs{\vecb}_{i}}^{2}}$.
\begin{solution}
\end{solution}
\part Another way of stating Minkowski's theorem is that
$\lambda_{1}(\lat) \leq 2(\det(\lat)/V_{n})^{1/n}$, where $V_{n}$
is the volume of an $n$-dimensional ball of radius 1.
Prove the \emph{lower} bound $\mu(\lat) \geq
(\det(\lat)/V_{n})^{1/n}$. \footnote{Note that this implies the
statement from part~(\ref{item:mu-lower}), but with a much more
sophisticated proof!}
\begin{solution}
\end{solution}
\end{parts}
\question Suppose we are given $N=pq$ for some unknown $n$-bit
primes $p,q$, along with a little more than half of the most
significant bits of $p$. More precisely, we are given some $P$ such
that $p = P + x_{0}$ where $\abs{x_{0}} \leq B = p^{1/2-\epsilon}$.
In this problem you will show that given this information, we can
factor $N$ efficiently.
Modulo $p$, the polynomial $f(x) = P + x$ of degree $d=1$ clearly
has a small root $x_{0} = p-P$, where
$\abs{x_{0}} \leq p^{1/2-\epsilon} \ll p^{1/d}$. But we do not know
$p$, so we cannot simply apply Coppersmith's theorem as-is.
Fortunately, we do know a multiple of $p$, namely $N$. This will be
enough to apply Coppersmith's method.
\begin{parts}
\part Let $h$ be an integer to be determined later. The $h+1$
polynomials
\[ f(x)^{h}, x \cdot f(x)^{h}, \ldots, x^{h} \cdot f(x)^{h} \] are
clearly all zero modulo $p^{h}$ when evaluated at $x_{0}$. Find
$h$ more polynomials having this property, and which work for the
remainder of this problem.
\begin{solution}
\end{solution}
\part Define an appropriate lattice basis using the $2h+1$
polynomials from the previous part, and analyze the determinant
and length bound guaranteed by LLL.
\begin{solution}
\end{solution}
\part Prove that for an appropriate choice of $h$, LLL returns a
vector corresponding to a polynomial having~$x_{0}$ as a root over
the integers, and argue that this allows us factor $N$
efficiently.
\begin{solution}
\end{solution}
\end{parts}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: