\documentclass[11pt]{article}

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

\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 2026}  \
  \begin{center}
    {\Large Problem Set 5}
  \end{center}
\textbf{Due:}
Friday, 5 June 2026 (submit via Gradescope)
\end{minipage}}
\vspace{0.7cm}

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

\noindent \textbf{Submission Instructions:} You must submit your problem set
via \href{https://gradescope.com/}{Gradescope}. Please use course code
\textbf{X85KN6} to sign up. 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 Ed.

\hrule
\problem{True/False [4 points]}
\begin{enumerate}
  \item
  For any pair of points $(x_1, y_1), (x_2, y_2) \in \Z_{6}^2$, where $x_1 \ne
  x_2$,
  there is a polynomial $p$ of degree at most $1$
  such that
  $p(x_1) = y_1$
  and
  $p(x_2) = y_2$.
  (Note: ``$6$'' is not a prime.)

  \item
  You and your friends want to determine which one of you has the lowest
  salary. You design and run a protocol, at the end of which all your friends
  learn that their Big 4 salaries$\textsuperscript{TM}$ are higher than yours.
  This blatant invasion of your privacy could have been avoided if you had
  used a proper maliciously-secure MPC protocol.

  \item In Yao's protocol for secure two-party computation
       of a function $f(\cdot, \cdot)$ (as described in lecture), the two parties must
       exchange a number of bits that is at least as large as
       a Boolean circuit computing~$f$.

 \item Say that Alice, with input $x \in \zo$, and Bob, with input $y \in \zo$,
       use Yao's protocol to compute $f(x,y) \in \zo$, for some function
       $f: \zo \times \zo \to \zo$. Then, under reasonable computational assumptions,
       the protocol must hide $y$ from Alice---that is, Alice's probability of guessing
       Bob's bit after running the protocol
       is at most $1/2 + \negl(\lambda)$, for security parameter $\lambda$.
\end{enumerate}

\problem{Generating Beaver Multiplication Triples [15 points]}
Recall from lecture that Beaver multiplication triples enables general multiparty
computation on secret-shared data. In this problem, we will explore two
methods that can be used to generate Beaver multiplication triples. For simplicity,
we will just consider the two-party setting and we will generate Beaver multiplication triples
over the binary field $\Z_2$ (where addition corresponds to xor).
To be precise, we first describe an ``idealized
process'' for generating a single multiplication triple. In this ``idealized process'',
a trusted party generates the triple and then distributes the shares of the
triple to the two parties Alice and Bob.
\begin{enumerate}
  \item The trusted party chooses $a, b \getsr \Z_2$ and computes $c = ab \in \Z_2$.

  \item The trusted party distributes a 2-out-of-2 secret sharing of
  $a$, $b$, and $c$ to Alice and Bob. Specifically,
  the trusted party samples $r_a, r_b, r_c \getsr \Z_2$ and gives $r_a, r_b, r_c$
  to Alice. The trusted party then computes $s_a = a \oplus r_a$, $s_b = b \oplus r_b$, and $s_c = c \oplus r_c$,
  and gives $s_a, s_b, s_c$ to Bob.
\end{enumerate}
By construction $[a] = (r_a, s_a)$ is an additive secret-sharing of $a$,
$[b] = (r_b, s_b)$ is an additive secret-sharing of $b$, and
$[c] = (r_c, s_c)$ is an additive secret-sharing of $c$. Moreover, $c = ab$,
so $([a], [b], [c])$ is a valid Beaver multiplication triple.

\medskip

\noindent We will show how Alice and Bob can generate these Beaver
triples without relying on a trusted party. Throughout this problem, you may assume that
Alice and Bob are ``honest-but-curious'' (namely, they follow the protocol exactly as described,
but may try to infer additional information from the protocol transcript---this is the model
that we considered in lecture).

\begin{enumerate}[label=(\alph*), leftmargin=*]
 \item Show how Alice and Bob can generate a Beaver multiplication triple using
 Yao's protocol.\footnote{You may use the variant of Yao's protocol where only one
 party receives output (and the other party learns nothing).} Your construction should not make any
 modifications to the internal details of Yao's protocol (in fact, any secure two-party
 computation protocol can be used here). Then, give an {\em informal} argument why your
 protocol is correct and secure. [\textbf{Hint:} To apply Yao's protocol, you will need
 to come up with a two-party functionality $f$ that Alice and Bob will jointly compute. Try
 letting Alice's inputs to $f$ be her shares $(r_a, r_b, r_c)$, which she samples
 uniformly at random at the beginning of the protocol.]



 \item Show how Alice and Bob can use a {\em single invocation} of an
 $1$-out-of-$4$ oblivious transfer (OT) protocol (on $1$-bit messages)
 to generate a Beaver multiplication triple. Give an {\em informal} argument why your
 protocol is correct and secure. (In a $1$-out-of-$n$ OT, the sender has $n$ messages
 $m_1, \ldots, m_n$, while the receiver has a single index $i \in [n]$. At the
 end of the protocol execution, the sender learns nothing while the receiver
 learns $m_i$ (and nothing else). The formal definitions of sender and receiver privacy are the
 analogs of those presented in lecture.) [\textbf{Hint:} Try using OT to directly
 evaluate the functionality $f$ you constructed from Part~(a).]


 \item Let $\ell \in \N$ be a constant. Show how to build a $1$-out-of-$2^\ell$ OT protocol (on $1$-bit messages)
 using $\ell$ invocations of an $1$-out-of-$2$ OT protocol (on $\lambda$-bit messages) together with a PRF
 $F \colon \zo^\lambda \times \zo^\ell \to \zo$. Here, $\zo^\lambda$ is the key-space of the PRF
 and $\zo^\ell$ is the domain of the PRF. Then, give an {\em informal} argument for why
 your protocol satisfies correctness, sender privacy, and receiver privacy.
 [\textbf{Hint:} Start by having the sender
 sample $2 \ell$ independent PRF keys. The sender will use these keys to blind each of its
 messages $m_1, \ldots, m_{2^\ell}$.]

\end{enumerate}


\problem{Key-Exchange from LWE [18 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 when $\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)\]
  where the probability is taken over the randomness of all procedures.

  \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}
    Here, $\round{q/4}$ denotes the integer closest to $q/4$, with ties broken
    downward.
    %
    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 [1 point 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 the anonymous feedback form available on the course website.
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 so far?

\end{enumerate}

\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}
