\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 4803/8803 PC: Programmable Cryptography \hfill Fall 2026} \\
  \begin{center}
    {\Large Homework 1}
  \end{center}
\textbf{Due:}
6pm, Friday, 4 September 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://faculty.cc.gatech.edu/~aozdemir/class/pc26/homework.tex}
\end{center}

\noindent \textbf{Submission Instructions:} You must submit your problem set
via \href{https://www.gradescope.com/courses/1351923}{Gradescope}. Please use course code
\textbf{4DN8ZD} 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{A PRG hybrid argument [15 points]}
Let $G$ be a PRG from
$\zo^\lambda$ to $\zo^{2\lambda}$.
%
Use a hybrid argument to prove that
\[
  G'( (s_1, s_2) ) = ( G(s_1), G(s_2) )
\]
is a PRG.
\problem{PRG true-or-false [15 points]}
Let $G$ be a PRG from
$\zo^\lambda$ to $\zo^{2\lambda}$.
Let $G'$ be PRG from
$\zo^{2\lambda}$ to $\zo^{3\lambda}$.
%
Is each of the following $G_i$ a PRG: true or false?
If true, give a 1-2 sentence justification.
If false, describe the attack in 1-2 sentences.
\begin{enumerate}
  \item $G_1( s ) = (s, G(s))$
  \item $G_2( (s_1, s_2) ) = (s_1, G(s_2))$
  \item $G_3( s ) = G'(G(s))$
  \item $G_4( s ) = G(s) \oplus G(s)$
  \item $G_5( s ) = (G(s), G(s))$
\end{enumerate}
\problem{Multi-Commitments [15 points]}

Let $\G$ be a group of prime order $q$ in which the discrete logarithm problem is hard.
Let $g$ and $h$ be generators of $\G$. 
As we saw in class, 
the Pedersen commitment scheme commits to a message $m \in \Z_q$
using randomness $r \in \Z_q$ as $\Commit(m; r) \deq g^m h^r \in \G$.
The ``public parameters'' associated with the Pedersen commitment scheme
are the description of the prime-order group
$\G$ and the group elements $g$ and $h$.

\begin{enumerate}[label=(\alph*), leftmargin=*]
\item Use $\G$ to construct an additively homomorphic commitment scheme $\Commit_n(m_1, \dots, m_n; r)$
      that commits to a length-$n$ vector of messages $(m_1, \dots, m_n) \in \Z_q$
		using randomness $r \in \Z_q$. The output of the commitment should be short -- only a single group element.
		%with only a \emph{single} group element (i.e., the type signature is
		%$\Commit_n \colon \Z_q^n \times \Z_q \to \G$).
    You should specify both the public parameters of your scheme (which may be different from
      that of the basic Pedersen commitment scheme) as well as the description of the
      $\Commit_n$ function.
      
\item Prove that your commitment scheme is perfectly hiding and
      computationally binding (assuming hardness of discrete log in $\G$).
\end{enumerate}
\problem{Implementation: coin flipping [15 points]}

This problem is a way to learn a little Rust while implementing a cool
secure-computation protocol.
%
(The Rust will come in handy for future problems.)
%
Your task is to implement Blum's coin-flipping protocol
and Pedersen commitments,
as we described in class.
%
The protocol is:

\begin{figure}[H]
\centering
\begin{minipage}{.48\linewidth}
\begin{algorithm}[H]
  \caption{Alice (speaks first)}
  \label{alg:alice}
\begin{algorithmic}[1]
  \State $b_A \getsr \zo$, \quad $r \getsr \Z_q$
  \State $c \gets \Commit(b_A; r)$
  \State send $c$ to Bob
  \State receive $b_B$ from Bob
  \State send the opening $(b_A, r)$ to Bob
  \State \Return $b_A \oplus b_B$
\end{algorithmic}
\end{algorithm}
\end{minipage}
\hfill
\begin{minipage}{.48\linewidth}
\begin{algorithm}[H]
  \caption{Bob (speaks second)}
  \label{alg:bob}
\begin{algorithmic}[1]
  \State receive $c$ from Alice
  \State $b_B \getsr \zo$
  \State send $b_B$ to Alice
  \State receive $(b_A, r)$ from Alice
  \State \textbf{if} $c \ne \Commit(b_A; r)$ \textbf{then} abort
  \State \Return $b_A \oplus b_B$
\end{algorithmic}
\end{algorithm}
\end{minipage}
\end{figure}

\paragraph{Toolchain}
You need Rust, \texttt{make}, \texttt{zip}, \texttt{unzip}, and a bash shell.
%
Install Rust with rustup (\url{https://rustup.rs}) on every platform;
pre-installed Rust version may be too old.
%
For the rest of the toolchain:
\begin{itemize}
  \item Linux:
    you likely already have it,
    if not, use your package manager,
    e.g. \texttt{sudo apt install build-essential zip unzip}.
  \item macOS:
    \texttt{xcode-select -{}-install} supplies \texttt{make} and the linker;
    \texttt{zip}/\texttt{unzip} are already installed.
  \item Windows: use WSL and follow the Linux instructions there.
    Keep the crate in the Linux filesystem
    (\texttt{\textasciitilde/coin\_flip})
    rather than under \texttt{/mnt/c/\ldots}.
\end{itemize}

If you are new to Rust, I recommend using VS Code with the
\textbf{rust-analyzer} extension,
which works on every platform.
%
(On WSL, install VS Code on Windows together with its \textbf{WSL} extension,
then run ``\texttt{code .}'' from a WSL shell and accept the prompt to install
rust-analyzer \textit{into} WSL.)

\textit{Note: we'll be writing somewhat `simple' Rust code,
but the language can still be challenging.
Feel free to ask for help at office hours or from each other.}

\paragraph{What to implement}
Start from \texttt{coin\_flip-starter.zip}, which unpacks into a Rust crate in a
directory named \texttt{coin\_flip}.
%
{\color{blue}
You will implement \texttt{commit} and the Alice and Bob branches of
\texttt{main}, inside \texttt{src/main.rs}.}
%
Many of the basics are implemented for you:
the group (\texttt{Group}),
its scalars (\texttt{Scalar}),
operations over them (\texttt{+}, \texttt{-}, \texttt{*}, \ldots),
the generators (\texttt{g()}, \texttt{h()}),
sampling (\texttt{random\_bit()}, \texttt{random\_scalar()}),
conversion (\texttt{bit\_to\_scalar()}),
connection setup (\texttt{connect\_to\_peer}),
and
serialization
(\texttt{read}/\texttt{write}, which send any \texttt{arkworks} value---or a
tuple of them---over the socket).

\paragraph{Resources}
You may find the following resources helpful:
\begin{itemize}
  \item The Rust Book, if the language is new to you:
    \url{https://doc.rust-lang.org/book/}
  \item arkworks field documentation: \url{https://docs.rs/ark-ff/}
  \item arkworks group documentation: \url{https://docs.rs/ark-ec/}:
    the group operations live here: \texttt{+} between two group elements,
    and \texttt{*} between a group element and a \texttt{Scalar}.
  \item documentation for other arkworks crates is also online
\end{itemize}

\paragraph{Testing}
Your \texttt{main} is a binary
that takes the party name as its only argument,
and each party prints the agreed-upon bit (as \texttt{0} or \texttt{1}) and exits.
%
Alice listens and Bob connects, so start Alice first:

\begin{verbatim}
    $ cargo run -- alice      # terminal 1
    $ cargo run -- bob        # terminal 2
\end{verbatim}

Both parties use TCP port 27183 on \texttt{localhost}.
%
If you see ``address already in use'' or a hang, a party from an earlier run is
probably still alive; kill it and try again.

You can type-check, lint, build, and run basic tests with the
\texttt{Makefile}:

\begin{verbatim}
    $ make check              # type-check, check format, and lint
    $ make build              # build
    $ make test               # build, then test (20 trials)
\end{verbatim}


\paragraph{Submitting}
In the crate directory, run

\begin{verbatim}
    $ make zip
\end{verbatim}

which cleans the build artifacts and writes
\texttt{../coin\_flip-solution.zip}, a zip of the whole crate, one directory
up. Submit that zip file.

\paragraph{Grading}
``\texttt{make test}'' just tests correctness,
but your protocol
will also be hand-graded for security.
Be sure to implement all of Blum's protocol!
\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_3DHvozY6gXerpsO}{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 so far?

\end{enumerate}
\end{document}
