\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\input{texdefs}

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf CS195-7: Introduction to Cryptography} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\ho}[4]{\handout{#1}{#2}{Instructor:
#3}{}{Handout #1: #4}}

\newcommand{\solution}[1]{#1}

\begin{document}
\handout{PS5}{DUE: October 10, 2002}{Instructor: Anna Lysyanskaya}
{\solution{*** Your name here *** }}{Midterm Exam}

\noindent
Please note that you are not allowed to collaborate with others
on this exam.

\section*{Problem 1:  One-way functions and permutations}

Let $f~:~\{0,1\}^* \mapsto \{0,1\}^*$ be a one-way function.
Let $p~:~\{0,1\}^* \mapsto \{0,1\}^*$ be a
one-way permutation.  

For each of the suggested implications below, prove or
disprove that they are valid.  That is to say, if an implication is
valid, give a reduction.  If it is not valid,
give an example of a one-way function $f$ and a
one-way permutation $p$ for which the implication is false.  
You
may assume existence of one-way functions 
permutations.  

Problem 2 from Problem Set 2 may serve as a helpful hint for 
a couple of these problems.

{\bf Example.}  Does it follow that $f(x)$ is a permutation?

{\bf Solution.}  It does not.  Let $f'(x)$ be a one-way
function.  Let $f(x) = g(x)$ where $g(x)$ is as defined in
Problem 2a of problem set 2.  Then $f(x)$ is a one-way
function (that's what is shown in that problem) but it
cannot be a permutation because it ignores half of its input
bits.

\medskip

{\bf (a)} Does it follow that $g(x) = f(f(x))$ is a one-way function?

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}

{\bf (b)} Does it follow that  $g(x) = p(p(x))$ is a one-way permutation?

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}

{\bf (c)} Does it follow that  $g(x) = f(x)\circ p(x)$ is 
a one-way function? (Recall that $\circ$ denotes concatenation.)

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}

{\bf (d)}  Does it follow that, on input $p(x)$,
one can efficiently compute $f(x)$?

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}


\section*{Problem 2: The Blum-Rabin trapdoor permutation}

Recall the definition of a family of trapdoor permutations.  
A trapdoor permutation family
consists of algorithms $(G, M_{\pk}, f_{\pk}, f_{\pk}^{-1})$.
$G$ generates a member of the family, that is to say, a public
key $\pk$ that allows to efficiently evaluate the permutation $f_{\pk}$,
and the secret key $\sk$ that allows to efficiently invert $f_{\pk}$.
$M_{\pk}$ is the algorithm that efficiently samples
the domain of the permutation $f_{\pk}$.  

For example, in RSA, the procedure $G$ 
generates the modulus $n=pq$ and the exponent $e$, and sets
$\pk = (n,e)$ and $\sk = d$, where $de \equiv 1 \bmod \phi(n)$.
Furthermore, $M_{(n,e)} = \Zns$,  $f_{(n,e)}(x) = x^e \bmod n$,
and $f^{-1}_{(n,e)}(y) = y^d \bmod n$.

$(G, M_{\pk}, f_{\pk}, f^{-1}_{\pk})$ constitute a trapdoor permutation 
if $f_{\pk}$ is hard to invert.  More formally, for all
probabilistic polynomial-time adversaries $\{A_k\}$, there
exists a negligible function $\nu(k)$ such that

$$\Pr[(\pk,\sk)\leftarrow G(1^k); y \leftarrow M_{\pk}; 
x \leftarrow A_k(y)~:~f_{\pk}(x) = y] = \nu(k)$$

Consider the following collection of algorithms:

\begin{description}
\item[Key generation]  The procedure $G(1^k)$ generates two 
$k$-bit primes, $p$ and $q$, such that $p \equiv q \equiv 3 \bmod 4$.
It outputs $\pk = n = pq$, and $\sk=(p,q)$.  (Such a modulus
$n$ is called a {\em Blum integer}.)

\item[Domain]  The domain $M_n$ of the permutation $f_n$ consists of all
the quadratic residues modulo $n$.  More formally,
$$M_n = \{ x~\mid x \in \Zns \wedge \exists u \mbox{ such that } x \equiv u^2 \bmod n\}$$  To sample from the domain,
pick $u \leftarrow \Zns$, and output $x = u^2 \bmod n$.

\item[Computing the function]  The permutation $f_n$ is squaring:
$f_n(x) = x^2 \bmod n$.

\item[Inverting the function] To compute $f^{-1}_n(y)$, one must compute the 
value $x \in M_n$ such that $x^2 = y \bmod n$.
\end{description}

In this problem, you will prove that the algorithms given above
constitute a family of trapdoor permutations.

{\bf (a)}  Show that $f_n$ is a permutation.  (Hint: work modulo $p$ and
$q$ first, and then combine using the Chinese remainder theorem.)

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}

{\bf (b)}  Suppose that $p = 4m+3$ is a prime and that $a$ is a
quadratic residue modulo $p$. Prove that $a^{m+1}$ is a square
root of $a$ modulo $p$.  

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}

{\bf (c)}  Devise an efficient algorithm that, on input $(p,q,y)$,
computes $x = f^{-1}_{pq}(y)$, i.e., $x$ such that $x^2 = y \bmod n$,
where $n=pq$ is a Blum integer.

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}

{\bf (d)}  Devise an efficient algorithm that,
on input $(n,a,b)$, where $a, b \in \Zns$, $a\neq \pm b \bmod n$, 
and $a^2 \equiv b^2 \bmod n$, outputs a non-trivial divisor of $n$.

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}

{\bf (e)}  Let us assume that factoring Blum integers is infeasible.
More precisely, assume that for all probabilistic polynomial-time
adversaries $\{A_k\}$, there exists a negligible function
$\nu(k)$ such that

$$\Pr[(n, (p,q)) \leftarrow G(1^k); p \leftarrow A_k(n)~:~p\mid n \wedge 1<p<n] = \nu(k)$$

Show that under this assumption, it is infeasible to invert $f_n$.
More precisely, show that for all probabilistic polynomial-time
adversaries $\{A_k\}$, there exists a negligible funtion $\nu'(k)$ 
such that

$$\Pr[(n, (p,q))\leftarrow G(1^k);  y \leftarrow M_n;
x \leftarrow A_k(n)~:~x^2 = y \bmod n] = \nu'(k)$$

(This fact is due to Michael Rabin.)

\medskip 
\solution{
{\bf Solution:} \bigskip \noindent

***************** INSERT SOLUTION HERE ***************
}
\end{document}

