\documentstyle[11pt,twoside]{article}

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


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

\begin{document}

\courseheader

\bigskip
\begin{center}
{\Large{\bf Problem Session 4}}
\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$. 
\item Is that enough to say that the scheme is secure? 
\end{enumerate}


\bigskip
{\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))$
\item $G''(s)=G_1(s).G(G_2(s))$

\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. 

\bigskip
{\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}$? 
\item 
Is the Diffie Hellman key uniformly distributed over all possible
keys in $Z_p^*$?  
\end{enumerate}


\bigskip
{\bf Problem 4.4: Hardness on Average}

In this problem we will prove that if the RSA function 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$).

\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$)
  
\end{enumerate}

\end{document}