\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
\newif\ifpdf
\ifx\pdfoutput\undefined \else
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\else
\pdftrue
\fi
\fi
\fi
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\def\class{0}
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\GF}{\mathsf{GF}}
\newcommand{\maxpr}{\text{\rm max-pr}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\PH}{\cclass{PH}}
\newcommand{\coNP}{\cclass{coNP}}
\newcommand{\AvgP}{\cclass{AvgP}}
\newcommand{\DTIME}{\cclass{DTIME}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\BQP}{\cclass{BQP}}
\newcommand{\NTIME}{\cclass{NTIME}}
\newcommand{\SIZE}{\cclass{SIZE}}
\newcommand{\Ppoly}{\cclass{P_{/poly}}}
\newcommand{\SPACE}{\cclass{SPACE}}
\newcommand{\PSPACE}{\cclass{PSPACE}}
\newcommand{\BPL}{\cclass{BPL}}
\newenvironment{summary}{\begin{quote}\textbf{Summary.}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}[theorem]
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\sstart}{\triangleright}
\newcommand{\send}{\triangleleft}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{3SAT}}}
\newcommand{\IS}{\mathsf{INDSET}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\inp}{\mathsf{in}}
\newcommand{\outp}{\mathsf{out}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Supp}{\mathsf{Supp}}
\newcommand{\dist}{\Delta}
\newcommand{\indist}{\approx}
\newcommand{\PRG}{\mathsf{G}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\Com}{\mathsf{Com}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\eqdef}{\stackrel{\text{\tiny def}}{=}}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
\newcommand{\qstart}{q_{\text{\tiny start}}}
\newcommand{\qacc}{q_{\text{\tiny acc}}}
\newcommand{\qrej}{q_{\text{\tiny rej}}}
\newcommand{\csp}{\mathsf{CSP}}
\newcommand{\ared}{\text{\tt alph-red}}
\newcommand{\qred}{\text{\tt q-red}}
\newcommand{\dred}{\text{\tt deg-red}}
\newcommand{\amp}{\text{\tt gap-amp}}
\newcommand{\LC}{\mathcal{LC}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\pmo}{\{\pm 1\}}
\newcommand{\set}[1]{\{ #1 \}}
\newcommand{\jacobi}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\bE}{\mathbf{E}}
\newcommand{\Add}{\mathsf{Add}}
\newcommand{\Mult}{\mathsf{Mult}}
\newcommand{\Clean}{\mathsf{Clean}}
\newcommand{\Rerand}{\mathsf{ReRand}}
\newcommand{\cE}{\mathcal{E}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 433 --- Cryptography --- Homework 11 --- last one! \texttt{:)}.}
\author{Boaz Barak}
\date{Total of 180 points. Due April 30th, 2010.}
\begin{document}
\maketitle
Since it seems several people had issues with zero knowledge (which is indeed a tricky concept), I decided to add
another question on zero knowledge. Also, lectures 24 till 28 in Trevisan's lecture notes
(\url{http://www.cs.berkeley.edu/~luca/cs276/}) are a good source for zero knowledge.
\begin{exercise}[30 points] A somewhat counterintuitive aspect of zero knowledge is that the simulator's job is just to sample
a random variable and so it can generate randomness for the verifier in the process, which may seem ``unfair''. The
following question illustrates why this is the right notion, by showing that the zero knowledge property implies that
anything the verifier can learn about the secret after the interaction, he could have learned on his own. (This can be
viewed as the mathematical formalization of Chazelle's description of zero knowledge..)
Recall the zero knowledge protocol for quadratic residuosity we saw in class (Protocol QR in notes for lecture 17).
\begin{enumerate}
\item Suppose that there is a cheating verifier $V^*$ that satisfies the following property: if we choose $N=PQ$ as
random Blum prime of $2n$ bits, choose $W \getsr \Z^*_N$, and $X=W^2 \pmod{N}$, then after interacting with the
prover for protocol QR on public input $X,N$ and with prover's private input being $W$, $V^*$ outputs the least
significant bit of $W$ with probability at least $0.99$.
Prove that in this case there is a polynomial-time algorithm $A$ that if $X,N,W$ chosen as above and $A$ is
given $X,N$ as input, then $A$ outputs the least significant bit of $W$ with probability at least $0.98$.
\item Prove that the above holds not just for that particular protocol, but for any $\e$-computational zero
knowledge protocol (as per the definition given in class and also in homework 10).
\end{enumerate}
\end{exercise}
\begin{exercise}[30 points] Prove that if there exists a fully homomorphic CPA-secure private key encryption scheme, then there exists a
fully homomorphic CPA-secure public key encryption scheme. (The definition we use is with the $NAND$ algorithm, as in
the lecture notes and homework 10.)
\end{exercise}
\begin{exercise}[30 points] In this exercise you'll prove the variant of the ``leftover hash lemma'' that we needed for showing
that rerandomization works. This lemma is useful in many other settings, and so it's worthwhile to know in general.
\begin{enumerate}
\item Let $R\in\N$ and let $\pi:\Z_R\to [0,1]$ be a probability distribution over $\Z_R$, that is $\sum_i
\pi(i)=1$. Let $cp(\pi)$ denote the collision probability of $\pi$. That is, $cp(\pi) = \Pr_{a,b \sim \pi}[a=b]
= \sum_i \pi(i)^2$ (can you see why?). Prove that if $cp(\pi) \leq 1/R + \e$ then the statistical distance of
$\pi$ from the uniform distribution is at most $10\sqrt{\e R}$. See footnote for hint.\footnote{\textbf{Hint:}
{\tiny Write this statistical distance as $\sum_i |\pi(i)-1/R|$ and use the Cauchy-Schwarz inequality that
$\sum_i |a_i||b_i| \leq \sqrt{\sum_i a_i^2 \sum_j b_j^2}$ .}}
\item Let $\overline{b} = b_1,\ldots,b_{10n}$ and $\overline{a} = a_1,\ldots,a_{10n}$ be two $10n$-bit vectors that are
not the same (there is an $i$ such that $a_i \neq b_i$). Prove that if $R$ is prime and $Q_1,\ldots,Q_{10n}$ are chosen at random
in $\Z_R$ then $\Pr[ \overline{Q} \cdot \overline{a} = \overline{Q} \cdot \overline{b} ] = 1/R$, where
$\overline{Q}$ denotes the vector $Q_1,\ldots,Q_{10n}$ and $\overline{Q}\cdot \overline{a} = \sum_{i=1}^{10n}
a_iQ_i \pmod{R}$. See footnote for hint\footnote{\textbf{Hint:} {\tiny this is the same calculation we have done in the past when discussing
pairwise independent hash functions.}}
\item For a vector $\overline{Q}$ as above, let $\pi_{\overline{Q}}$ denote the distribution over $\Z_R$ obtained by
choosing a random set $S\subseteq [10n]$ (by setting each $i$ to be inside $S$ with probability $1/2$
independently) and outputting $\sum_{i\in S} Q_i \pmod{R}$. Prove that the expectation of $cp(\pi_S)-1/R$ over the
choice of a random $Q$, is at most $2^{-5n}$.
\item Show the lemma stated in class: if $\overline{Q}$ is chosen at random as above, then with probability at
least $1-2^{-n}$, the statistical distance of $\pi_{\overline{Q}}$ and the uniform distribution over $\Z_R$ is at most
$2^{-n}$. This completes the proof of the rerandomization step we showed in class, since now the distribution
$\sum_{i\in S} Q_iP \pmod{N}$ for a random subset $S$ will be statistically close to the distribution $QP$ where
$Q$ is chosen uniformly over $\Z_R$.
\end{enumerate}
\end{exercise}
\begin{exercise}[30 points] \label{ex:deg1} In this exercise we use a slightly different definition of $\cE^{\bE}(b)$. We define
$\cE^{\bE}(b) = \{ X \in \Z_N : X = PQ + 2E+b \pmod{N} \text{ and } |2E+b| \leq \bE \}$. Note that this is the same as
we defined in class up to a factor of $3$ in the noise, and so none of the discussion in class is affected by this.
Define $\Add(Y_1,\ldots,Y_k) = \sum_i Y_i \pmod{N}$ and $\Mult(Y_1,\ldots,Y_k) = \prod_{i=1}^k Y_i \pmod{N}$. Prove
that if $Y_i \in \cE^{\bE_i}(c_i)$ then $\Mult(Y_1,ldots,Y_k) \in \cE^{\bE_1\cdots\bE_k}(c_1c_2\cdots c_k)$ and
$\Add(Y_1,\ldots,Y_k) \in \cE^{\sum_i \bE_i}(c_1\oplus \cdots \oplus c_k)$.
Let $C$ be a Boolean circuit, composed of multiplication and addition gates modulo $2$, that computes a function
mapping $\GF(2)^m$ to $\GF(2)$. Recall that we can think of $C$ as a labeled directed acyclic graph, with $m$ sources
corresponding to the inputs and also the constants $0$ and $1$, one sink corresponding to the output, and the other
vertices correspond to the gates, and are labeled with either $\oplus$ or $\times$. We define the \emph{degree} of an
input or constant vertex to be $1$, and define the degree of other vertices inductively: let $v$ be a vertex and
suppose that we already defined the degrees $d_1,\ldots,d_k$ of the vertices that have a edges to $v$. If $v$ is
labeled with $\times$ then we define the degree of $v$ to be $d_1+\cdots+d_k$, and if $v$ is labeled with $\oplus$ then
we define the degree of $v$ to be $\max\{ v_1,\ldots, v_k \}+1$. The degree of the circuit is the maximum degree of all
its vertices.
Let $C$ be a circuit of degree at most $d$ and size at most $S$. Suppose that we are given $m$ ciphertexts
$X_1,\ldots,X_m$ where $X_i \in \cE^{\bE}(b_i)$, and we run the circuit $C$ on these ciphertexts, by changing each
$\oplus$ gate to a call of $\Add$ and each $\times$ gates to a call of $\Mult$. Prove that we get as output $X$ in
$\cE^{\bE'}(b)$ where $\bE' \leq (\bE+S)^{d}$ and $b=C(b_1,\ldots,b_m)$. See footnote for hint\footnote{\textbf{Hint:}
{\tiny Sort the circuit topologically, and prove by induction.} }
\end{exercise}
\begin{exercise}[30 points] \label{ex:deg2} Let $f:\GF(2)^{\ell}\To\GF(2)$ be any function. Prove that $f$ has a circuit of degree at most
$2\ell$ and size at most $2^{3\ell}$. See footnote for hint.\footnote{\textbf{Hint:} {\tiny You can express $f$ as the
polynomial $\sum_{y\in\GF(2)^{\ell}}f(y)\prod_{i=1}^{\ell}(1+ x_i + y_i) \pmod{2}$.}}
\end{exercise}
\begin{exercise}[30 points] \label{ex:deg3} Let $SUM_i:\bits^m\To\bits$ be such that $SUM_i(a_1,\ldots,a_m)$ denote the $i^{th}$ bit of the sum $\sum_j
a_j$. That is, one can write $\sum_j a_j = \sum_i 2^i SUM_i(a_1,\ldots,a_m)$. Give a circuit of $\poly(m,2^i)$ size and
degree at most $100(\log m + 2^i)$ to compute $SUM_i$. If you want, you can follow the approach below (or you can use
any other design).
\begin{enumerate}
\item Define \[ S_k(a_1,\ldots,a_m) = \sum_{\substack{S \subset [m] \\ |S|=k}} \prod_{j\in S} a_j \pmod{2}
\] Prove that $SUM_i(a_1,\ldots,a_m)= S_{2^i}(a_1,\ldots,a_m)$. See footnote for hint.\footnote{\textbf{Hint:} {\tiny use induction on $m$}}
\item Prove that $S_k(a_1,\ldots,a_m) = \sum_{j=0}^k S_j(a_1,\ldots,a_{m/2}) \cdot S_{k-j}(a_{m/2+1},\ldots,a_m)$.
\item Give a circuit of $\poly(m,2^i)$ size and degree at most $100(\log m + 2^{i})$ to compute the function
$SUM_i$. (If it simplifies matters, you can assume $m$ is a power of $2$). See footnote for
hint.\footnote{\textbf{Hint:} use dynamic programming
and the recursion above.}
\end{enumerate}
\end{exercise}
By combining Exercises~\ref{ex:deg1}, \ref{ex:deg2} and~\ref{ex:deg3}, we can obtain the $\Clean$ procedure. The main
goal there was to add up $m$ numbers that are of $O(\log k)$ size, at most $k$ of them are non zero. The idea is to
follow the trivial gradeschool algorithm for addition. Recall that it starts by summing up the least significant digit
of all the numbers, where the functions $SUM_1,\ldots,SUM_{log k}$ allow us to compute the carry. We then sum up the
second least significant digit of all the numbers and add the first bit of carry from the first sum, and continue in
this way. One can see that the $i^{th}$ digit of the sum can always be computed with degree roughly $2^i$.
\end{document}