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

\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{\Mc}{\mathsf{Mac}_k}

\newcommand{\Vrf}{\mathsf{Verify}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\KG}{\mathsf{KeyGen}}
\newcommand{\DelKey}{\mathsf{DelegateKey}}





\begin{document}

%Do not modify

\begin{textblock*}{4cm}(-1.7cm,-2.3cm)

\noindent {\large CS 655-Spring 2023} 

\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 3} \\ 

\textbf{Due date: Tuesday, April 11, 2023 at 11:59PM (Gradescope)}

\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 (40 points)} 
Let $N=2^n$ and define the ``\textit{Powers of Two Graph}” (a folklore construction of a depth-robust graph) $G_n =(V,E)$ with nodes $V=[N]$ and the edge $E=\{(i-2^j, i): i \leq N \text{ and } i-2^j \geq  1\}$. 

\begin{itemize}
\item[\textbf{Part A.}] We say that a node $v \leq  N$ is $\alpha$-forward good with respect to a set $S$ of deleted nodes, if for all $r > 0$ the interval $[v,v+r-1]$ contains at most $\alpha \times r$ nodes in $S$. Suppose that $v$ is $\alpha$-forward good and let $U(j)$ denote the number of nodes in the interval $[v,v+2^j-1]$ that are not reachable from $v$ in $G_n-S$. Similarly, let $s_j$ denote the number of deleted nodes in the interval $[v,v+2^j-1]$. Use induction to prove that $U(j) \leq \sum_{i=0}^j s_i 2^{j-i} \leq j 2^j \alpha$.
 
\begin{answer}

    \dots

\end{answer}

\item [\textbf{Part B.}] Suppose that $2^j < r < 2^{j+1}$. Show that at least $r-2(j+1)r\alpha$ nodes in $[v,v+r-1]$ are reachable from $v$ in $G_n-S$.

\begin{answer}

    \dots

\end{answer}

\item [\textbf{Part C.}] We say that a node $w \leq N$ is $\alpha$-backward good with respect to a set $S$ of deleted nodes if for all $0 < r \leq w$ the interval $[w-r+1,w]$ contains at most $\alpha \times r$ nodes in $S$. Show that if node $w$ is $\alpha$-backward good and node $v < w$ is $\alpha$-forward good with respect to $S$ with $\alpha = 0.01/n$ then there is a directed path connecting $v$ to $w$ in $G_n-S$.  

\begin{answer}

    \dots

\end{answer}

\item [\textbf{Part D.}] Show that $G_n$ is $(e,d)$-depth robust with $e=\Omega(N/n)$ and $d=\Omega(N)$ and lower bound the cumulative pebbling cost $\mathsf{CC}(G_n)$.

\begin{answer}

    \dots

\end{answer}


\newpage

\item [\textbf{Part E.}] Assume that $G$ is $(e,d)$-depth-robust with $e  > d$. Suppose that we delete $|S|=e/2$ nodes from $G$. Show that the graph $G-S$ contains at least $e/(2d)$ node disjoint paths of length $d$. ({\bf Hint:} To get started, let $S_0 = S$ and let $S_1 = S_0 \cup P$ where $P$ is a directed path in $G-S_0$ containing exactly $d$ nodes.)
\begin{answer}

    \dots

\end{answer}

\item [\textbf{Part F.}] We say that a directed graph $G=(V=[N],E)$ is $(e,d,f)$-fractionally depth-robust if for any subset $|S|\leq e$ of at most $e$ nodes there is a subset $T \subseteq [N]\setminus S$ of $|T| \geq f$ nodes such that for every node $v \in T$ the graph $G-S$ contains a directed path of length $d$ ending at node $v$. Supposing that $N=2^n$ and  $G$ is $\left(\Omega(N), \Omega(N/n) \right)$-depth robust show that $G$ is $(e,d,f)$-fractionally depth-robust with $e=\Omega(N)$, $d = \Omega(N/n)$ and $f = \Omega(N)$. ({\bf Hint:} You should used what you proved in part E to get started.)  
\begin{answer}

    \dots

\end{answer}

\item  [\textbf{Part G.}] Suppose that $G$ is $(e, d, f)$-fractionally depth-robust and consider the pebbling challenge game used in the analysis of Proofs of Space. In particular, suppose that Alice can place $e' < e$ pebbles on the graph $G$ and then a challenger asks Alice to place pebbles on randomly selected nodes $v_1,\ldots, v_k$. Alice can place pebbles in parallel, but is not finished until she has placed pebbles on {\em all} of the challenge nodes $v_1,\ldots, v_k$. Upper bound the probability that Alice can complete the challenge within $d' < d$ steps. 

\begin{answer}

    \dots

