\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{color}
%%%%%%%%%%%%%%% MACROS specific to this PSET %%%%%%%%%%%%%%%%%%%%%%
\newcommand{\lat}{\mathcal{L}}
\newcommand{\basis}{\mathbf{B}}
\newcommand{\vol}{\mathsf{vol}}
\newcommand{\sh}{\lambda_1}
%\newcommand{\det}{\mathsf{det}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
%%%%%%%%% Vectors and Matrices
\newcommand{\vecv}{\mathbf{v}}
\newcommand{\vecb}{\mathbf{b}}
\newcommand{\vecbt}{\widetilde{\vecb}}
\newcommand{\vecs}{\mathbf{s}}
\newcommand{\vect}{\mathbf{t}}
\newcommand{\vecy}{\mathbf{y}}
\newcommand{\matB}{\mathbf{B}}
\newcommand{\poly}{\mathsf{poly}}
\newcommand{\Span}{\mathsf{Span}}
\newcommand{\dist}{\mathsf{dist}}
\def\rot{\mathsf{Rot}}
\def\bydef{\stackrel{\Delta}{=}}
\def\matA{\mathbf{A}}
\def\vecy{\mathbf{y}}
\def\vece{\mathbf{e}}
\def\vecz{\mathbf{z}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{CSC 2414 Problem Set 3\\{\large Due: December 22, 2011}}
\author{}
\date{}
\begin{document}
\maketitle
%\input{pset-preamble.tex}
%\lecture{1}{Vinod Vaikuntanathan}{September 13, 2011}{October 3, 2011}
\subsection*{Notes}
\begin{itemize}
\item This problem set is worth $100$ points.
\item Collaboration is allowed, {\em but you must write up the solutions by yourself without consulting to notes from the discussions}. You must also reference your sources.
\item Grading is based on correctness as well as the clarity of the solutions. When writing proofs, it is generally a good idea to first explain the intuition behind your solution in words (wherever appropriate), before jumping in to the formalisms.
\item There is no deadline for the extra credit problem. You can turn in a solution any time until the last class.
\item {\bf Notation:} If $X$ is a probability distribution, then $x \in_R X$ means that $x$ is drawn randomly according to the probability distribution $X$. If $S$ is a finite set, then $x \in_R S$ means that $x$ is drawn from the uniform probability distribution over $S$.
\end{itemize}
%\subsection*{Problem $1$: SIS and LWE (25 points)}
%
%Let us first define a generalized version of the Short Integer Solutions (SIS) and the Learning with Error (LWE) problems.
%Let $\chi$ be a probability distribution on $\Z_q = \{-(q-1)/2,\ldots,(q-1)/2 \}$.
%%(For example, think of $\chi$ as being the uniform distribution on some interval $\{-B, \ldots, B\}$ for a positive integer $B \ll (q-1)/2$).
%
%\begin{description}
%\item $\mathsf{gSIS}_{n,m,q,\chi}$: Given a uniformly random matrix $\matA \in \Z_q^{n\times m}$ and a vector
%$\vecy = \matA \vece \in \Z_q^n$ where each component of $\vece = (e_1,\ldots,e_m) \in \Z_q^m$ is chosen independently
%from the distribution $\chi$, find $\vece$.
%
%\item $\mathsf{LWE}_{n,m,q,\chi}$: Given a uniformly random matrix $\matB \in \Z_q^{n\times m}$ and a vector
%$\vecz = \matB^T \vecs + \vece \in \Z_q^m$ where $\vecs \gets_R \Z_q^n$ is uniformly random and
%each component of $\vece = (e_1,\ldots,e_m) \in \Z_q^m$ is chosen independently from the distribution $\chi$,
%find $\vecs$.
%
%\end{description}
%
%\medskip\noindent
%Show that $\mathsf{LWE}_{n,m,q,\chi}$ and $\mathsf{gSIS}_{m-n,m,q,\chi}$ are equivalent in difficulty. That is,
%if one of these is solvable in polynomial time, so is the other.
%
%\medskip\noindent
%Formally, you need to exhibit two reductions -- one that solves $\mathsf{gSIS}$ given an algorithm that solves $\mathsf{LWE}$, and
\newcommand{\inner}[2]{\langle {#1}, {#2} \rangle}
% Usage, to denote the inner product of a and b, write \inner{a}{b}
\def\sslwe{\mathsf{ssLWE}}
\def\lwe{\mathsf{LWE}}
% Macros for vectors
\def\veca{\mathbf{a}}
\def\vecs{\mathbf{s}}
\def\vecc{\mathbf{c}}
\subsection*{Problem $1$: LWE with a Short Secret (65 points)}
Define the ``short secret LWE'' problem $\sslwe$ as follows. Let $n$ and $q \geq 2$ be natural numbers
and $\chi$ be a probability distribution over $\Z_q = \{0,\ldots, q-1\}$, and let $\chi^n$ denote a
probability distribution on $\Z_q^n$ where each component is drawn independently from $\chi$.
\medskip\noindent
$\sslwe_{n,q,\chi}$: Given access to an oracle that produces samples of the form
$(\veca_i, \inner{\veca_i}{\vecs} + e_i)$ where $\veca_i \in_R \Z_q^n$, $x_i \in_R \chi$
and $\vecs \in_R \chi^n$, find $\vecs$.
Note that the only difference between $\lwe$ and $\sslwe$ is in the distribution of the secret $\vecs$ --
in $\lwe$, the secret is drawn from the uniform distribution over $\Z_q^n$ whereas in $\sslwe$, it is
drawn from $\chi^n$.
Prove that $\sslwe$ and $\lwe$ are equivalent. Namely,
\begin{itemize}
\item (5 points) Show that if there is an algorithm that solves $\lwe$ with $m$ samples, then
there is an algorithm that solves $\sslwe$ with $m$ samples as well.
\item (60 points) Show that if there is an algorithm that solves $\sslwe$, then
there is an algorithm that solves $\lwe$. Your $\lwe$ algorithm can use up more samples than
the $\sslwe$ algorithm -- try to make do with $m+O(n)$ samples.
\medskip\noindent
{\em [Hint: Observe that given (say) $n$ $\sslwe$ samples written compactly as $(\matA, \matA^T \vecs + \vece)$,
one can write down a linear relation between the LWE secret $\vecs$ and the error $\vece$.]}
\end{itemize}
\subsection*{Problem $2$: Modulus Reduction Lemma (35 points)}
The modulus reduction procedure works as follows:
\begin{enumerate}
\item {\bf Input:} A ciphertext of the form $\vecc := (\veca, b = \inner{\veca}{\vecs} + 2e + \mu) \in \Z_q^n \times \Z_q$
where $\veca \in_R \Z_q^n$, $\vecs \in_R \chi^n$, $e \in_R \chi$, and the message $\mu \in \{0,1\}$. A natural number $p$.
\item {\bf Procedure:}
\begin{itemize}
\item \textsf{Scaling:} Compute $\vecc_f = (\frac{p}{q} \cdot \veca, \frac{p}{q} \cdot b) \in \Q^n \times \Q$.
\item \textsf{Special Rounding:} Round $\vecc_f$ to the nearest integer vector $\vecc' \in \Z^n\times \Z$
such that $\vecc' = \vecc \pmod{2}$. Namely, apply the special rounding operation to each coefficient of $\vecc_f$
separately.
\end{itemize}
\item {\bf Output:} The output is the vector $\vecc' = (\veca', b')$, considered as an element of $\Z_p^n \times \Z_p$.
\end{enumerate}
Your goal is to prove that $\vecc'$ is an encryption of $\mu$ modulo $p$. Namely,
\begin{itemize}
\item Prove that $\bigg|b' - \inner{\veca'}{\vecs}\bigg| \leq \frac{p}{q}\cdot \bigg|b - \inner{\veca}{\vecs}\bigg| + \sum_{i=1}^n |s_i| = \frac{p}{q}\cdot \bigg|b - \inner{\veca}{\vecs}\bigg| + \ell_1(\vecs)$, where $\ell_1(\vecs)$ denotes the $\ell_1$ norm of the vector $\vecs$.
\item Assume that $p