\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
\newif\ifpdf
\ifx\pdfoutput\undefined \else
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\else
\pdftrue
\fi
\fi
\fi
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\def\class{0}
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\GF}{\mathsf{GF}}
\newcommand{\maxpr}{\text{\rm max-pr}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\PH}{\cclass{PH}}
\newcommand{\coNP}{\cclass{coNP}}
\newcommand{\AvgP}{\cclass{AvgP}}
\newcommand{\DTIME}{\cclass{DTIME}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\BQP}{\cclass{BQP}}
\newcommand{\NTIME}{\cclass{NTIME}}
\newcommand{\SIZE}{\cclass{SIZE}}
\newcommand{\Ppoly}{\cclass{P_{/poly}}}
\newcommand{\SPACE}{\cclass{SPACE}}
\newcommand{\PSPACE}{\cclass{PSPACE}}
\newcommand{\BPL}{\cclass{BPL}}
\newenvironment{summary}{\begin{quote}\textbf{Summary.}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}[theorem]
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\sstart}{\triangleright}
\newcommand{\send}{\triangleleft}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{3SAT}}}
\newcommand{\IS}{\mathsf{INDSET}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\inp}{\mathsf{in}}
\newcommand{\outp}{\mathsf{out}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Supp}{\mathsf{Supp}}
\newcommand{\dist}{\Delta}
\newcommand{\indist}{\approx}
\newcommand{\PRG}{\mathsf{G}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\Com}{\mathsf{Com}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\eqdef}{\stackrel{\text{\tiny def}}{=}}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
\newcommand{\qstart}{q_{\text{\tiny start}}}
\newcommand{\qacc}{q_{\text{\tiny acc}}}
\newcommand{\qrej}{q_{\text{\tiny rej}}}
\newcommand{\csp}{\mathsf{CSP}}
\newcommand{\ared}{\text{\tt alph-red}}
\newcommand{\qred}{\text{\tt q-red}}
\newcommand{\dred}{\text{\tt deg-red}}
\newcommand{\amp}{\text{\tt gap-amp}}
\newcommand{\LC}{\mathcal{LC}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\pmo}{\{\pm 1\}}
\newcommand{\set}[1]{\{ #1 \}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 433 --- Cryptography --- Homework 6.}
\author{Boaz Barak}
\date{Total of 150 points. Due November 8th, 2007.}
\begin{document}
\maketitle
\noindent\textbf{Note:} You have two weeks to solve this
exercise and it also has many bonus points. So this is a good
chance to make up for lost points in past or future exercises.
However, note that all proofs and reductions must be rigorous---
written clearly and precisely, and without any logical gaps. Try
to ensure that a reader will be able to easily follow your line
of reasoning, and will be absolutely convinced in your proof's
validity. You will not receive credit for proofs that are
written in a confusing, vague, or incomplete fashion.
\begin{exercise}[30 points] In this question we complete and formalize the proof of the
Chinese Reminder Theorem.
\begin{enumerate}
\item Let $G_1,G_2$ be abelian groups where $+_i$ is the
group operation of $G_i$. We define the \emph{direct
product} $G\eqdef G_1 \times G_2$, which consists of all
pairs $(a_1,a_2)$ where $a_i\in G_i$. We can view $G$ in
a natural way as an abelian group if we define the group
operation $+_G$ component-wise:
$(a_1,a_2)+_G(b_1,b_2)=(a_1+_1 b_1,a_2+_k b_2)$. Prove
that $G$ is indeed an abelian group with respect to
$+_G$.
\item A \emph{group homomorphism} is a function $f$ from an
abelian group $G$ to an abelian group $H$ that preserves
the group operation; i.e., $f(a)+_H f(b) = f(a +_G b)$
for all $a,b\in G$. Let $n=p\cdot q$ where
$\gcd(p,q)=1$. Let $f$ be a mapping from $Z_n$ to
$Z_{p}\times Z_{q}$ such that $f(x)=(x \mod p, x \mod
q)$. Show that $f$ is a group homomorphism.
\item Show that $f(x)\in Z^*_{p}\times Z^*_{q}$ if and only
if $x\in Z^*_n$.
\item By the previous question, $f$ can be viewed as a
mapping from $Z^*_n$ to $Z^*_{p}\times Z^*_{q}$. Show
that in this case $f$ is also a group homomorphism.
\item Consider the following algorithm for inverting $f$.
(Assume that $p,q$ are known.)
\begin{itemize}
\item Input: $(x_p,x_q)\in Z_p \times Z_q $.
\item Use Euclid's algorithm to find integers
$\alpha,\beta$ such that $\alpha p +\beta q=1$.
\item Set $1_p= \alpha q \mod n$ and $1_q= \beta p
\mod n$.
\item Compute $x= (x_p \cdot 1_p + x_q\cdot 1_q) \mod
n$
\end{itemize}
Prove that the algorithm inverts $f$, namely, $x\mod p=x_p$
and $x\mod q =x_q$.
\item Conclude that $f$ is an isomorphism from $Z^*_n$ to
$Z^*_{p}\times Z^*_{q}$ as well as from $Z_n$ to
$Z_{p}\times Z_{q}$. You might want to use the following
fact (that we proved in class):
$|Z^*_n|=(p-1)\cdot(q-1)$.
\item Read your answers to the previous questions. Where did
you use the fact that $p$ and $q$ are primes? Is it
possible to prove these results under a weaker
condition?
\end{enumerate}
\end{exercise}
\begin{exercise}[20 points]
\begin{enumerate}
\item We say that a number $y\in Z^*_n$ is a Quadratic
Residue (QR) if $y=x^2$ for some $x\in Z^*_n$. (We
refer to $x$ as a sqrt of $y$.) Prove that the set of
QRs is a subgroup of $Z^*_n$.
\item Let $p>1$ be a prime number. It can be shown that
$Z^*_p$ is a cyclic group, that is there exists a
generator $g\in Z^*_p$ such that
$Z^*_p=\{g^1,\ldots,g^(p-1)\}$. For $y\in Z*_p$ we let
$\log_g (y)$ to denote the smallest non-negative integer
$i$ for which $g^i=y$. For example $\log_g (1)=0$ and
$\log_g (g)=1$. (Note that $0\geq \log_g (y) \geq p-1$.)
Show that $y$ is a QR in $Z*_p$ if and only $\log_g (y)$
is an even number.
% \item Let $y$ be a QR in $Z^*_p$. Show that $y$ has
% exactly two distinct roots.
%
% \item Let $p$ be a prime of the form $p=4t+3$. Suppose
% that $y$ is a QR. Prove that $y^{t+1}$ is a sqrt of
% $y$. Can you find the other sqrt of $y$? We remark
% that there exists an efficient probabilistic algorithm
% that extracts sqrt when the prime $p$ is of the form
% $p=4t+1$, hence sqrt can be performed efficiently when
% the modulus is prime.
%
% \item Let $n=pq$ where $p$ and $q$ are primes. How many
% QRs are there in $Z^*_n$? How many sqrts does a QR
% $y\in Z^*_n$ have? Show how to efficiently extract
% sqrts when $p,q$ are known. (You can rely on the
% algorithm that was mentioned in the previous question.
\end{enumerate}
\end{exercise}
\begin{exercise}[30 points] \label{ex:tdp} In class we saw the following public key
encryption scheme based on any family of trapdoor permutations
$\{ f_e \}$.
\begin{description}
\item[Key generation] Choose $(e,d) \getsr \Gen(1^n)$
where $\Gen$ is the generator for the trapdoor
permutation family $\{ f_e \}$.
\item[Encryption] To encrypt a bit $b\getsr \bits$ using
the key $e$: choose $x \getsr S_e$, choose $r \getsr
\bits^n$, and output $f_e(x),r, \iprod{x,r} \oplus
b$.
\item[Decryption] To decrypt the message $(y,r,c)$ using
$d$: compute $x = f_e^{-1}(y)$ and output
$\iprod{x,r} \oplus c$.
\end{description}
Prove that if $\{ f_e \}$ is a trapdoor permutation collection,
the above scheme is a CPA secure public key encryption scheme.
\end{exercise}
\begin{exercise}[25 points] We can define \emph{chosen ciphertext security}
for public key encryption schemes in the same way that we
defined them for private key encryption schemes: the adversary
gets access to a decryption box before the challenge and after
receiving the challenge ciphertext $y^*$ is allowed to query the
box on every string $y$ \emph{except} for $y^*$. The only
difference is that the adversary gets initially the encryption
key as another input. As usual we say the scheme is secure
against Chosen Ciphertext Attack (CCA secure for short) if no
poly-time adversary can win with $1/2+\e(n)$ probability where
$\e$ is poly-bounded.
\begin{enumerate}
\item Show that every public key encryption that is built from a
trapdoor permutation family as in Exercise~\ref{ex:tdp} (when we encrypt an $n$
bit message by encrypting each bit individually) is
\emph{not} CCA secure. See footnote for hint\footnote{\textbf{Hint:} \tiny Show that
every encryption scheme that works in a bit-by-bit fashion is not CCA secure. }
\item Show that the specific encryption scheme based on Rabin's
trapdoor permutation family has an even more devastating
attack: show that given access to a decryption box for this scheme a
polynomial-time adversary can recover the \emph{private key}
with high probability using only a constant number of
queries.
\end{enumerate}
\end{exercise}
\begin{exercise}[25 points] As mentioned in class, the way to generate a random
$n$-bit prime, is to pick a random $n$-bit number and test it
for primality. Thus we need a polynomial-time primality
algorithm. We now describe such an algorithm. We assume that we
have a polynomial-time algorithm \texttt{SQRT} that on input a
pair $y,N$ such that $N$ is prime and $y$ is a quadratic residue
modulo $N$, outputs a square-root of $y$ modulo $N$ (i.e., a
number $x$ such that $x^2 = y \pmod{N}$). We saw in class such
an algorithm for the case that $N= 4K+3$ for some $K$, and in
the KL book Section 11.2.1 you can see its extension for the
case that $N$ is a prime of the form $N=4K+1$. We stress that we
make no assumption on the algorithm's output if $x$ and $N$ are
not of this form. However, by stopping the algorithm if it runs
for too much time, we can assume that it always stops in
polynomial-time and outputs some number between $1$ and $N-1$.
Consider the following algorithm:
\noindent\textbf{Algorithm} \texttt{PTEST}. On input $N$ do:
\begin{enumerate}
\item If $N$ is even or $N=C^k$ for some $k \in \{1,\ldots,
\log N \}$ then output \texttt{`composite'} and halt.
\item Pick $x \getsr \{1,\ldots,N-1\}$.
\item If $gcd(x,N) \neq 1$ output \texttt{`composite'} and
halt.
\item Compute $y = x^2 \pmod{N}$ and $w =
\texttt{SQRT}(y,N)$.
\item If $w^2 = y \pmod{N}$ and $y=x \pmod{N}$ or $y=-x
\pmod{N}$ then output \texttt{`prime'} and halt. Otherwise
output \texttt{`composite'}.
\end{enumerate}
Prove that for every positive integer $N$, Algorithm
\texttt{PTEST} runs on input $N$ in $\poly(\log N)$-time and
\begin{enumerate}
\item If $N$ is prime then \texttt{PTEST}$(N)$ outputs
\texttt{`prime'} with probability $1$.
\item If $N$ is composite then \texttt{PTEST}$(N)$ outputs
\texttt{`composite'} with probability $\geq 1/10$.
\end{enumerate}
\end{exercise}
\begin{exercise}[20 points] Suppose that the RSA Assumption fails
``somewhat'' on a particular composite number $N$ and $e$ with
$gcd(e,\varphi(N))=1$, in the sense that there is a $T$-time
algorithm $A$ such that
\[
\Pr_{y \getsr \Z^*_N}[ A(y)= x \text{ s.t. } x^e =y \pmod{N} ] >
0.01
\]
Show that there is a $100(\log N)^{100} \cdot T$-time algorithm
$B$ that breaks the RSA Assumption completely for $N,e$ in the
sense that
\[
\Pr_{y \getsr \Z^*_N}[ A(y)= x \text{ s.t. } x^e =y \pmod{N} ] >
0.99
\]
See footnote for hint\footnote{\textbf{Hint:} \tiny Use the fact
that $y^{1/e}r = (yr)^{1/e} \pmod{N}$ for every $r \in \Z^*_N$.}
\end{exercise}
\end{document}