\end{answer}

\end{itemize}




\begin{colabs}

	\dots 

\end{colabs}

\newpage

\section*{Question 2 (30 points)}
Recall that a point function $f_{\alpha,\beta}(x)$ outputs $\beta$ if $x=\alpha$ and $f_{\alpha,\beta}(x) =0$ otherwise. Consider the following construction of a distributed point function. The setup algorithm picks a random Puncturable PRF key $K \in \{0,1\}^\lambda$ and sets $K_0 = \mathtt{iO}(1^\lambda, C_0)$ to Alice and $K_1 = \mathtt{iO}(1^\lambda, C_{1,\alpha,\beta})$ to Bob where functionality of the circuits $C_0$ and $C_1$ are described as follows $C_0(x) \doteq F_K(x)$ and $C_{1,\alpha,\beta}(x) = F_k(x)$ if $x \neq \alpha$; otherwise if $x=\alpha$ we have $C_{1,\alpha,\beta}(x) = F_K(x) \oplus \beta$. Consider the following security game: The attacker fixes $(\alpha_0,\beta_0)$, $(\alpha_1,\beta_1)$ and a role $i \in \{0,1\}$ (indicating whether the attacker plays the role of Alice/Bob) and sends these values to the challenger. The challenger picks a random coin $b$, sets $(\alpha,\beta) = (\alpha_b,\beta_b)$ and then generates $K_0 = \mathtt{iO}(C_0)$ and $K_1 = \mathtt{iO}(C_{1,\alpha,\beta})$ and sends $K_i$ back the the attacker. Finally, the attacker outputs a guess $b'$. The attacker wins if $b'=b$ and we use $\mathtt{WIN}_{\Ad}(\lambda)$ to denote the event that the attacker $\Ad$ wins when using securing parameter $\lambda$. The advantage of an attacker $\Ad$ over random guessing is denoted $\mathtt{ADV}_{\Ad}(\lambda) = \Pr[\mathtt{WIN}_{\Ad}(\lambda)]-\frac{1}{2}$.  We say that the DPF is secure if all PPT attackers $\Ad$  there exists a negligible function $\mu(\lambda)$ upper bounding $\mathtt{ADV}_\Ad(\lambda)$. 







\begin{itemize}
    \item [\textbf{Part A. } ] (5 points) Explain how Alice and Bob can locally generate their shares of $f_{\alpha,\beta}(x)$ given any input $x$. 
        \begin{answer}

    \dots

    \end{answer}
    \item [\textbf{Part B. } ] (25 points) Prove that DPF construction is secure according to the above distribution. You may assume that the PPRF and $\mathtt{iO}$ constructions are both secure.

    \begin{answer}

    \dots

    \end{answer}
    
\end{itemize}


\begin{colabs}

	\dots 

\end{colabs}

\newpage 

\subsection*{Question 3 (30 points)} Alice wants to design a delegated signature scheme. In particular, the delegated signature scheme should implement four PPT algorithms $(\KG, \DelKey, \Sign,\Vrf)$. $\KG(1^\lambda)$ takes as input a security parameter ($\lambda$) and outputs a secret-public key pair $(sk,pk)$ and $\DelKey(sk, x)$ takes as input a prefix $x$ and the secret key $sk$ and outputs a key $sk_x$ which can be used to sign any message of the form $m=x||y$. $\Sign(sk,m)$ outputs a signature $\sigma$ such that $\Vrf(pk,\sigma,m)=1$. If $m= x||y$ then $\Sign(sk_x, m)$ outputs a signature $\sigma$ such that $\Vrf(pk,\sigma,m)=1$. However, if $x$ is not a prefix of $m$ then $\Sign(sk_x,m)=\bot$.


\paragraph{Selective security game:} In the selective security game, we fix a target message $m^*$ and then the challenger $\C$ generates $(sk,pk)$ and sends $pk$ to the attacker $\Ad$. The attacker may make $q = \mathtt{poly}(\lambda)$  queries  to $\DelKey(sk,.)$ but may not submit a query $x_i$ which is a prefix of $m^*$. The game ends when the attacker outputs an attempted forgery for $m^*$. The scheme is secure, if for all PPT attackers there is a negligible function upper bounding the probability that the attacker wins.

\begin{itemize}
    \item [\textbf{Part A.}] Use indistinguishability obfuscation to design a secure delegated signature scheme according to the above game. 

    \begin{answer}

    \dots

    \end{answer}

    \item[\textbf{Part B.}] Prove that your construction is secure according to the above definition of selective security. 
    \begin{answer}

    \dots

    \end{answer}
    
\end{itemize}


\begin{colabs}

	\dots 

\end{colabs}




\end{document}