\documentclass{article}

\usepackage{amsmath, amsfonts, amsbsy, amsgen, mathrsfs, amscd}
\usepackage{amssymb}
\usepackage{algorithmicx, algorithm, algpseudocode}
\usepackage{caption}

\newcommand{\PCP}{{\mathrm{PCP}}}
\renewcommand{\P}{{\mathrm{P}}}
\newcommand{\NP}{{\mathrm{NP}}}
\newcommand{\coNP}{{\mathrm{coNP}}}
\newcommand{\poly}{{\mathrm{poly}}}
\newcommand{\twosat}{{\mathrm{2SAT}}}
\newcommand{\SAT}{{\mathrm{SAT}}}
\newcommand{\maxtwosat}{{\mathrm{MAX-2SAT}}}
\newcommand{\polylog}{{\mathrm{polylog\,}}}
\newcommand{\remove}[1]{}
\newcommand{\eps}{\epsilon}

\newcommand{\F}{\mathcal{F}}
\newcommand{\size}{{\sf size}}
\newcommand{\bbG}{\mathbb{G}}
\renewcommand{\time}{{\sf time}}
\newcommand{\bbF}{\mathbb{F}}
\newcommand{\G}{\mathcal{G}}



\setlength{\topmargin}{0.25in}
\setlength{\columnsep}{2.0pc}
\setlength{\textheight}{8.0in}
\setlength{\textwidth}{6in}
\setlength{\oddsidemargin}{-0.3in}
\setlength{\topmargin}{-.10in}
\setlength{\headheight}{0.0in} %size of head (for myheadings)
\setlength{\headsep}{0.3in} %space between head and text (for myheadings)
\setlength{\parskip}{0.0in} %space between items

\begin{document}
\begin{center}
\begin{Large}
\noindent {Homomorphic Secret Sharing -- Questions}
\end{Large}
\\ December 2018
\end{center}

\bigskip

\begin{enumerate}


\item {\bf (Private search via DPF)}
Suppose that $2$ servers hold the same set of $M$ documents, each containing $N$ keywords in $\{0,1\}^n$. We are interested in obtaining efficient private search protocols in which a client sends $O(\lambda n)$ bits to each server, where $\lambda$ is a security parameter, and receives $O(\log M)$ bits in return.  The client's search query should remain hidden from each individual server.
\begin{enumerate}
  \item Use a DPF to obtain a private search protocol as above allowing the client to learn the number of documents containing a secret keyword $w\in\{0,1\}^n$. 
  \item Show a similar protocol allowing the client to learn the number of documents containing {\em both} $w_1,w_2$, where $w_1,w_2\in\{0,1\}^n$ can be arbitrarily chosen by the client. The computational complexity of the servers can grow quadratically with $N$.
  \item Show how to use 4 servers for making the computational complexity of the servers linear in $N$.
  \end{enumerate}

\item {\bf (Error-free share conversion)}
Show that an error-free implementation of the multiplicative-to-additive share conversion procedure implies an efficient algorithm for discrete logarithm.
  
\end{enumerate}



\end{document}
