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

\textbf{Due date: Tuesday, April 25, 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 (30 points)} Consider the Single-Server Private-Information Retrieval problem where Bob (server) has a database $D = \{x_1,\ldots, x_n\}$. Alice would like to retrieve the item $x_i$ without revealing $i$ to Bob. Formally, a solution consists of three PPT algorithms $(\mathtt{Query}, \mathtt{Respond}, \mathtt{Recover})$. Here, $\mathtt{Query}$ takes as input a security parameter $\lambda$ (unary), an index $i \in [n]$, and random coins $R$ and outputs a query $q$ and a hint $s$ to be used later i.e., $(q,s)=\mathtt{Query}(1^\lambda, i; R)$. $\mathtt{Respond}$ takes as input a query $q$ and the database $D =\{x_1,\ldots, x_n\}$ and generates a response $r = \mathtt{Respond}(q,D)$. Finally, $\mathtt{Recover}(r,s)$ takes as input a response $r$ and a hint $s$ and outputs a value $x$. 
\paragraph{Usage} Intuitively, Alice is given $i$ and generates $(q,s)=\mathtt{Query}(1^\lambda,i; R)$. Alice sends the query $q$ to Bob who will respond with $r = \mathtt{Respond}(q,D)$. Finally, Alice recovers $x_i = \mathtt{Recover}(r,s)$. 
\paragraph{Correctness} The scheme is correct if for any database $D$ of $n$ items $x_1,\ldots,x_n$, any security parameter $\lambda$ and any random coins $R$ and any index $i \in [n]$ we have $\mathtt{Recover}(r,s) = x_i$ where $(q,s)=\mathtt{Query}(1^\lambda, i; R)$ and $r = \mathtt{Respond}(q,D)$. 


\paragraph{Security} The scheme is secure if for all PPT distinguishers $\Ad$ there is a negligible function $\mu(\ldots)$ such that for all $\lambda$ and all indices $i, j \in [n]$ we have 
\[ \left| \Pr_R\left[\Ad \left(1^\lambda, q \right) = 1 ~: (q,s) \leftarrow \mathtt{Query}(i; R) \right] - \Pr_R\left[\Ad \left(1^\lambda,q \right) = 1 ~: (q,s) \leftarrow \mathtt{Query}(j; R)  \right] \right| \leq \mu(\lambda) \ . \]






\begin{itemize}
\item[\textbf{Part A.}] Consider the Pallier construction described informally in the slides. Prove that this scheme is correct and secure and analyze the computational/communication overhead for both parties. The construction is described more formally below. \\

$\mathtt{Query}(1^\lambda, i; (R_1,R_2))$ works as follows 1) Generate a Pallier Key $(pk,sk) = \mathtt{PKeyGen}(1^\lambda,R_1)$ using random coins $R_1$, 2) Set $c_i = \mathtt{Enc}_{pk}(1)$ and $c_j= \mathtt{Enc}_{pk}(0)$ for $j \neq i$, 3) Set $q= (pk, c_1,\ldots, c_n)$ and $s = sk$ and return $(q,s)$.  \\ 

$\mathtt{Respond}(q,x_1,\ldots,x_n)$ works as follows 1) parse $q$ to extract $(pk,c_1,\ldots,c_n)$ and extract $N$ from the Pallier key $pk$, 2) compute $c_j' = c_j^{x_j} \mod{N^2}$  (Note: you may assume that $x_j < N$ for each $j \in [n]$), 3) Compute $r = \prod_{j=1}^n c_j' \mod{N^2}$ and return $r$. \\ 

$\mathtt{Recover}(r,s) \doteq \mathtt{Dec}_s(r)$. 
 
\begin{answer}

    \dots

\end{answer}

\item [\textbf{Part B.}] Assume that we have Fully Homomorphic Encryption (FHE). Develop a secure PIR protocol which reduces the communication and computation overhead for Alice. 




\begin{answer}

    \dots

\end{answer}
\item [\textbf{Part c.}] Prove your construction in part B is secure. 




\begin{answer}

    \dots

\end{answer}

\end{itemize}




\begin{colabs}

	\dots 

\end{colabs}

\newpage

\section*{Question 2 (40 points)} Consider a quantum attacker $\Ad$ who has quantum access to the random oracle $H:\{0,1\}^{2\lambda}\rightarrow \{0,1\}^{\lambda}$ and classical access to the oracle $H(K,\cdot)$ where $K \in \{0,1\}^\lambda$ is a uniformly random key (unknown to the attacker $\Ad$). In many applications it makes sense to assume that $\Ad$ only has classical access to the latter oracle $H(K,\cdot)$ e.g., because the attacker can only observe the response $H(K,x)$ if it convinces the honest party to encrypt a classical message related to $x$. We define two hybrids: $H_0$ and $H_1$. In $H_0$ (real world) we pick $K$ randomly the attacker gets quantum access to $H(\cdot)$ and classical access to the oracle $H(K,\cdot)$ as above. In $H_1$ the attacker still gets quantum access to $H(\cdot)$, but the oracle $H(K,\cdot)$ is replaced by a truly random function $f:\{0,1\}^{\lambda}\rightarrow \{0,1\}^{\lambda}$ which is unrelated to $H(\cdot)$. Let $p_0$ (resp. $p_1$) denote the probability that $\Ad$ outputs $1$ in hybrid $H_0$ (resp. $H_0$) then the advantage of the attacker is $\mathtt{ADV}_{\Ad} = |p_0-p_1|$.

