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