\documentclass[11pt]{article}

\usepackage[margin=0.75in]{geometry}
\input{latexdefs}

\usepackage{chngcntr}
%\counterwithin*{equation}{section}
\newtheorem*{defn*}{Definition}

\begin{document}

\newlength{\boxwidth}
\setlength{\boxwidth}{\textwidth}
\addtolength{\boxwidth}{-2cm}
\noindent\framebox[\textwidth]{
\begin{minipage}[t]{\boxwidth}
  {\bf CS 355: Topics in Cryptography \hfill Spring 2021}  \\ [-0.3cm]
  \begin{center} 
    {\Large Problem Set 5}
  \end{center}
  {\bf Due:} June 4, 2021 at 11:59pm
\end{minipage}}
\vspace{0.7cm}

\noindent \textbf{Instructions:} You {\bf must} typeset your solution in LaTeX
using the provided template:
\begin{center}
  \url{https://crypto.stanford.edu/cs355/21sp/homework.tex}
\end{center}

\noindent \textbf{Submission Instructions:} You must submit your problem set via
\href{https://www.gradescope.com/courses/84284}{Gradescope}. Note that
Gradescope requires that the solution to each problem starts on a \textbf{new
page}.

\medskip

\noindent \textbf{Bugs:} We make mistakes! If it looks like there might be a
mistake in the statement of a problem, please ask a clarifying question on
Piazza.

\noindent \textbf{Limited Late Days:}
You may only use one late day on this assignment.
This limitation is necessary to give us time to grade the assignment before the
final grade deadline for the quarter.

\hrule

\problem{Local Differential Privacy [10 points]}

The differential-privacy model we saw in class, where a trusted curator
aggregates all the data and then randomizes responses to queries, is also called
the \emph{central model} of differential privacy. 

In the \emph{local model} of differential privacy, the users do not want to
trust the aggregator, so they each randomize their own data locally, before
sending it to the aggregator. We'll look at a very simple local DP algorithm
called \emph{Randomized Response} (RR), which was proposed by Warner in 1965,
four decades before differential privacy was invented! The goal of RR is to
collect sensitive statistics (e.g., ``how many people do drugs'') while allowing
each individual participant in the survey some amount of \emph{deniability}.

Formally, each of the $n$ users holds a private bit $b_i\in \{0,1\}$. The
quantity we are interested in estimating is $a \coloneqq \frac1n\sum_{i=1}^n
b_i$. Consider the following RR mechanism, that is run independently by each
user:

\begin{itemize}[itemsep=0pt, label=-]
	\item Flip two unbiased coins.
	\item If the first coin is heads, send $b_i$ to the aggregator.
	\item Otherwise, look at the second coin:
	\begin{itemize}[topsep=0pt,itemsep=0pt, label=-]
		\item If heads, send $0$ to the aggregator.
		\item If tails, send $1$ to the aggregator.
	\end{itemize}
\end{itemize}

\begin{enumerate}[label=(\alph*), leftmargin=*]
	\item  Show that RR guarantees $\epsilon$-differential privacy for
	$\epsilon=\ln(3)$ for each individual user's bit.
  
	\item Let $\hat{b}_i$ be the $i$-th user's randomized response. Show that the
	untrusted aggregator that receives all these noisy bits can compute an
	unbiased estimate $\hat{a}$ of $a$ (i.e., $\Exp[\hat{a}] = a$).
    
	\item Show that the estimation error $\hat{a} - a$ has standard deviation
	$O(1/\sqrt{n})$.
  
	\item How much worse is this than what we can achieve in the central model?
	Suppose all users send their bits $b_i$ to a trusted curator that uses the
	Laplace mechanism to output a noisy estimate $\hat{a}_{\text{c}}$ of $a$ that
	is $\ln(3)$-differentially private. Show that the estimation error
	$\hat{a}_{\text{c}}-a$ has standard deviation $O(1/n)$.
  
\end{enumerate}



\problem{Private Information Retrieval [15 points]}
Throughout this question, we consider one-round information-theoretic
PIR over an $n$-bit database.

In class, we saw a simple two-server PIR with $O(n^{1/2})$ communication complexity.
In this problem, you will first construct a \textit{four}-server PIR scheme
with communication complexity $O(n^{1/3})$.
Then you will construct a \textit{two}-server 
PIR with much improved $O(n^{1/3})$
communication complexity.
As we mentioned in lecture, this $O(n^{1/3})$ scheme was essentially the 
best-known two-server PIR scheme for many many years, so in this problem you will
reprove a very nice and very non-trivial result.

\begin{enumerate}[label=(\alph*), leftmargin=*]

      \item\label{part:four} In the following box, we describe a 
        four-server PIR scheme with $O(\sqrt n)$ communication.
        Prove that the scheme is correct. Explain \textit{informally}
        in 2-3 sentences why the scheme is secure as long as the
        adversary controls at most \textit{one} server.\\
        (\textbf{Hint}: Using matrix notation will make your life easy. 
        The correctness argument should not require more than a few lines of math.)

  %\begin{figure}[!h]
  \begin{minipage}[t]{\textwidth}
  \begin{framed}
    \begin{center}
    \textbf{Four-Server $O(\sqrt n)$-Communication PIR Scheme}
    \end{center}  
    Write the $n$-bit database as a matrix $X \in \Z_2^{\sqrt n \times \sqrt n}$.
    The client wants to read the bit $X_{ij}$ from this database, where
    $i,j \in [\sqrt n]$.
    Recall that $e_i \in \Z_2^{\sqrt n}$ is the dimension-$\sqrt n$ vector that
    is zero everywhere except with a ``$1$'' at position $i$.
    \begin{itemize}
      \item $\textsf{Query}(i,j) \to (q_{00}, q_{01}, q_{10}, q_{11})$. \\
        Sample random vectors $r_0, r_1, s_0, s_1 \in \Z_2^{\sqrt n}$
        subject to $r_0 + r_1 = e_i \in \Z_2^{\sqrt n}$ 
        and $s_0 + s_1 = e_j \in \Z_2^{\sqrt n}$.\\
        For $b_0, b_1 \in \zo$, let $q_{b_0 b_1} \gets (r_{b_0}, s_{b_1})$.\\
        Output $(q_{00}, q_{01}, q_{10}, q_{11})$.
      \item $\textsf{Answer}(X, q) \to a$.\\
        Parse the query $q$ as a pair $(r, s)$ with $r,s \in \Z_2^{\sqrt n \times 1}$.\\
        Return as the answer the single bit $a \gets r^T X s \in \Z_2$.
      \item $\textsf{Reconstruct}(a_{00}, a_{01}, a_{10}, a_{11}) \to X_{ij}$.\\
        Output $X_{ij} \gets a_{00} + a_{01} + a_{10} + a_{11} \in \Z_2$.
    \end{itemize}
  \end{framed}
  \end{minipage}
%\end{figure}
 % \vspace{-0.5em}

\item\label{part:bal} 
        Say that you have a $k$-server PIR scheme that requires the client to
        upload $U(n)$ bits to each server and download one bit from each server.
        Explain how to use this scheme to construct a 
        $k$-server PIR scheme in which, for any $\ell \in \N$, each client uploads 
        $U(n/\ell)$ bits to each 
        server and downloads $\ell$ bits from each server.
        (You may assume that $n$ is a multiple of $\ell$.)

        Sketch---without a formal proof---why your construction does not break
        the correctness or security of the initial PIR scheme.

\item Show how to combine parts
  \ref{part:four} and~\ref{part:bal} 
  get a four-server PIR scheme with total 
  communication $O(n^{1/3})$.
  In particular, you should calculate the optimal
  value of the parameter $\ell$ used in part~\ref{part:bal}.

\item \label{part:eight} 
      Sketch how to generalize the PIR scheme 
      in part~\ref{part:four} to give an eight-server
      PIR scheme in which the client sends $O(n^{1/3})$ bits to each
      server and receives a single bit from each server in return.
      This should only take a few sentences to describe.

\item Now comes the grand finale! Use the \textit{eight}-server scheme from
      part~\ref{part:eight} to construct a \textit{two}-server scheme with
      communication $O(n^{1/3})$.

      \textbf{Hints:} 
      \begin{itemize}
        \item Label the queries of the eight-server scheme from part-\ref{part:eight} as $q_{000},q_{001},q_{010},\dots,q_{111}$. The two queries in your new two-server scheme should be $q_{000}$ and $q_{111}$ from the eight-server scheme. 
        \item The two servers can clearly send back the $1$-bit answers for $q_{000}$ and $q_{111}$ respectively. NOW, here is the beautiful idea: show that by sending back to the client $O(n^{1/3})$ additional bits, each of the two servers can enable the client to recover the answers for three additional queries.
    \end{itemize}

\end{enumerate}


\problem{Key-Exchange from LWE [10 points]} 
In this problem, we will formalize the concept of a \emph{non-interactive key
exchange} (NIKE) protocol, and then construct it from LWE. NIKE
protocols are a core component of Internet protocols like TLS, and the lattice-based
NIKE that we develop in this problem is a simplified variant of some of the leading
candidates in the NIST competition for standardizing post-quantum key-exchange.


\ifdefined\Setup
\else
\newcommand{\Setup}{\ms{Setup}}
\newcommand{\Publish}{\ms{Publish}}
\newcommand{\ClientMsg}{\ms{ClientPublish}}
\newcommand{\ServerMsg}{\ms{ServerPublish}}
\newcommand{\KeyGen}{\ms{KeyGen}}
\newcommand{\pp}{\ms{pp}}
\newcommand{\pub}{\ms{pub}}
\newcommand{\priv}{\ms{priv}}
\newcommand{\key}{\ms{key}}
\newcommand{\HNFLWE}{\ms{LWE}_{\ms{HNF}}}
\newcommand{\normi}[1]{\norm{#1}_\infty}
\newcommand{\roundq}[1]{\lfloor{#1}\rceil_{q/4}}
\fi


\noindent
\begin{minipage}[t]{\textwidth}
\begin{framed}
  A \emph{non-interactive key exchange} (NIKE) protocol for a key space $\calK$
  consists of the following PPT algorithms:
  \begin{itemize}
    \item $\Setup \big(1^\lambda \big) \to \pp$: On input the security parameter
      $\lambda$, the setup algorithm outputs the public parameters $\pp$. 

    \item $\ClientMsg \big(\pp \big) \to (\priv, \pub)$: On input the public
      parameters $\pp$, the client-publish algorithm outputs a secret value
      $\priv$, and a public message $\pub$. 

    \item $\ServerMsg \big(\pp \big) \to (\priv, \pub)$: On input the public
      parameters $\pp$, the server-publish algorithm outputs a secret value
      $\priv$, and a public message $\pub$. 

    \item $\KeyGen \big( \priv, \pub \big) \to \key$: On input a secret value
      $\priv$, and a public message $\pub$, the key generation algorithm outputs
      a key $\key \in \calK$. 
  \end{itemize}

  \setlist[description]{font=\bfseries}
  \begin{description}
  \item[Correctness.] We require that for all $\pp \gets
  \Setup(1^\lambda)$, $(\pub_0, \priv_0) \gets \ClientMsg(\pp)$, $(\pub_1,
  \priv_1) \gets \ServerMsg(\pp)$, we have
  \[ \Pr \big[ \KeyGen \big( \priv_0, \pub_1 \big) = \KeyGen \big(
  \priv_1, \pub_0 \big) \big] = 1 - \negl(\lambda).\]

  \item[Security.] For a NIKE protocol $(\Setup, \ClientMsg, \ServerMsg, \KeyGen)$, 
  we define the following two experiments:
  \begin{description}
    \item \textbf{Experiment} $b$ \quad ($b = 0,1$):
      \begin{itemize}
        \item The challenger computes the following:
          \begin{itemize}[label={}, noitemsep]
            \item $\pp \gets \Setup(1^\lambda)$, 
            \item $(\priv_0, \pub_0) \gets \ClientMsg(\pp)$, 
            \item $(\priv_1, \pub_1) \gets \ServerMsg(\pp)$,
            \item $\key_0 \gets \KeyGen \big( \priv_0, \pub_1 \big)$, 
            \item $\key_1 \getsr \calK$. 
          \end{itemize}
          It provides $(\pp, \pub_0, \pub_1, \key_b)$ to the adversary. 
          
        \item The adversary outputs a bit $\hat{b} \in \zo$. 
      \end{itemize}
  \end{description}
      Let $W_b$ be the event that $\calA$ outputs $1$ in Experiment $b$. Then, we
      say that a NIKE protocol is secure if       
      \[ \bigg| \Pr[W_0] - \Pr[W_1] \bigg| = \negl(\lambda) .\]
\end{description}
\end{framed}
\end{minipage}
\newpage

\begin{enumerate}[label=(\alph*), leftmargin=*]
  \item Explain in words why the security definition above captures our
    intuitive notion of security for key-exchange.

  \item Consider the following NIKE protocol:\footnote{We restrict the key space to $\calK = \zo$ for
      simplicity. To get a NIKE protocol for $\calK = \zo^{128}$,
      we can simply run 128 parallel instances of the protocol using the same
      public matrix $\Am$.}

    \noindent
    \begin{minipage}[t]{\textwidth}
    \begin{framed}
      Let $n = \poly(\lambda), q, \chi_B$ be parameters for which $\HNFLWE(n,n,q,\chi_B)$
      and $\HNFLWE(n,n+1,q,\chi_B)$ is hard. Recall from lecture that in
      practice, for $\lambda = 128$, we use $n \approx 800$. 

      \medskip
      Define the key space $\calK = \zo$ and consider the
      following algorithms.
      \begin{itemize}
        \item $\Setup \big(1^\lambda \big) \to \pp$: Sample a matrix $\Am \getsr
          \Z_q^{n \times n}$ and set $\pp = \Am$. 

        \item $\ClientMsg \big(\pp \big) \to (\priv,
          \pub)$: Sample vectors $\sv \gets \chi_B^n$, $\ev \gets \chi_B^n$. 
          Then, set $\priv = \sv$, and $\pub = \Am^T \sv + \ev$. 

        \item $\ServerMsg \big(\pp \big) \to (\priv,
          \pub)$: Sample vectors $\sv \gets \chi_B^n$, $\ev \gets \chi_B^n$. 
          Then, set $\priv = \sv$, and $\pub = \Am \sv + \ev$. 

        \item $\KeyGen \big( \priv, \pub \big) \to \key$: Let $\priv = \sv \in
          \Z_q^n$ and
          $\pub = \bv \in \Z_q^n$. The key generation algorithm first samples a
          small noise term $e \gets \chi_B$. Then, 
          if $\norm{\iprod{\sv,\bv} + e}_\infty \le \round{q/4}$,
          set $\key = 0$. Otherwise, set $\key = 1$. 
          
      \end{itemize}
    \end{framed}
    \end{minipage}

    \vspace{3mm} 
    Suppose that $q$ is prime and chosen to satisfy $4nB^2/q = \negl(\lambda)$. 
    Prove that the protocol satisfies correctness. For the proof, feel free to use
    the following fact (you do not need to prove this fact):

    \begin{minipage}[t]{\textwidth}
    \begin{framed}
      For any prime $q$, 
      for $\Am \getsr \Z_q^{n \times n}$
      any two non-zero vectors $\sv_0, \sv_1 \in \Z_q^n$, and $c \in \Z_q$,
      \[ \Pr_{\Am \gets \Z_q^{n \times n}} \big[ \sv_0^T \Am \sv_1  = c \big]
      = 1/q - \negl(\lambda), \]
      where the probability is over the random choice of $\Am$.
    \vspace{-1em}
    \end{framed}
    \end{minipage}

  \item Prove that the protocol above is secure assuming 
    $\HNFLWE(n,n,q,\chi_B)$ and $\HNFLWE(n,n+1,q,\chi_B)$. 
    The definition of $\HNFLWE$ is on the last page of this problem set.
    [\textbf{Hint:} Use a hybrid argument.]

\end{enumerate}

\begin{problem}{Time Spent [3 points for answering]} 
  How long did you spend on this problem set? This is for calibration purposes,
  and the response you provide will not affect your score.
\end{problem}

\paragraph{Optional Feedback [0 points].} Please answer the following questions
to help us design future problem sets. You do not need to answer these
questions, and if you would prefer to answer anonymously, please use this
\href{https://stanforduniversity.qualtrics.com/jfe/form/SV_6XTKIK2cWZyqpRr}{form}.
However, we do encourage you to provide us feedback on how to improve the course
experience.
\begin{enumerate}[label=(\alph*), leftmargin=*]

  \item What was your favorite problem on this problem set? Why?

  \item What was your least favorite problem on this problem set? Why?

  \item Do you have any other feedback for this problem set?

  \item Do you have any other feedback on the course?

\end{enumerate}

%\newpage
\section*{Appendix: Definition of LWE in Hermite Normal Form.}
\label{app}
We review the formal definitions of the
Learning with Errors problem in \emph{Hermite Normal Form}. Note that in this
variant of the LWE problem, the vector $\sv$ is sampled from the $B$-bounded
error distribution~$\chi_B$ instead of the uniform distribution. This version of the
LWE problem is known to be as hard as the standard LWE problem. 

\noindent
\begin{minipage}[t]{\textwidth}
\begin{framed}
  $\HNFLWE(n,m,q,\chi_B)$:
    Let $n,m,q,B \in \N$ be positive integers, and let $\chi_B$ be a
      $B$-bounded distribution over $\Z_q$. For a given adversary $\calA$, we define the
      following two experiments: \\
      
      \textbf{Experiment} $b$ \quad ($b = 0,1$):
      \begin{itemize}
        \item The challenger computes
          \[ \hspace{-8mm} \Am \getsr \Z_q^{m \times n}, \quad \sv \gets
          \chi_B^n, \quad \ev \gets
          \chi_B^m, \quad \bv_0 \gets \Am \cdot \sv + \ev, \quad \bv_1 \getsr
          \Z_q^m,\]
          and gives the tuple $(\Am, \bv_b)$ to the adversary. 
        \item The adversary outputs a bit $\hat{b} \in \zo$. 
      \end{itemize}
      Let $W_b$ be the event that $\calA$ outputs $1$ in Experiment $b$. Then, we
      define $\calA$'s advantage in solving the $\HNFLWE$ problem for the set of parameters
      $n,m,q,\chi_B$ to be
      \[ \HNFLWEadv_{n,m,q,\chi_B} \big[\calA \big] \coloneqq \bigg| \Pr[W_0] - \Pr[W_1]
      \bigg| .\]
\end{framed}
\end{minipage}

\end{document}
