\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 7.}
\author{Boaz Barak}
\date{Total of 140 points. Due March 31, 2010.}
\begin{document}
\maketitle
For this exercise, let us say that $\{ f_e \}$ is collection of trapdoor permutations if for every $e\in\bits^n$, $f_e$
is a permutation of $\bits^n$, there is a polynomial-time algorithm $G$ that on input $1^n$ outputs a pair $(e,d)$ such
that the maps $(x,e) \mapsto f_e(x)$ and $(y,d) \mapsto f_e^{-1}(y)$ can be computed in polynomial time, and for every
polynomial-time $A$ there is a negligible function $\e$ such that
\[
\Pr_{\substack{(e,d)\getsr G(1^n) \\ x \getsr \bits^n}}\bigl[ A(1^n,e,f(x)) = x \bigr] < \e(n)
\]
(This is a slight strengthening of the definition of trapdoor functions we saw in class and is in the Boneh-Shoup book,
made mostly for simplicity.)
\begin{exercise}[30 points] \label{ex:tdp} Consider 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 \bits^n$, 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, where the definition of CPA secure public key encryption scheme is the same as the definition of CPA-security
for private key schemes, except that the adversary gets the public key $e$.
\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}[20 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}[20 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 Give a polynomial-time algorithm to invert $f$ (assuming that $p,q$ are known). That is, give a
$\poly(\log(p)+\log(q))$-time algorithm that on input $p,q$ and $(x',x'')\in Z_p \times Z_q $ outputs $x \in
\{1..pq\}$ such that $x' = x \pmod{p}$ and $x'' = x \pmod{q}$. See footnote for hint.\footnote{\textbf{Hint:}
\tiny Use the gcd algorithm to find integers $\alpha,\beta$ such that $\alpha p +\beta q=1$. Use this to
invert $f$ on the inputs $(1,0)$ and $(0,1)$ and proceed using linearity.}
\item Prove that $|Z^*_n|=(p-1)\cdot(q-1)$, and 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}$.
\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}
\begin{exercise}[20 bonus points + 10 extra bonus points]
Prove that the following algorithm outputs a random number $R$ in $\{1..N\}$ together with $R$'s factorization:
\begin{enumerate}
\item \label{step:1} Generate a random decreasing sequence $N \geq S_1 \geq \cdots \geq S_{\ell} = 1$, by
choosing $S_1$ at random in $\{1..N\}$, $S_2$ at random in $\{1..S_1 \}$ and so on until reaching $1$.
\item \label{step:2} Let $( P_1,\ldots, P_{\ell'} )$ denote the $S_i$'s in this sequence that are \emph{prime},
and let $R = P_1 \cdots P_{\ell'}$. If $R \leq N$ then with probability $R/N$ output $R$ together with its
factorization $( P_1,\ldots, P_{\ell'} )$.
\item If we did not output a number in Step~\ref{step:2}, go back to Step~\ref{step:1}.
\end{enumerate}
You need to prove that (a) conditioned on outputting a number $R$, $R$ will be distributed uniformly in $\{1.. N\}$ and
(b) that the algorithm runs in time $\poly(\log N)$. Both follow by showing that for every $R \in \{1..N\}$, the
probability that $R$ is output in one iteration of the algorithm in Step~\ref{step:2} is $(1/N)\prod_{P\leq N}(1-1/P)$
(note that this product is over all $P \leq N$, and not just $P$ that divides $N$). You can use the fact that
$\prod_{P\leq N}(1-1/P) \geq \Omega(1/\log N)$ (or for 10 extra points prove it by using the method from the lecture
notes to bound $\sum_{P \leq N}\log P$). See footnote for hint\footnote{\textbf{Hint:} \tiny Think of the random number
$S_1$ as chosen as follows: we output $N$ with probability $1/N$, otherwise we output $N-1$ with probability $1/(N-1)$,
otherwise we output $N-2$ with probability $1/(N-2)$, etc..}
The algorithm of this exercise is due to Adam Kalai, although please do not look at his paper until after you have
completed the exercise on your own.
\end{exercise}
BTW a clarification - there is really no difference between bonus points and ``plain'' points. I designate some
questions as bonus when they are harder or a bit tangential to the course. I also always make sure that you can earn
100 points for the home work without doing the bonus questions. Thus I suggest that you work on the other questions
first, and tackle the bonus questions later.
\end{document}