From b826034077c581658a6308b6ebceacb292a5ea9b Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 4 May 2015 11:25:09 -0400
Subject: [ps6] solutions

---
 ps6/main.tex | 338 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 338 insertions(+)
 create mode 100644 ps6/main.tex

(limited to 'ps6/main.tex')

diff --git a/ps6/main.tex b/ps6/main.tex
new file mode 100644
index 0000000..87c179b
--- /dev/null
+++ b/ps6/main.tex
@@ -0,0 +1,338 @@
+\documentclass[10pt]{article}
+\usepackage{fullpage}
+\usepackage[utf8x]{inputenc}
+\usepackage{amsmath,amsfonts,amsthm}
+\usepackage[english]{babel}
+\usepackage[capitalize, noabbrev]{cleveref}
+\usepackage{algorithm}
+\usepackage{algpseudocode}
+
+\newenvironment{enumerate*}%
+  {\vspace{-2ex} \begin{enumerate} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{enumerate}}
+ 
+\newenvironment{itemize*}%
+  {\vspace{-2ex} \begin{itemize} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{itemize}}
+ 
+\newenvironment{description*}%
+  {\vspace{-2ex} \begin{description} %
+     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
+  {\end{description}}
+
+
+\DeclareMathOperator{\E}{\mathbb{E}}
+\DeclareMathOperator{\Enc}{\mathrm{Enc}}
+\DeclareMathOperator{\Dec}{\mathrm{Dec}}
+\DeclareMathOperator{\Ext}{\mathrm{Ext}}
+\let\P\relax
+\DeclareMathOperator{\P}{\mathbb{P}}
+\DeclareMathOperator*{\argmin}{\arg\min}
+\newcommand{\ex}[1]{\E\left[#1\right]}
+\newcommand{\prob}[1]{\P\left[#1\right]}
+\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
+\newcommand{\R}{\mathbf{R}}
+\newcommand{\poly}{\text{poly}}
+\newcommand{\N}{\mathbf{N}}
+\newcommand{\C}{\mathcal{C}}
+\newcommand{\eps}{\varepsilon}
+\newcommand{\cl}[1]{\text{\textbf{#1}}}
+\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
+\newcommand{\llbracket}{[\![}
+
+
+\newtheorem{theorem}{Theorem}
+\newtheorem{lemma}{Lemma}
+\algrenewcommand\algorithmicensure{\textbf{Output:}}
+\algrenewcommand\algorithmicrequire{\textbf{Input:}}
+
+\author{Thibaut Horel}
+\title{CS 225 Problem Set 6 -- Solutions}
+
+\begin{document}
+\maketitle
+
+\section*{Problem 7.1}
+
+Let us consider the function $f:\{0,1\}^l\to\{0,1\}$ defined by:
+\begin{displaymath}
+    f(x) = \begin{cases}
+        1&\text{if }\exists\, y\in\{0,1\}^{d^{-1}(l-1)-l}\text{ st } x\cdot y\in \text{Im}(G_{d^{-1}(l-1)})\\
+        0&\text{otherwise}
+    \end{cases}
+\end{displaymath}
+where $\text{Im}$ denotes the image of a function (here the generator). In
+other words, $f(x)$ is 1 iff $x$ is the first $l$ bits of one of the outputs
+of $G_{d^{-1}(l-1)}$. Note that the output is guaranteed to have at least $l-1
++1 = l$ by definition of a pseudorandom generator.
+
+$f(x)$ can be computed by iterating over all possible $2^{l-1}$ inputs of
+$G_{d^{-1}(l-1)}$ and checking whether or not the first $l$ bits of the output
+are equal to $x$, hence $f\in \cl{E}$.
+
+Let us assume that there exists a probabilistic non-uniform algorithm $A$ such
+that $\prob{A(x) = f(x)}\geq \frac{2}{3}$ for all $x\in\{0,1\}^l$. Using $A$,
+I define the following test of randomness $T$:
+\begin{displaymath}
+    \forall z\in \{0,1\}^{d^{-1}(l-1)},\; T(z) = A(z_l)
+\end{displaymath}
+where $z_l$ denotes the first $l$ bits of $z$. Then we have:
+\begin{displaymath}
+    \prob{T(G(U_{l-1})) = 1} = \prob{A(G(U_{l-1})_l) = 1}
+    = \prob{A(G(U_{l-1})_l) = f(G(U_{l-1})_l)} = p_A
+\end{displaymath}
+where $U_{l-1}$ is a uniform variable over $\{0,1\}^{l-1}$ and $p_A$ is the
+probability that $A$ is correct (\emph{i.e} $p_A \geq \frac{2}{3})$. Indeed, $f$
+is constant equal to $1$ on the first $l$ bits of the image of $G$. We also
+have:
+\begin{displaymath}
+    \prob{T(U_d) = 1} = \prob{U_d\in \text{Im}(G)}p_A + (1-p_A)\prob{U_d\notin
+    \text{Im}(G)}
+\end{displaymath}
+where $U_d$ is uniform over $\{0,1\}^{d^{-1}(l-1)}$.  Hence:
+\begin{displaymath}
+    |\prob{T(G(U_{l-1})) = 1} - \prob{T(U_d) = 1}| = (2p_A - 1)(1-\prob{U_d\in
+    \text{Im}(G)})
+\end{displaymath}
+but $\text{Im}(G)$ is of size at most $2^{l-1}$ (when $G$ is injective) hence:
+\begin{displaymath}
+    |\prob{T(G(U_{l-1})) = 1} - \prob{T(U_d) = 1}|
+    \geq \frac{1}{3}\left(1- \frac{2^{l-1}}{2^{d^{-1}(l-1)}}\right)\geq
+    \frac{1}{6}
+\end{displaymath}
+Hence $T$ has an advantage larger than $\frac{1}{6}$ and by definition of $G$
+this implies that $T$, hence $A$ has running time at least $d^{-1}(l-1)$, which
+concludes the proof.
+
+\section*{Problem 7.4}
+
+\paragraph{1.} Given constant depth circuit $C$ of size $n$, pick $m$ such that
+$m\geq n$ and $m\geq \frac{1}{\eps}$, e.g, $m = n + \frac{1}{\eps}$. And
+consider the pseudorandom generator $G_m$ given by Theorem 7.29. By definition:
+\begin{displaymath}
+    |\prob{C(G(U_1)) = 1} - \prob{C(U_2) = 1}|\leq \frac{1}{m}\leq \eps
+\end{displaymath}
+where $U_1$ is uniformly distributed over $\{0,1\}^{\log^{O(k)}m}$ and $U_2$ is
+uniformly distributed over $\{0,1\}^m$. Note that the input size of $C$ is at
+most $n\leq m$, so we might have to drop some bits from $U_2$ or $G((U_1)$ for
+the above formula to make sense (this is not a problem since the truncation of
+a uniform variable is still uniform).
+
+Now, observe that $\prob{C(U_2) = 1}$ is exactly the quantity we wish to
+estimate within an additive error of $\eps$. $\prob{C(G(U_1) = 1}$ can be computed
+by averaging over all the possible $2^{\log^{O(k)}m} = 2^{\text{poly}(\log
+n,\log\frac{1}{\eps})}$ values of $U_1$. Since $G_m$ can be computed in time
+$\text{poly}(m) = \poly(n,\frac{1}{\eps})$, the running time is still $2^{\text{poly}(\log
+n,\log\frac{1}{\eps})}$.
+
+By the inequality above, the computed value of $\prob{C(G(U_1)) = 1}$ is within
+an additive $\eps$ error of $\prob{C(U_2) = 1}$.
+
+\paragraph{2.} Let us consider the circuit $C$ of depth $2$ which computes
+$\phi$. I denote by $l$ the number of clauses in $C$ and by $v$ the number of
+literals. As suggested, I assume that each clause contains exactly $r$
+literals. Note that we have $rl = v\leq n$.
+
+It is easy to see that $C$ can be “extended” into a circuit $C'$
+which takes as input $i\in[l]$ and assignment $\alpha\in\{0,1\}^{v-r}$ (which
+should be interpreted as an assignment of all the variables which do not appear
+in clause $i$) and output $C'(i,\alpha)$ which is 0 or 1 depending on whether
+or not $\alpha$ violates all the clauses before the $i$th clause (we do not
+need to know the assignment of variables in clause $i$ to verify this). $C'$
+still has constant depth (I was able to draw a circuit of depth 4 for this,
+maybe 3 is possible?).
+
+Now, using the notations of Algorithm 2.35, a uniform sample $(i,\alpha)$ in
+$[n]\times \{0,1\}^{v-r}$ can be interpreted as a random sample in $B$ (since
+we do not need to specify the assignment of the variables in clause $i$) and
+the output of $C'$ tells whether or not the sample is in $A'$. By the analysis
+of Algorithm 2.35, for uniform $U_2$ in $[n]\times \{0,1\}^{v-r}$ (since all
+the clauses have the same number of literals, we have the right probability of
+picking each clause):
+\begin{displaymath}
+    \prob{C'(U_2) = 1} = |A|/|B|
+\end{displaymath}
+
+Using the same averaging argument as in \textbf{1.} by averaging over all
+inputs of an appropriate pseudorandom generator, it is possible to approximate
+$\prob{C'(U_2) = 1} = \frac{|A|}{|B|}$ within an \emph{additive}
+$\frac{\eps}{l}$ error in time $2^{\text{poly}(\log n,\log\frac{l}{\eps})}= 
+2^{\text{poly}(\log n,\log\frac{1}{\eps})}$ since $l\leq n$.
+
+Now our algorithm simply outputs this average times $B$. The same analysis as
+the one Algorithm 2.35 shows that this quantity is within
+a \emph{multiplicative} $1+\eps$ ratio of $|A|$ (since $|B|/l\leq |A|$). Since
+$|A|$ is the number of satisfying assignments, this concludes the proof.
+
+\section*{Problem 7.6}
+
+\paragraph{1.} Assume that we are given received word $r$ which differs from
+$\Enc(x)$ on a fraction at most $\frac{1}{3q}$ of the symbols, and apply the
+decoder $\Dec$ of the $q$-query smooth code for some query $i$. By union bound,
+the probability $p$ that the $q$ queries made by $\Dec$ are all at positions
+where $r$ coincides with $x$ is:
+\begin{displaymath}
+    p\geq 1 - q\cdot\frac{1}{3q} = \frac{2}{3}
+\end{displaymath}
+Hence, with probability at least $\frac{2}{3}$, $\Dec$ will only query correct
+symbols of $r$ and will behave exactly the same as if it had been given
+$\Enc(x)$, it will thus return $x_i$ in this case. In others words, for query
+$i$, $\Dec$ returns $x_i$ with probability at least $\frac{2}{3}$ given
+received word $r$ at distance at most $\frac{1}{3q}$ from $\Enc(x)$. This is
+the definition of a local $\frac{1}{3q}$-decoder.
+
+\paragraph{2.} The scheme is very simple: the server algorithms are all equal
+and given query $i\in[\hat{n}]$ and database $D$ return $\Enc(D)_i$. Given
+query $i\in[n]$, the user algorithm run the decoder $\Dec$ of the $q$-query
+smooth code on input $i$. The $q$ oracle queries made by $\Dec$ to $\Enc(D)$
+are sent to the $q$ different servers. In other words, we simulate the oracle
+access to $\Enc(D)$ required by $\Dec$ by having the servers answer the oracle
+queries.  Since $\Dec$ makes $q$ queries, we need $q$ servers.
+
+By definition of a smooth code, the queries made to the server are uniformly
+distributed in $[\hat{n}]$ and hence have the same distribution regardless of
+the index $i$ being queried, this satisfies the privacy requirement of our PIR
+scheme.
+
+Finally, the communication complexity is $\log \hat{n} + \log|\Sigma|$ for each
+query (we ask an index $j\in[\hat{n}]$ and receive a symbol in $\Sigma$). The
+overall number of bits exchanged is $q(\log\hat{n} + \log|\Sigma|)$.
+
+\paragraph{3.} I follow an approach very similar to Algorithm 7.43 except that
+it is simpler since there are no corruptions.
+
+I interpret the database $D$ as a function $f:\{0,1\}^l \to \{0,1\}$,
+\emph{i.e}, we have $n = 2^l$. A query $i$ to the database can be interpreted
+as obtaining the value $f(x)$ for some input $x\in\{0,1\}^l$. Using this
+interpretation the $\text{polylog}(n)$ requirements of the scheme are
+equivalent to $\text{poly}(l)$ requirements.
+
+I choose a finite field $F$ of size $2l$, and consider the multilinear
+extension $\hat{f}$ of $f$ over $F$. In particular, $\hat{f}:F^{l}\to F$ is
+a $l$-variate polynomial of total degree at most $l$.
+
+I define the PIR scheme as follows:
+\begin{itemize}
+    \item $l+1$ servers with the same algorithm: given query $z\in F^{l}$,
+        the server returns $\hat{f}(z)$.
+    \item the user algorithm:
+        \begin{itemize}
+            \item fix $l+1$ elements in $F$ distinct from $0$ (these are the
+                same regardless of the query). Denote these elements
+                $y_0,\dots, y_l$.
+            \item Given input $x\in\{0,1\}^l$, pick a uniformly random
+                direction $y\in F^{l}$ and query $z_i = x+ y\cdot y_i$ for
+                $0\leq i\leq l$ to the $l+1$ servers (one query per server).
+            \item use the $l+1$ answers from the servers to find the unique
+                univariate polynomial $p$ of degree $l$ equal to $\hat{f}|_L$
+                where $L$ denotes the affine line passing through $x$ and
+                direction $y$. Note that this is feasible since the answers
+                given by the server are the values of $\hat{f}$ at $l+1$
+                distinct points of $L$, and $\hat{f}|_L$ is a univariate
+                polynomial (over $F$) of degree at most $l$.
+            \item output $p(0) = \hat{f}|_L(0) = \hat{f}(x) = f(x)$
+        \end{itemize}
+\end{itemize}
+
+The correctness of this PIR scheme was established while defining it (since
+there are no corruptions, this follows directly from univariate polynomial
+interpolation, there is no need to account for the corruptions as in the
+lecture notes).
+
+The privacy requirement follows from the fact that for fixed $x$ and $y_i$,
+$z_i = x+y\cdot y_i$ is uniform over $F^{l}$ for $y$ uniform over $F^{l}$.
+Hence query $i$ is uniformly distributed (in particular, the distribution does
+not depend on $x$).
+
+Finally, the number of server is $l+1 = \text{poly}(l)$. The number of bits
+exchanged is $l\log |F| + \log |F| = O(l\log l)$ per server, for a total of
+$O(l^2\log l) = \text{poly}(l)$ bits exchanged overall.
+
+Note that I had to choose a field of size $|F| = 2l$ because I need at least
+$l+1$ distinct elements different from $0$ in $F$ ($|F| = l+2$ would have been
+sufficient).
+
+\section*{Problem 7.13}
+
+\textbf{1.} Assume by contradiction that there exists a constant $c$ and
+algorithm $A$ running in time $(l+\log\hat{L})^c$ such that:
+\begin{displaymath}
+    \P_{X,Y}\big[A(f(X), Y) = \Enc(X)_Y\big] > \frac{1}{2}
+    + \frac{1}{(l+\log\hat{L})^c}
+\end{displaymath}
+Then by Markov's inequality, for all $d$:
+\begin{displaymath}
+    \P_{X}\Big[\P_Y\big[A(f(X), Y) = \Enc(X)_Y\big] > \frac{1}{2}
+    + \frac{1}{l^d}\Big]\geq \frac{1}{(l+\log\hat{L})^c} - \frac{1}{l^d}
+\end{displaymath}
+Since $\Enc$ can be $(1/2-1/l^d)$ local list decoded, we construct the
+following algorithm $A'$ to “invert” $f'$. Given input $(f(x), y)$:
+\begin{itemize}
+    \item do local list decoding with oracle $g_x(y') = A((f(x), y')$ and
+        obtain a list of $s$ possible decoded messages $x_1,\dots, x_s$. Here
+        I combined $\Dec_1$ and $\Dec_2$ in one step and decoded all symbols.
+        However, the local-list decoding property is still important for the
+        running time: we don't need to query the oracle for all $y'$ to do the
+        decoding (this is important when $\hat{L}$ is exponential in $l$).
+    \item for each message $x_1,\dots, x_s$ check whether or not $f(x_i)
+        = f(x)$
+    \item if one $x_i$ was found in the previous step, output it $(x_i, y)$
+        (pick one at arbitrarily if there are several of them), if not pick $x_i$ at
+        random and output $(x_i, y)$.
+\end{itemize}
+
+By the inequality above, the probability over $X$ that the oracle $g_X$ agrees
+with $\Enc(X)$ on at least $\frac{1}{2}+\frac{1}{l^d}$ fraction of the symbols
+is at least $\frac{1}{(l+\log\hat{L})^c} - \frac{1}{l^d}$. In those cases, local
+list decoding is successful, that is, with probability $\frac{2}{3}$ the list
+of messages contains $X$ and in this case $A'$ output $(X', Y)$ such that
+$f(X') = f(X)$.
+
+Since $f$, $\Dec_1$ and $\Dec_2$ can be computed in time $\poly(l)$, the
+running time of $A'$ is $\poly(l)(l+\log\hat{L})^c$.
+
+Furthermore we have just proven that the probability of “success of inversion”
+of $A'$ over random input $(f(X),Y)$ is at least:
+\begin{displaymath}
+    \frac{2}{3}\cdot\left(\frac{1}{(l+\log\hat{L})^c} - \frac{1}{l^d}\right)
+\end{displaymath}
+By chosing $d$ appropriately, this can be made larger than the inverse of the
+running time of $A'$, yielding a contradiction to the \emph{one-wayness}
+(unilaterality?  unidirectionality?) of $f'$.
+
+\paragraph{2.} Using Proposition 7.16, it suffices to show that $G(X)$ is
+previous-bit unpredictable in the following sense: for all non uniform
+algorithm $A$ running in time $m^c$ and all $i\in[m]$:
+\begin{displaymath}
+    \prob{A(G(X)_{:i}) = G(X)_i}\leq\frac{1}{2}+\frac{1}{m^{c+1}}
+\end{displaymath}
+where $G(X)_i$ represents the $i$th last bit of $G(X)$ and $G(X)_{:i}$
+represents the last bits of $G(X)$ up to (but excluding) the $i$th last one.
+
+Assume by contradiction that there exists $c$ and algorithm $A$ running in time
+$m^c$ such that:
+\begin{displaymath}
+    \P_X[A(G(X)_{:i}) = G(X)_i]>\frac{1}{2}+\frac{1}{m^{c+1}}
+\end{displaymath}
+Then I construct the following algorithm $A'$ contradicting the hardcoreness of
+predicate $b$. Given input $f(X)$:
+\begin{itemize}
+    \item compute $b(f(X))$, $b(f^2(X))$, $\dots$, $b(f^{(i-1)}(X))$
+    \item apply $A$ on the values computed at the previous step and output the
+        result
+\end{itemize}
+The running time of $A'$ is at most $m\poly(m) + m^c$ where the $\poly(m)$ factor
+accounts for the running time of $f$ composed with $b$.
+
+Since $f$ is a permutation, $f(X)$ has the same distribution as
+$f^{(m-i+1)}(X)$ (i.e it is uniform on $\{0,1\}^l$), hence:
+\begin{displaymath}
+    \P_X[A'(f(X)) = b(X)] =
+    \P_X[A'(f^{(m-i+1)}(X)) = b(f^{(m-i)}(X)] =
+    \P_X[A(G(X)_{:i}) = G(X)_i]
+\end{displaymath} 
+by our assumption this probability is at least $\frac{1}{2}+\frac{1}{m^{c+1}}$.
+Hence, the algorithm $A'$ contradicts the hardcoreness of the predicate $b$.
+\end{document}
-- 
cgit v1.2.3-70-g09d2

