%%% Document Class

\documentclass[11pt]{letter}
\usepackage[margin=1in]{geometry}


%%% Packages

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathtools}
\usepackage{booktabs}


%%% Variables

\newcommand{\courseName}{Math 480A2}
\newcommand{\hwNumber}{10}
\newcommand{\hwDueDate}{November 3, 2022}


%%% Definitions

\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}

\renewcommand{\implies}{\rightarrow}
\renewcommand{\iff}{\leftrightarrow}

\renewcommand{\vec}[1]{\mathbf{#1}}

\DeclareMathOperator{\Prob}{Pr}               % probability
\newcommand{\Exp}{\mathbb{E}}                 % expected value
\newcommand{\C}{{\rm c}}                      % complement
\newcommand{\card}[1]{\left|#1\right|}        % cardinality
\newcommand{\Pv}{\mathcal{P}}                 % prover
\newcommand{\Vf}{\mathcal{V}}                 % verifier

\DeclareMathOperator{\AND}{AND}
\DeclareMathOperator{\OR}{OR}

\renewcommand{\theenumi}{\Alph{enumi}}
\newcounter{saveenum}

%%% Document

\begin{document}

\begin{center}
	{\large \courseName, Homework \hwNumber}\\
	Due \hwDueDate\\
\end{center}

{\small \textit{Homework is graded out of a total of 10 points.  Collaboration is permitted, but you must list all coauthors on a problem's solution at the top of the page, and your writing must be your own.}}

\vspace{5mm}

\textbf{Problem 1.} (5 points) Let $G_0 = \ZZ / 83 \ZZ$ be the integers modulo 83, and let $G$ be the prime order cyclic subgroup of $G_0$ generated by $g = 3$, which has order $p = 41$.  Suppose that the following transcripts are produced by Schnorr's protocol over $G$ with public input $h = 33$: $\tau = (37, 18, 22)$, and $\tau' = (37, 29, 23)$.
\begin{enumerate}
	\item Show that $\tau$ and $\tau'$ are accepting transcripts for Schnorr's protocol.
	\item Using these two transcripts, find a witness $w$ such that $33 = 3^w \pmod{83}$.
\end{enumerate}

\vspace{3mm}

\textbf{Problem 2.} (3 points) Recall that a Pedersen commitment in a cyclic group $G$ with prime order $p$ and hard discrete logarithms is defined for a random pair of generators $g, h \in G$ by \[ \textsc{Commit}(m) = g^m h^z \] where $z$ is chosen randomly in $\{0, \ldots, p-1\}$.  Suppose that instead of random generators $g$ and $h$, you are given generators such that you know a discrete logarithm relation between them, say $h = g^k$ for some $k \in \{0, \ldots, p-1\}$.  How can this knowledge be used to break the binding property of the commitment scheme?

\vspace{3mm}

\textbf{Problem 3.} (2 points) Pick a topic for your final project, and give a brief (non-binding) summary of several specific aspects of your topic that you might want to explore in your write-up and presentation.  Also decide if you would like to work with a partner, and if so, indicate who you will be working with.

\end{document}