%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace,stmaryrd}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\newcommand\nd{\textsuperscript{nd}\xspace}
\newcommand\bset{\{0,1\}}
\begin{document}
%Do not modify
\begin{textblock*}{4cm}(-1.7cm,-2.3cm)
\noindent {\large CS 555-Fall 2018} 
\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}
\begin{center}
\textbf{\Large Homework 5} \\ 
\textbf{Due date: Thursday, November 29th 3:00 PM}
\end{center}
\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
\subsection*{Question 2 (20 points)} 
Let $\left( \mathsf{Gen},\mathsf{Sign},\mathsf{Ver}\right)$ be a signature scheme. In this problem we will show how to obtain a signature scheme $\left( \mathsf{Gen}',\mathsf{Sign}',\mathsf{Ver}'\right)$ with a {\em shorter} public key using a collision-resistant hash function $H:\{0,1\}^* \rightarrow \{0,1\}^\ell$. We will assume that $H$ is a random oracle. 

\begin{itemize}
	\item $\mathsf{Gen}'\left(1^n\right)$ runs $\mathsf{Gen}\left(1^n\right)$ to obtain $(pk,sk)$ with $pk \in \{0,1\}^n$ and then outputs $pk' = H(pk)$ and $sk' = (pk,sk)$. Explain how the algorithms $\mathsf{Sign}'$ and $,\mathsf{Ver}'$ work. 
	
	\item Suppose that $ \left( \mathsf{Gen},\mathsf{Sign},\mathsf{Ver}\right)$ is a $(t,q_{sign},\epsilon)$-secure signature scheme meaning that any attacker running in time $t$ and making at most $q_{sign}$ queries to the signature oracle wins the signature forgery game with probability at most $\epsilon$. Show that $\left( \mathsf{Gen}',\mathsf{Sign}',\mathsf{Ver}'\right)$ is $\left(t',q_{sign},q_{oracle},\epsilon'\right)$-secure with $t'=t-O(q_{sign}n)$ and $\epsilon'=\epsilon-\frac{q_{oracle}}{2^\ell}$ meaning that any attacker running in time $t'$ making at most $q_{sign}$ (resp. $q_{oracle}$) queries to the signing oracle $\mathsf{Sign}'$ (resp. random oracle $H(\cdot)$) wins the signature forgery game with probability at most $\epsilon'$. 
\end{itemize}

\subsection*{Question 3 (20 points)}
Let $pk = (N,e=7)$ (resp. $sk=(N,d)$) denote the public (resp. private) key in a plain RSA signature scheme. Define the function $\mathbf{Int}:\{0,1\}^* \rightarrow \mathbb{Z}_N^*$ as follows

\[ \mathbf{Int}\left(x_1 \| ... \|x_n\right) = \sum_{i=1}^n 2^{n-i} x_i \]
on input string $x = \left(x_1 \| ... \|x_n\right) \in \{0,1\}^n$ and let $\mu$ denote an ASCII character to byte mapping in which $\mu(0) = 0^8, \mu(1) = 0^71,\mu(2)=0^610,\ldots, \mu(9)= 0^41001$. Given an ASCII message $m = m_1,\ldots,m_n$ we define $\mathbf{Encode}(m) =\mathbf{Int}\left(\mu(m_1)\| ... \| \mu (m_n) \right) $.

Finally, for and ASCII message $m$ we can set 
\[\mathbf{Sign}_{sk}\left(m\right) = \mathbf{Encode}\left(m \right)^d \mod{N} \ .\]

Suppose Alice signs the message $m=$ "Please pay Bob the following amount from my bank account (USD): 50". Suppose that Bob obtains $\sigma = \mathbf{Sign}_{sk}\left(m\right)$. Explain how Bob can obtain a signature $\sigma'$ authorizing the bank to transfer more than $\$50$. How much money can Bob make? Assume that the Bank denies transfers above $750$ million (USD) without in person authorization. You may assume that $\mathbf{Encode}(m) < N/ 2^{64}$.
\subsection*{Question 4 (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).

\end{itemize}
\subsection*{Question 5 (20 points)} 
Suppose that Alice has a secret bits $a_1$ and $a_2$ and that Bob has a secret bits $b_1,b_2$ and that Alice and Bob want to compute the function $h(a_1,a_2,b_1,b_2) = \left( b_1 \wedge \left( b_2 \oplus a_1\right), \left(b_2 \vee b_1\right) \oplus a_1  \right)$ using Yao's Garbled Circuit protocol. 
\begin{itemize}
\item[(a)] Suppose that Alice selects several random permutations $\pi_1,\pi_2,\ldots, \pi_{100}:\{(0,0),(0,1)$ $,(1,0),(1,1)\} $$\rightarrow \{(0,0),(0,1),(1,0),(1,1)\} $. Write down a garbled circuit that Alice could sends Bob in terms of these permutations. (Note: You do not need to use all 100 permutations in your solution). 
\item[(b)] Suppose that Alice is malicious, but Bob behaves honestly during the execution of the protocol. Write down a garbled circuit that Alice can send Bob to extract {\em both} secret bits $b_1$ and $b_2$.
\end{itemize}
\end{document}