\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage[table]{xcolor}
\usepackage{adjustbox}
\usepackage{dashbox}
\usepackage{cjhebrew}
\usepackage{xspace}
\begin{document}
\input{preamble.tex}
\lecture{5}{December 28, 2017}{Nir Bitansky}{January 11}
\paragraph{Instructions:}
\begin{itemize}
\item
Type your solution and email it to "focf17hw@gmail.com", with subject "HW\#, ID\#, Name".
\item
You're encouraged to use latex. You can find on the webpage the assignment's tex file to help you.
\item
You can cooperate. However, you should write the solution by yourself, and list all collaborators for each question. Same goes for any external sources that you may use.
\item
Do not discuss solutions over the course's forum. You are more than welcome though to ask for clarifications regarding the questions themselves.
\end{itemize}
\bigskip
\begin{enumerate}
\item
Consider the GMW zero-knowledge proof system for 3COL when repeated sequentially $t = n \cdot |E|$ times. Let $G=(U,E)$ be a graph and let $P^*$ be a prover that manages the convince the verifier $V$ of accepting with probability $n^{-O(1)}$. We will prove that we can efficiently extract a legal 3-coloring of $G$ given oracle access to $P^*$.
For $i\in [t]$, let $G_i$ be the event that after $i-1$ sequential interactions with the prover, where the verifier chooses random challenges, in the next interaction, the prover provides the verifier with a valid answer with probability larger than $1-\frac{1}{|E|}$, over the verifier's random challenge.
\begin{enumerate}
\item (15 pts) Prove that the probability that in $t$ interactions the prover convinces the verifier of accepting, but non of the events $G_1,\dots,G_t$ occurred is bounded by $2^{-\Omega(n)}$.
\item (10 pts) Deduce that in $t$ interactions the probability that for some $i$, the event $G_i$ occurs is $n^{-O(1)}$.
\item (15 pts) Prove the existence of the required extractor.
\end{enumerate}
\item
Consider an auction with a seller $S$ party and three participants $A,B,C$ with inputs $a,b,c\in [2^n]$ representing they're bids. They run an MPC protocol (against malicious parties) for the function that gives $S$ the identity and the bid of the highest bidder. Assume that $b$ and $c$ are chosen at random.
\begin{enumerate}
\item (15 pts) Prove that the probability that a corrupted $A^*$ outputs $b$ is negligible.
\item (15 pts) Prove that the probability that a corrupted $A^*$ wins with bid $\max\set{b,c}$ is negligible.
\end{enumerate}
\item
In the following question, addition and multiplication are done modulo $2$.
\begin{enumerate}
\item
(15 pts) Consider the following $m$-party randomized function mapping $m$ pairs of bits to $m$ bits:
$$(a_1,b_1),\dots,(a_m,b_m) \longmapsto c_1,\dots, c_m\enspace,$$
where $c_1,\dots,c_m$ are uniform in $\zo^m$ subject to $\sum_{i\in [m]}c_i = \(\sum_{i\in [m]} a_i\) \times \(\sum_{i\in [m]} b_i\)$.\\
Describe a semi-honest protocol for computing the above function, assuming a semi-honest protocol for any two-party function.
\item
(15 pts) Use the fact that $\set{+,\times}$ is a universal set of Boolean gates to describe a semi-honest protocol for any deterministic $m$-party function.
\end{enumerate}
\item
({\bf Bonus} 10 pts) Show that any two-message $(1,2)$-OT (that is semi-honestly secure) implies public-key encryption.
\end{enumerate}
\end{document}