% Homework 9: Multiparty secure computation

<!--- ~ MathDefs   --->

\newcommand{\zo}{\{0,1\}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\getsr}{\leftarrow_R\;}
\newcommand{\Gp}{\mathbb{G}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\Epubcca}{E^{pub,cca}}
\newcommand{\Epubcpa}{E^{pub,cpa}}
\newcommand{\Epriv}{E^{priv,cca}}
\newcommand{\Sign}{S}
\newcommand{\Ver}{V}

\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}

\newcommand{\cF}{\mathcal{F}}

\newcommand{\onand}{\overline{\wedge}}

<!--- ~  --->

### Total of 115 points

1. (25 points) Let $F$ be the two party functionality such that $F(H\|C,H')$ outputs $(1,1)$ if the graph $H$ equals the graph $H'$ and $C$ is a Hamiltonian cycle and otherwise outputs $(0,0)$. Prove that a protocol for computing $F$ is a zero knowledge proof (w.r.t. an _efficient_ prover) system for the language of Hamiltonicity.


2. (25 points) Let $F$ be the $k$-party functionality that on inputs $x_1,\ldots,x_k \in \zo$ outputs to all parties the majority value of the $x_i$'s.  Prove that in any protocol that securely computes $F$,  for any adversary that controls less than half of the parties, if at least $k/2+1$ of the other parties' inputs equal $0$, then the adversary will not be able to cause an honest party to output $1$.

3. (25 points) For two distributions $X,Y$ over some set $\Omega$, we define their _total variation distance_, denoted as $\Delta(X,Y)$ as $\sum_{\omega\in\Omega}\left| \Pr[X=\omega]-\Pr[Y=\omega]\right|$. If $X$ is a distribution over $\Omega$ then we denote by $X^m$ the distribution over $\Omega^m$ where every entry of $X^m$ is sampled independently from $X$ (i.e., $\Pr[ X^m = (\omega_1,\ldots,\omega_m)]=\Pr[X=\omega_1]\cdots\Pr[X=\omega_m]$). Prove that if two distributions  $X$ and $Y$ satisfy $\Delta(X,T)<\delta$ then  $\Delta(X^m,Y^m) \leq m\delta$.

4.  (40 points) For a prime $p>5$, suppose that we select a random degree $2$ polynomial $S(x) = s_0 + s_1x+ s_2x^2$ moudlo $p$ by selecting $s_0,s_1,s_2$ independently and uniformly from $\Z_p$, and consider the random variable $(S(1),S(2),S(3),S(4),S(5)) \in \Z_p^5$.

     a. (10 points) Prove that for every distinct $i,j,k \in \{1,\ldots, 5 \}$, there is an algorithm to recover $S(0)$ from $S(i),S(j),S(k)$.

     b. (10 points) Prove that for every $i,j \in \{1,\ldots,5\}$, the distribution of $S(0),S(i),S(j)$ is the uniform distribution over $\Z_p^3$. Conclude that there is no algorithm to recover $S(0)$ from $S(i)$ and $S(j)$.

     c. (20 points) The "pretty good privacy (PGP)" software used to have (essentially) the following mechanism for key recovery. To hide a key $K\in\zo^n$, we pick a prime $p>2^n$ (and so can think of $K$ as a member of $\Z_p$). The user would record $5$ question answer pairs $(q_1,a_1),\ldots,(q_5,a_5)$ (each encoded as a string). We let $H$ be a hash function that maps $\zo^*$ to $\Z_p$ and model it as a random oracle. Then we pick a random salt $salt\in\zo^n$, random degree $2$ polynomial $S$ as above subject to $S(0)=K$ and store the data block $D=(q_1,\ldots,q_5,salt,z_1,\ldots,z_5)$ where $z_i = H(a_i\|salt)+S(i) (\mod q)$ on the user's machine.

         i.  (10 points) Prove that given this information, a user who remembers at least three of the answers to the questions can recover the key $K$.

         ii. (10 points) Prove that in the random oracle model, one can transform a time $T$ adversary $A$ that succeeds in recovering a random key $K$ from $D$ with probability at least $1/2$ into an adversary $A'$ that outputs three of the answers in $\{ a_1,\ldots, a_5 \}$ with probability at least $1/4$.