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

\def\handoutdate{August 6, 1998}
\def\handoutname{Problem Session 4 Solutions}
\def\handoutnumber{10S}
\input{defs}


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

\begin{document}

\courseheader

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

\bigskip
{\bf Problem 4.1: The Ong-Schnorr-Shamir signature scheme.}

Ong, Schnorr and Shamir suggested the following signature scheme. 

Let $n$ be a large integer (it is not necessary to know the factorization
of $n$.) Then choose $k \in Z_n^*$. Let 
\[ h = -k^{-2} \bmod n = -(k^{-1})^2 \bmod n \]
The public key is $(n,h)$, the secret key is $k$. 

To sign a message $M$, generate a random number $r$, such that 
$r$ and $n$ are relatively prime. Then calculate
\[ S_1 = \frac{M/r+r}{2} \bmod n \]
\[ S_2 = \frac{k}{2}(M/r-r) \]
The pair $(S_1,S_2)$ is the signature. 

To verify the signature, check that 
\[ M = S_1^2 + h S_2^2 \bmod n \]
\begin{enumerate}
\item Prove that reconstructing the private key from the public key is 
equivalent to factoring $n$. 

{\bf Solution}

Given a black box that finds the private key from the public key, we
construct a factoring algorithm that operates in the following manner:

\begin{itemize}
\item Pick a random number $z \in {{\mathbb Z}_n}^*$
\item Call the black box function $B()$ thus: $y = B(-(z^{-1})^2)
\pmod n$.
\item Repeat until $y^{-1} \neq \pm z^{-1} \pmod n$
\item We now have two square roots of some number in ${{\mathbb
Z}_n}^*$. We can use $gcd(z^{-1}+y^{-1}, n)$ to break up $n$ into components,
and therefore factor $n$.
\end{itemize}

\item Is that enough to say that the scheme is secure? 

{\bf Solution}

Normally, the answer is just ``no'', since there may be a completely
unrelated way to sign without computing the private key from the
public key. In fact, that is exactly the case here. We can discover
the private key through a chosen-message attack:

Ask for the signature of $M = 0$ This gives us $S_1 = r/2$, $S_2 =
-rk/2$. Therefore $k = - S_2 / S_1$.

\end{enumerate}


\clearpage
{\bf Problem 4.2: Extending Pseudo Randomness}

Suppose you are given a PRG $G$ which stretches a $k$ bit seed into a
$2k$ bit pseudorandom sequence. We would like to construct a PRG $G'$
which stretches a $k$ bit seed into a $3k$ bit pseudorandom sequence.

Let $G_1(s)$ denote the first $k$  bits of the string $G(s)$ and
let $G_2(s)$ the last $k$ bits (that is $G(s)=G_1(s).G_2(s)$ where
$a.b$ denotes the concatenation of strings $a$ and $b$.)

Consider the two constructions
\begin{enumerate}

\item $G'(s)=G_1(s).G(G_1(s))$

{\bf Solution}  Since $G()$ is deterministic, our distinguisher can
easily tell the random sequence from the generated sequence. If the
distinguisher gets a sequence of bits $x = x_1 \cdot x_2 \cdot x_3$,
He can check whether $G(x_1) = x_2 \cdot x_3$. If this is the case,
then we probably have a generated sequence (there is a
$\frac{1}{2^{2k}}$ possibility that the random last $2/3$ bits of the
string happen to be equal to $G(x_1)$). So, the advantage of thse
distinguisher is basically: $1 - \frac{1}{2^{2k}}$.

\item $G''(s)=G_1(s).G(G_2(s))$

{\bf Solution} This scheme appears to be secure. It can be argued that
if it was possible to distinguish, then either you can tell from the
first third (meaning $G()$ is weak), or the other 2/3 (meaning G() is
weak) or from some relationship between the first and second half of a
sequence generated by $G()$ (which makes $G()$ weak).

\end{enumerate}
For each construction indicate whether you think it works or not. 
If the answer is no, provide a simple statistical test that 
distinguishes the output of the construction from a random $3k$ bit
string. 

\clearpage

{\bf Problem 4.3: Distribution of Diffie-Hellman keys}

Recall the Diffie-Hellman key exchange protocol. $p$ is a prime
and $g$ a generator of $Z_p^*$. Alice's secret key is a random 
$a<p$ and her public key is $g^a \bmod p$. Similarly Bob's secret key 
is a random $b<p$ and his public key is $g^b \bmod p$. Their common
key is $g^{ab}$.
\begin{enumerate}
\item 
What is the probability that $g^a$ is a square $ \bmod\ p$? 
\quad $g^b$?  \quad $g^{ab}$? 

{\bf Solution}.

 If $a$ is selected at random, then $g^a$ is functionally a random
element of ${\mathbb Z}_p$. The probability that $g^a$ is a square is
the same as the probability that $a$ is even. Which is, of course,
$1/2$. (This is a property of elements in a prime field : half are QR
and half are NQR).

The same argument as above holds for $g^b$. There is a 50\% chance
that it is a square.

