\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}

\def\handoutdate{August 7, 1998}
\def\handoutname{Problem Session 5 Solutions}
\def\handoutnumber{11S}
\input{defs}


% ========================================================================

\begin{document}


\courseheader

\bigskip
\begin{center}
{\Large{\bf Problem Session 5 Solutions}}
\end{center}

\bigskip
{\bf Problem 5.1: Secret Sharing with cheaters.}

Dishonest trustees can prevent the reconstruction of the
secret by contributing {\em bad} shares $\hat{s_i} \neq s_i$. 
Using the cryptographic tools you have seen so far in the class show how
to prevent this denial of service attack. 

{\bf Solution}

There are many ways of dealing with this issue. If we assume that the
dealer is not fraudulent, and we assume that the communications stream
is secure, then we can trust that any errors in the $s_i$ we get are
the fault of the respective trustees.

One way to ensure the shares we receive are valid is to, during the
share generation, also generate a public/private key pair. For each
share, sign the share with the private key.  When done, dispose of the
private key.  Then, when you are reconstructing, do not accept any
shares that are not well signed.

{\bf Note:}  We have to select this signature scheme carefully. For
example, RSA is bad because a person can modify the value of his share
AND the signature using the multiplicative property of RSA.

Another way is to use a random encryption scheme, and publish a random
encryption (commitment) of each share to everyone. Then, in the reveal
phase, every person publishes his share, plus the random data used in
the commitment (which he was given from the dealer).

Other methods exist that are information-theoretically secure, and
involve putting error detecing/correcting data into the
shares. However, this makes each share bigger, and requires a larger
percentage of good shares.

\clearpage
{\bf Problem 5.2: Zero--Knowledge proof for discrete logarithms}

Let $p$ be a prime and $g$ a generator modulo $p$. 
Given $y=g^x$ Alice claims she knows the discrete logarithm $x$ of $y$. 
She wants to convince Bob of this fact but she does not want to 
reveal $x$ to him. How can she do that?  (Give a zero-knowledge protocol for
this problem.)

{\bf Solution}

A zero knowledge protocol for the knowledge of the discrete log of
$y = g^x \bmod p$:

\begin{itemize}
\item P generates $r \in_R {{\mathbb Z}_{p-1}}^*$, computes $q = g^{r} \bmod
p$.

\item P sends $q$ to V.

\item V generates a challenge bit: $b \in_R \{0,1\}$, and sends it to
$P$.

\item P sends back $s = (r + bx) \bmod (p-1)$

\item V verifies that $q y^{b} = g^{s} \bmod p$

\end{itemize}

We now need to prove that the three properties of a ZKP hold:
\begin{description}
\item[Completeness] Implies that if the prover knows the secret, he
can cause the verifier to accept.

If he follows as per the protocol spec, then the verifier will always
accept, since $q y^b = g^rg^{bx} = g^{r+bx} = g^{s} \pmod p$, and so
he will pass.

\item[Soundness] If Verifier accepts, then Prover knows $x$.
\begin{definition}
A program $P$ knows $x$ in a given state if it is possible 
to easily extract $x$ by examining $P$'s outputs to several different 
inputs (from a same given starting state).
\end{definition}

In this case, we have:\\
\[
\begin{array}{cl}
\mbox{input $b=0$} & \mbox{output $r$} \\
\mbox{input $b=1$} & \mbox{output $r+x \pmod {p-1}$}
\end{array}\]
Thus $x \pmod {p-1}$ is known by $P$. 
Since $P$ has demonstrated her ability to respond to challenges, she must
be prepared to respond either way. 

Can she cheat?

\begin{eqnarray*}
P\ \mbox{guesses $b=0$}&:&\begin{array}[t]{l}
                              \mbox{pick $r\in_R Z_{p-1}$}\\
                                \mbox{output $q=g^r \pmod p$} \\
                                t=r \end{array}      \\
P\ \mbox{guesses $b=1$}&: &\begin{array}[t]{l}
                              \mbox{pick $\overbrace{r+x}^r  \in_R Z_{p-1}$}\\
                                \mbox{output $q=\frac{g^{r+x}}{g^x}=
                                      \frac{g^{r+x}}{y} \pmod p$} \\
                                t=k+x \end{array}    
\end{eqnarray*}

She can only succeed with probability 
$2^{-k}$ by guessing the challenges ($b$). 
Therefore, $P$ must `know' $x$. 

\item[zero-knowledge] holds if the transcript of a real conversation
is indistinguishable from the transcript generated by the verifier
talking to nobody.

{\bf The Transcripts of the Interactive Protool}
\begin{eqnarray*}
&&\mbox{$q$ is uniform in $Z^*_{p}$}  \\
&&\mbox{$b$ is uniform in $\{0,1\}$}  \\
&&\mbox{$s$ is uniform in $Z_{p-1}$}  
\end{eqnarray*}
Such that $qy^b=g^s$

{\bf Construction of sample transcripts without knowing $x$}
\[
\left[\begin{array}{l}
\mbox{pick $s\in_R Z_{p-1}$}\\
\mbox{pick $b\in_R \{0,1\}$}\\
\mbox{compute $q=\frac{g^s}{y^b} \pmod p$}\\
\mbox{output $(q,b,s)$}\\
\end{array}\right] \mbox{repeat for $k$ rounds}
\]

Since we have an identical distribution here, an honest verifier gains zero 
knowledge.

\end{description}
\end{document}