%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{mdframed}
\usepackage{xcolor}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\newcommand\nd{\textsuperscript{nd}\xspace}
\newcommand{\eps}{\epsilon}

\newenvironment{answer}{\begin{mdframed}\textit{Answer:}}{ \end{mdframed}}
\newenvironment{colabs}{\begin{mdframed}\textit{Resource and Collaborator Statement: }}{ \end{mdframed}}
\newenvironment{proofSK}{\begin{mdframed}\textit{Sketch:}}{ \end{mdframed}}
\newenvironment{proof}{\begin{mdframed}\textit{Proof:}}{ \end{mdframed}}
\newcommand\bset{\{0,1\}}

\newcommand{\M}{\mathcal{M}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\Ad}{\mathcal{A}}
\newcommand{\Enc}{\mathtt{Enc}}
\newcommand{\Dec}{\mathtt{Dec}}
\newcommand{\PvK}{\mathsf{PrivK}}
\newcommand{\Gen}{\mathsf{Gen}}

\begin{document}
%Do not modify
\begin{textblock*}{4cm}(-1.7cm,-2.3cm)
\noindent {\large CS 555-Spring 2021} 
\end{textblock*}
%Do not modify other than putting your name where stated
% \begin{textblock*}{8cm}(-1.5cm,-1cm)
% \noindent {Name: } 
% \end{textblock*}
%Do not modify other than typing your acknowledgement where stated
% \begin{textblock*}{13.5cm}(-1.5cm,0cm)
% \noindent {Purdue E-mail: } 
% \end{textblock*}
% \begin{textblock*}{18.5cm}(-1.5cm,0.5cm)
% \noindent \textit{\footnotesize  I collaborated with (...). I affirm that I wrote the solutions in my own words and that I understand the solutions I am submitting.} 
% \end{textblock*}
% \vspace{1cm}
%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 5} \\ 
\textbf{Due date: Thursday , April  29\nd}
\end{center}

%Rest should contain your solution for the homework. Feel free to improvise in ways that you believe make grading easier.

\subsection*{Question 1 (20 points)}
Consider a variant of the Fiat-Shamir transform (Construction 12.9 page 454) in which the signature is  $(I,s)$ rather than $(r,s)$ and verification is changed in the natural way.
Show that if the underlying identificaiton scheme is secure, then the resulting signature scheme is secure here as well. 
	\begin{answer}
		\dots 
	\end{answer}
		\begin{colabs}
		\dots 
	\end{colabs}

\subsection*{Question 2  (20 points)}
Given a prime $p > 2$ we say that $x \in \mathbb{Z}_{p}^*$ is a quadratic residue  if $x = y^2 \mod{p}$ for some $y \in \mathbb{Z}_{p}^*$. Assume that $g \in \mathbb{Z}_{p}^*$ is a generator such that $\langle g \rangle = \mathbb{Z}_{p}^*$. Let $QR_p = \{x \in \mathbb{Z}_{p}^*~:~\exists y~\mbox{s.t.}~y^2=x \mod{p} \}$.
\begin{enumerate}
	\item[a.] Show that $QR_p$ is a subgroup of $\mathbb{Z}_{p}^*$.
	\item[b.] Show that $g \notin QR_p$, but that $g^{2i} \in QR_p$ for every $i \geq 0$.
	\item[c.] Show that $\left| QR_p \right| = \frac{p-1}{2}$ (Hint: Look at Lemma 8.37). 
	\item[d.] Show that $y\in QR_p$ if and only if $y^{\frac{p-1}{2}} = 1$. In particular, this means that there is a polynomial time algorithm to test if $y \in QR_p$. 
	\item [e.]Show that the Decisional Diffie-Hellman Problem does not hold over the cyclic group  $\mathbb{Z}_{p}^*$ (although the computational Diffie-Hellman Assumption is believed to hold). 
	{\b Hint:} Use the properties you proved in previous items about quadratic residues.  You may assume  $g \in \mathbb{Z}_{p}^*$ is a generator such that $\langle g \rangle = \mathbb{Z}_{p}^*$. 
\end{enumerate}



	\begin{answer}
		
	\end{answer}
		\begin{colabs}
		\dots 
	\end{colabs}
	

	
\subsection*{Question 3 (20 points)}
Definition 12.14  of the reference book\footnote{Introduction to Modern Cryptography, 2nd Edition} presents a formal definition of weak one-time signature. According to this definition, the adversary makes the single signing query for message $ m' $ and will output $ (\sigma, m) $ and wins the \textbf{One-time signature } experiment $ \mathsf{Sig-forge}^{1-\mathsf{time}}_{\mathcal{A}, \Pi} $ if $ m\neq m' $ and $ \sigma $ is a valid signature.  