\begin{itemize}

    \item [\textbf{Part A} ] (10 points) As a warm-up suppose that $\Ad^{H(\cdot)}$ makes at most $T$ queries to $H(\cdot)$ and only has access to the oracle $H(\cdot)$ i.e. $\Ad$ makes no queries to $H(K,\cdot)$. Let $\psi_0^s, \psi_1^s,\ldots,\psi_T^s$ denote the states after each query to the random oracle $H(\cdot)$ when we run $\Ad^{H(\cdot)}(s)$ on initial input $s$. For each key $K' \in \{0,1\}^\lambda$ let $S_{K'} = \{ (K',x) : x \in \{0,1\}^\lambda \} $. Given a quantum state $\phi = \sum_{x,y,z} \alpha_{x,y,z} 
 \left|x,y,z\right\rangle$ let $\mathtt{QM}(K', \phi) \doteq \sum_{x,y,z: x \in S_{K'}} \left| \alpha_{x,y,z} \right|^2 $ denote the magnitude on basis states where we are making a query of the form $H(K',\cdot)$. We say that a key $K'$ is $\epsilon$-bad for the pair $(s,H(\cdot))$ if \[ \sum_{i=0}^{T-1} \mathtt{QM}(K', \psi_i^s ) \geq \epsilon \ . \]
 Formally, let $\mathtt{K}_{\epsilon,s,H} = \left\{K': \sum_{i=0}^{T-1} \mathtt{QM}(K', \psi_i^s ) \geq \epsilon \right\}$ denote the set of $\epsilon$-bad keys $K'$. Fix any pair $(s,H)$ and upper bound $\left| \mathtt{K}_{\epsilon,s,H}\right|$ the number of $\epsilon$-bad keys. Your upper bound should be a function of $T$ and $\epsilon$. 
        \begin{answer}

    \dots

    \end{answer}
  \item [\textbf{Part B. } ] (10 points) Let $F:\{0,1\}^\lambda \rightarrow \{0,1\}^\lambda$ be any function and let $H_{F,K}(\cdot)$ denote an oracle such that $H_{F,K}(K,x) = F(x)$ and $H_{F,K}(K',x) = H(K',x)$ whenever $K' \neq K$. Let $s_F \in \{0,1\}^{\lambda 2^\lambda}$ be a bit string describing the truth table of $F(\cdot)$.  
  
  Suppose that $K \not \in \mathtt{K}_{\epsilon,s_F,H}$. Upper bound the Euclidean distance between $\psi_t^{s_F}$ (the final state when we run $\Ad^{H(\cdot)}(s_F)$) and $\psi_{t,K}^{s_F}$ (the final state when we run $\Ad^{H_{F,K}(\cdot)}(s_F)$) 
 
        \begin{answer}

    \dots

    \end{answer}
    
    \item [\textbf{Part C. } ] (10 points) Assume that the attacker $\Ad$ makes at most $q_1$ quantum queries to $H(\cdot)$ and at most $q_2$ classical queries to the second oracle (either $H(K,\cdot)$ or $f(\cdot)$). Upper bound $\mathtt{ADV}_{\Ad}$.
        \begin{answer}

    \dots

    \end{answer}
    \item [\textbf{Part D. } ] (10 points) Consider the encryption scheme $\mathtt{Enc}_{K}(m) = (r,H(K,r) \oplus m)$. Argue that the scheme is CPA-Secure in the Quantum Random Oracle Model. 

    \begin{answer}

    \dots

    \end{answer}
    
\end{itemize}


\begin{colabs}

	\dots 

\end{colabs}

\newpage 

\subsection*{Question 3 (30 points)} In this problem we consider the Private Two-Server Keyword Search problem. Suppose that two servers $B$ and $C$ each hold a copy of the database $D=\{(x_1,y_1),\ldots,(x_n,y_n) \}$ where $x_1,\ldots, x_n$ denote distinct keywords and $y_1,\ldots, y_n \in \{0,1\}^m\setminus \{0^m\}$ denote documents. Alice $A$ would like to search for a specific keyword $x$ and retrieve the associated document $y$ if the pair $(x,y) \in D$ appears in the database. Alice does not want server B or C to learn the value of the query $x$. This rules out a naive protocol where Alice send $x$ to either server. However, Alice does trust that servers $B$ and $C$ will not communicate.  
\begin{itemize}
    \item [\textbf{Part A.}] Formalize the intuitive security property i.e., provide a formal security definition (Concrete/Asymptotic style definitions are both acceptable) 
    \begin{answer}

    \dots

    \end{answer}

    \item[\textbf{Part B.}] Define a secure two-server protocol using Distributed Point Functions. For full credit you should make sure that Alice's computational/communication complexity remains as low as possible. {\bf Note:} You may assume that the Distributed Point Function  shares $f_1$ and $f_2$ of the point function $f_{\alpha,\beta}(\cdot)$ \footnote{Recall that the point function $f_{\alpha,\beta}(\cdot)$ is defined as follows $f_{\alpha,\beta}(\alpha) = \beta$ and $f_{\alpha,\beta}(x) = 0$ for all inputs $x \neq \alpha$.} which, on input $x$, output additive shares $f_1(x)$ and $f_2(x)$ such that $f_1(x) + f_2(x) = f_{\alpha,\beta}(x) \mod{2^m}$ for all inputs $x$.  
    
    \begin{answer}

    \dots

    \end{answer}

        \item[\textbf{Part C.}] Argue that your protocol is secure.
    
    \begin{answer}

    \dots

    \end{answer}
    
\end{itemize}


\begin{colabs}

	\dots 

\end{colabs}




\end{document}