$g^{ab}$ is a square iff $ab$ are even. From basic math we know this
probability to be $3/4$

\item 
Is the Diffie Hellman key uniformly distributed over all possible
keys in $Z_p^*$?  

{\bf Solution}

Clearly the answer is no. In ${{\mathbb Z}_p}^*$, half the elements are
QR, and half are NQR. In our diffie-hellman distribution, $3/4$ are
QR, so the distribution is different.

\end{enumerate}

\clearpage

{\bf Problem 4.4: Hardness on Average}

In this problem we will prove that if the RSA nction is invertible
on a fraction of the inputs, then it is invertible on almost
all inputs. 

Consequently, if we assume that RSA is secure for a small fraction of the
values, then it is secure for almost all values, and in particular it
is secure on average (for random values). 

We will also prove a similar claim about the Diffie-Hellman key
exchange protocol. 

\begin{enumerate}
\item
Let $\epsilon$, $\delta \in (0,1)$.  % and let $S \subseteq I$.
Show that if there is a probabilistic algorithm $\cal A$ such that for all 
$(n,e)$, where $n=pq$, $gcd(e,\phi(n))=1$, 
\[ \Pr[{\cal A}(n,e,RSA_{n,e}(x)) = x] > \epsilon \]
(where the probability is taken over $x \in {\bf Z}_n^*$ and the coin tosses
of $\cal A$) and $\cal A$ runs in time polynomial in $|n|$, \\
Then there is a probabilistic algorithm $\cal B$ running in time polynomial in
$\epsilon^{-1},\delta^{-1}$, and $|n|$ such that for all $(n,e)$,
and $x \in {\bf Z}_n^*$
\[ \Pr[{\cal B}(n,e,RSA_{n,e}(x)) = x] > 1 - \delta \]
(where the probability is taken over the coin tosses of $\cal B$).

{\bf Solution}

We will use to our advantage the fact that RSA has a multiplicative
property.

define $B()$:
\begin{itemize}
\item choose $z \in_R {{\mathbb Z}_n}^*$.
\item $y \leftarrow A(n,e,RSA_{n,e}(x)\cdot RSA_{n,w}(z)) = A(n,e,
RSA_{n,e}(xz))$.
\item If A succeeds, then $y=xz$ so $x = z^{-1}y$. Verify that $x$ is
right, and output it. Else repeat (up to $t$ times)
\end{itemize}

Now we want to know what is the probability that $B()$ fails.

\begin{equation*}
\begin{split}
\Pr \left[ B \left( n,e, RSA_{n,e}(x) \right) \neq x \right] & =
	\left[ \Pr \left[A \left(n,e,RSA_{n,e}(xz) \neq xz \right)
		\right] \right]^t \\
	& < (1-\epsilon)^t = \left[ (1 - \epsilon)^{1/\epsilon}
	\right]^{\epsilon t} \leq e^{-\epsilon t}
\end{split}
\end{equation*}

Now, if we select $t$ such that $e^{-\epsilon t} < \delta$, we have
the fact that $-\epsilon t < \log (\delta)$, or:
\[ t > \epsilon^{-1} \log (\delta^{-1}) \].

The Probability that $B()$ succeeds given the above choice of $t$ is
$1-\Pr()$, which is therefore $1-\delta$.


\bigskip
\item
Let $\epsilon$, $\delta \in (0,1)$.
Show that if there is a probabilistic algorithm $\cal A$ such that 
for all primes $p$ and for all generators $g$ of ${\bf Z}_p^*$
\[ Prob[{\cal A}(g^a,g^b)=g^{ab}] > \epsilon \]
(where the probability is taken over the choices of $(a,b)$ and the 
internal coin tosses of $\cal A$), \\
Then there is a probablilistic algorithm $\cal B$ such that for all
$(a,b)$
\[ Prob[{\cal B}(g^a,g^b)=g^{ab}]>1-\delta \]
(where the probability is now taken only over the coin tosses of $\cal B$)
  
{\bf Solution}

the following algorithm for $B$ is presented:
\begin{itemize}
\item choose $(r_1, r_2) \in_R {{\mathbb Z}_n}^*$
\item $y \leftarrow A(g^a g^{r_1}, g^b g^{r_2}) = A(g^{a+r_1}, g^{b+r_2})$
\item if $A()$ successds, $y = g^{(a+r_1)(b+r_2)}$  $= g^{ab}{g^b}^{r_1}{g^a}^{r_2}g^{r_1r_2}$
\item compute $g^{ab} = \frac{y}{{(g^b)}^{r_1} {(g^a)}^{r_2} g^{r_1r_2}}$
\item Repeat $t = 2 \epsilon^{-1}\log \delta^{-1}$ times:
\end{itemize}

From the above, choose the value computed the majority of times.

\begin{equation*}
\begin{split}
\Pr(B(g^a, g^b) \neq g^{ab}) & = \Pr(A \text{ fails at least t/2 times }) \\
	& \leq [\Pr( A \text{ fails }) ]^{t/2} < (1-\epsilon)^{t/2} < \delta
\end{split}
\end{equation*}
\end{enumerate}

\end{document}