\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 3}
		\end{center}
		\textbf{Due:}
		Friday, 8 May 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{Somewhat-homomorphic encryption from pairings~[10 points]}
In this problem, you will construct a ``somewhat homomorphic'' public-key
encryption scheme: it allows computing any number of additions and a single
multiplication.
Let $\G_1$ be a cyclic group of prime order $p$ and $g\in\G_1$ be a generator of
the group.
Consider the following two algorithms:

\setlist[description]{font=\normalfont}
\begin{description}
	\item[$\ms{Gen}(g)\to (\pk, \sk)$]: Choose random $a,b,c\getsr \Z_p$ such that $c\neq ab\Mod{p}$. Set $g_a=g^a$, $g_b=g^b$, and $g_c=g^c$. Output the public key $\pk = (g, g_a, g_b, g_c)$ and the secret key $\sk=(a,b,c)$.
	\item[$\ms{Enc}(\pk=(g,g_a,g_b,g_c), m)\to \ct$]: Given a message $m\in\Z_p$, choose $r\getsr \Z_p$ and output $\ct=(g^mg_a^r, g_b^mg_c^r)$.
\end{description}

\begin{enumerate}[label=(\alph*), leftmargin=*]
	\item\label{part:decrypt} Give a $\textsf{Dec}$ algorithm that takes a secret key $\sk$ and a  ciphertext $\ct=(u,v)$ and outputs $m$. Your algorithm needs to be efficient only if the message $m$ lies in some known small space (say $0\leq m< B$ as an integer, for some bound $B=O(\polylog(p))$).
	\item Give an algorithm $\ms{Add}(\pk, \ct,\ct')\to \ct_{\textrm{sum}}$ that takes as input two ciphertexts $\ct$ and $\ct'$, that are encryptions of $m,m'\in\Z_p$ respectively, and outputs an encryption of $m+m' \bmod{p}$.
\end{enumerate}

Now let $\G_2, \G_T$ be two other cyclic groups of order $p$ (i.e.,
$|\G_1|=|\G_2|=|\G_T|$), $e\colon \G_1\times\G_2\to \G_T$ be a pairing, and
$h\in\G_2$ and $e(g,h)\in\G_T$ be generators of $\G_2$ and $\G_T$ respectively.
Furthermore, let $(\pk',\sk')\leftarrow \ms{Gen}(h)$ be the public and secret
keys obtained by running $\ms{Gen}$ using the group $\G_2$. Consider now the
following algorithm:

\begin{description}
	\item[$\ms{Mult}(\ct,\ct')$]: On input two ciphertexts $\ct=(u,v)\leftarrow \ms{Enc}(\pk, m)$ and $\ct'=(u',v')\leftarrow \ms{Enc}(\pk', m')$, output the tuple $(w_1,w_2,w_3,w_4)\in\G_T^4$ where
	      \begin{equation*} \label{q4:cond}
		      w_1=e(u,u'),\quad w_2=e(u,v'),\quad w_3=e(v,u'),\quad w_4=e(v,v') \,.
	      \end{equation*}
\end{description}

\begin{enumerate}[label=(\alph*), leftmargin=*,resume]
	\item Let $\alpha_1,\dotsc,\alpha_4\in\Z_p$ such that $w_i=e(g,h)^{\alpha_i}$ (i.e., $\alpha_i$ is the discrete log of $w_i$ in $\G_T$).
	      Show that ${m\cdot m'\bmod{p}}$ can be expressed as a \emph{linear function} $\sum_{i=1}^4C_i\alpha_i$, where the coefficients $C_i$ are independent of $m,m'$. (You \emph{need not} give an explicit formula for the coefficients $C_i$.)
	\item Show how to efficiently recover $m\cdot m'\bmod{p}$ from $w_1,\dotsc,w_4$ and the two secret keys $\sk$ and $\sk'$.  As in Part~\ref{part:decrypt}, you can assume that the messages $m,m'$ lie in some known small space.
	\item \textbf{Extra credit [3 points].} Show that if the DDH assumption holds in $\G_1$ then $\calE=(\textsf{Gen}, \textsf{Enc}, \textsf{Dec})$ is a semantically secure public-key encryption scheme.

\end{enumerate}
\problem{Conceptual Questions [8 points]}

For each of the following statements, say whether it is
TRUE or FALSE. Write \textit{one sentence} to justify
your answer.

\begin{enumerate}[label=(\alph*), leftmargin=*]
	\item Let $\langle P, V \rangle$ be an interactive proof system for a language $\calL$ with a
		      {\em randomized} verifier. If $\langle P, V \rangle$ satisfies
	      perfect completeness (i.e., completeness holds with probability~$1$) and
	      perfect soundness (i.e., soundness holds with probability~$1$),
	      then there is an interactive proof system for $\calL$ with a {\em deterministic}
	      verifier.


	\item Let $\langle P, V \rangle$ be a zero-knowledge interactive protocol for some language. The protocol has perfect completeness and soundness error $1/3$. Which of the following are true:
	      \begin{enumerate}
		      \item[i] A malicious verifier interacting with an honest prover will always accept a true statement.


		      \item[ii] An honest verifier interacting with a malicious prover will ``learn nothing'' besides the statements validity.


	      \end{enumerate}

	\item If an interactive proof $\langle P, V \rangle$ for an $\classNP$ language
	      $\calL$ is a proof of knowledge with negligible knowledge error, then
	      $\langle P, V \rangle$ has negligible soundness error (i.e., a malicious prover
	      can convince an honest verifier of a false statement with at most negligible probability).



	\item If an interactive proof system has soundness error greater than $1/3$,
	      then it cannot be a proof of knowledge with knowledge error less than $1/3$.

	\item Consider a modified version of Schnorr's signature in which the signing
	      nonce $r$ is computed as $r \gets H(m)$, where $H: \zo^* \to \Z_q$ is a
	      hash function, $m$ is the message to be signed, and $q$ is the order
	      of the group used for the signature scheme.
	      This deterministic version of Schnorr's signature scheme is secure.


	\item The Fiat-Shamir heuristic (as discussed in class) is a way to construct
	      non-interactive zero-knowledge proofs \textit{without} needing
	      to rely on random oracles.


	\item In the standard model (without random oracles), there exist
	      non-interactive zero-knowledge proofs for languages in $\classBPP$.

	\item Consider a hash function $H:\calW\to\calX$, and the NP-relation $\calR_n$ for knowledge of $n$
	      pre-images of $H$. Formally, $\calR_n$ has instance space $\calX^n$, witness
	      space $\calW^n$, and is defined by
	      \(
	      \{ (
	      x \in \calX^n
	      ,
	      w \in \calW^n
	      ):
	      H(w_1) = x_1 \land H(w_2) = x_2 \land \cdots \land H(w_n) = x_n
	      \}
	      \).
	      A SNARG for $\calR_n$ must have $o(n)$ verification time.
\end{enumerate}

\problem{Understanding Zero Knowledge [15 points]}

\begin{enumerate}[label=(\alph*), leftmargin=*]
	\item Let $\calL$ be an (arbitrary) $\classNP$ language (with associated $\classNP$ relation $\calR$).
	      Moreover, assume that all instances $x \in \calL$ have a {\em unique} witness: namely,
	      for every $x \in \calL$, there is a unique $w$ where $\calR(x, w) = 1$.
	      Give an interactive
	      proof system for $\calL$ that is complete and sound but is zero knowledge
		      {\em if and only if} there exists a probabilistic polynomial time
	      algorithm $M$ that on input $x \in \calL$ outputs the (unique) $\classNP$ witness $w$
	      for the instance $x$. \big(Namely,
	      $\Pr[w \gets M(x) : \calR(x, w) = 1] \ge \frac{2}{3}$\big). Prove all the above properties.

	\item Suppose one-way functions exist. Give a language $\calL$ and an interactive
	      proof system for $\calL$ that satisfies completeness, soundness, and honest-verifier
	      zero knowledge, but \textit{not} zero knowledge. Prove that all these properties indeed hold. [{\bf Hint:} Recall from lecture
			      that assuming one-way functions exist, the $\classNP$-complete language of graph
			      $3$-colorability has a zero-knowledge proof system. Modify this proof system so
			      that the prover reveals additional information depending on the verifier's messages.
			      To show that the resulting proof system is not zero-knowledge, show that
			      the existence of a simulator (for a specific verifier) implies a decision algorithm
			      for an $\classNP$-complete language. Use this to derive a contradiction.\footnote{To
				      formally show that a protocol is {\em not} zero-knowledge, you need to give
				      a verifier $V^*$ such that for {\em all} efficient simulators, the output distribution of
				      the simulator is distinguishable from an interaction between the honest prover $P$ and
				      $V^*$.}]
\end{enumerate}


\problem{Sigma Protocol for Circuit Satisfiability [10 points]}

Let $\cSAT$ be the language of satisfiable Boolean circuits%
%
\footnote{You can assume without loss of generality that a Boolean circuit consists of only \textsc{xor} and \textsc{and} gates.}
%
:
\[ \cSAT = \left\{ C \colon \zo^n \to \zo \mid n\in\N,\: \exists (x_1, \ldots,
	x_n) \in \zo^n \text{ such that } C(x_1, \ldots, x_n) = 1 \right\}\,.
\]
Let $\Comm \colon \zo \times \calR \to \calC$ be a perfectly-binding and computationally-hiding
commitment scheme with message
space $\zo$, randomness space $\calR$, and commitment space $\calC$. Suppose
that there exist Sigma protocols $\pro{P_{\textsc{xor}}, V_{\textsc{xor}}}$
and $\pro{P_{\textsc{and}}, V_{\textsc{and}}}$ for languages $\calL_{\textsc{xor}}$ and $\calL_{\textsc{and}}$, respectively, where:
\begin{align*}
	 & \calL_{\textsc{xor}} = \left\{ (c_1, c_2, c_3) \in \calC^3 ~\left|~ \begin{array}{c} \exists (m_1, m_2, m_3) \in
		                                                                       \zo^3, (r_1, r_2, r_3) \in \calR^3 \text{ such that } \\ \forall i \in
		                                                                       \set{1,2,3}~ c_i = \Comm(m_i; r_i) \text{ and } m_1 \oplus m_2 = m_3
	                                                                       \end{array} \right. \right\} \\
	 & \calL_{\textsc{and}} = \left\{ (c_1, c_2, c_3) \in \calC^3 ~\left|~ \begin{array}{c} \exists (m_1, m_2, m_3) \in
		                                                                       \zo^3, (r_1, r_2, r_3) \in \calR^3 \text{ such that } \\ \forall i \in
		                                                                       \set{1,2,3}~ c_i = \Comm(m_i; r_i) \text{ and } m_1 \land m_2 = m_3
	                                                                       \end{array} \right. \right\}\,.
\end{align*}

%\begin{enumerate}[label=(\alph*), leftmargin=*]
%  \item
Give a Sigma protocol for $\cSAT$. In addition to describing a protocol,
you will also need to show that your protocol satisfies completeness, soundness,
and honest-verifier zero-knowledge. [\textbf{Hint:} When showing that your protocol is honest-verifier
zero-knowledge, you may want to use a hybrid argument. One of your hybrids might rely on
the commitment scheme being computationally hiding, and the other hybrid might rely on the
underlying Sigma protocols being honest-verifier zero-knowledge.]

\ignore{
	\item \textbf{Extra Credit [5 points].} Give Sigma protocols for $\calL_{\textsc{xor}}$ and $\calL_{\textsc{and}}$ when
	the underlying commitment scheme is instantiated using the Pedersen commitment scheme
	(discussed in Problem~2).
	\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 this
\href{https://forms.gle/M1dQ6EoiuyawCbvr5}{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}