A strong one-time secure signature scheme satisfies the following: given a signature $\sigma '$ on a message $m'$, it is infeasible to output $(m,\sigma ) \ne (m',\sigma ')$ for which $\sigma$ is a valid signature on $m$ (note that $m = m'$ is allowed)

\begin{enumerate}
	\item Give a formal definition of strong one-time secure signatures.
	
	
	\item Assuming the existence of one-way functions, show a one-way function for which Lamport's scheme is not a strong one-time secure signature scheme. 

	
	\item Construct a strong one-time secure signature scheme based on any assumption use in the book. 
			\textbf{Hint:} Try to find a  particular one-way function for which Lamport's signature are strongly secure. 
	

\end{enumerate}


	\begin{answer}
		\dots 
	\end{answer}
	\begin{colabs}
		\dots 
	 \end{colabs}

	
\section*{Question 4 (20 points)}
Consider the following construction of hash function based on discrete logarithm. 

We define a fixed length hash function $ (\Gen, H) $ as follows: 

\begin{itemize}
	\item $ s\gets \Gen(1^n) $: On input $ 1^n $, this algorithm runs discrete logarithm parameter generator $ \mathcal{G}(1^n) $ to obtains the public parameters of $ (\mathbb{G}, q, h_i) $. Then this algorithm randomly samples the group elements $ h_2, \ldots, h_t \gets \mathbb{G}$ and set $ s:= \langle \mathbb{G}, q, (h_1, \ldots,  h_t) \rangle $ as the output hash key.
	
	\item $ h = H^s(x_1, \ldots,x_t ) $: This the hash algorithm which takes as input the hash key $ s = \langle \mathbb{G}, q, (h_1, \ldots,  h_t) \rangle  $ and message $ (x_1, \ldots, x_t) $ with $ x_i\in \mathbb{Z}_q $ for all $ 1\leq i \leq t $, and computes the hash $ h $ of the input message as follows: $ h = \prod_i h_i^{x_i} $. 
\end{itemize}

\begin{enumerate}
	\item [(a)] Prove that if the discrete logarithm problem is hard relative to $ \mathcal{G} $, and $ q $ is prime, then for any $ t = \mathsf{poly}(n)$ the construction is a fixed- length collision resistance hash function. 
	
	\item [(b)] Discuss how this construction can be used to obtain compression regardless of the number of bits needed to represent elements of $ \mathbb{G} $ (as long as it is polynomial in $ n $). You can denote  the bit length of elements in $ \mathbb{G} $ is a polynomial like $ p(n) $. 
	
\end{enumerate}

	\begin{answer}
		\dots 
	\end{answer}
		\begin{colabs}
		\dots 
	\end{colabs}

\section*{Question 5 (20 points)}
Consider the following Zero-Knowledge Proof for the the DDH problem. In particular, Bob (prover) and Alice (Verifier) are both given a triple $(X,Y,Z)$ where $X,Y,Z \in \langle g\rangle$ are all elements of a cycle group of prime order $p$. Bob is also given $x,y,z=xy$ such that $X=g^x,Y=g^y$ and $Z=g^z$ and wishes to prove to Alice in Zero-Knowledge that $(X,Y,Z)$ is a DDH triple. Consider the following protocol. 1) Bob picks random integer $r_1$ and $r_2$ and sends the triple $(X_1,Y_1,Z_1)$ to Alice where $X_1 = g^{r_1 +x}$, $Y_1=g^{r_2+ y}$ and $Z_1 = g^{(r_1+x)(r_2+y)}$. 2) Alice sends a challenge bit $b$ to Bob. 3) Bob reveals $e = r_1 +bx \mod{p}$ and $f = r_2 +by \mod{p}$ to Alice. 4) Alice accepts if and only if  $X_b = g^e,Y_b=g^f$ and $Z_b = g^{ef}$ where $X_0:=X_1/X$, $Y_0:=Y_1/Y$ and $Z_0:=Z_1/(ZX^{f}Y^e)$.

\begin{itemize}
	\item [(a)]  (2 points) Prove that the protocol is complete.
	
	
	\item [(b)]  (3 points) Prove that the protocol is sound in the sense that the probability Alice accepts when $(X,Y,Z)$ is not a DDH triple is at most $\frac{1}{2}$. 
	
	\item[(c)] (5 points) Prove that the protocol is zero-knowledge (Your proof should work even if the verifier behaves maliciously).
	
	\item[(d)]  (10 points) Using the Fiat-Shamir paradigm develop a non-interactive version of the above Zero-Knowledge proof (NIZK) in the random oracle model. Your protocol should be complete and should have soundness $2^{-\ell}$ for a security parameter $\ell$ against any attacker making at most $2^{\ell}$ queries to the random oracle. You should also prove that your protocol is ZK by showing that a simulator can produce an identical looking proof without knowledge of $x,y,z$ (Hint: the simulator should exploit program-ability of the random oracle).
\end{itemize}

 
 \begin{answer}
		\dots
	\end{answer}
		\begin{colabs}
		\dots 
	\end{colabs}

\end{document}