\documentclass[11pt,twoside]{book}

\usepackage[dvips]{graphics}

\def\book{1}

%
% defs.tex  - [Bellare, Rogaway] book macros
%

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

\DeclareMathAlphabet{\mathsl}{OT1}{cmr}{m}{sl}

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

% Page styles

\setlength{\evensidemargin}{0.5in}
\setlength{\oddsidemargin}{0.5in}
\setlength{\textwidth}{5.5in}
\setlength{\textheight}{8.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0.2in}
\setlength{\headsep}{0.75in}
\setlength{\footskip}{0.75in}

\renewcommand{\topfraction}{1}
\renewcommand{\bottomfraction}{1}
\renewcommand{\textfraction}{0}


\renewcommand{\baselinestretch}{1}
\renewcommand{\arraystretch}{1.2}

\setlength{\fboxsep}{10pt}


\newlength{\saveparindent}
\setlength{\saveparindent}{\parindent}
\newlength{\saveparskip}
\setlength{\saveparskip}{\parskip}


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

% Theorem environments


\ifnum\book=0
\newtheorem{thm}{Theorem}[section]
\else
\newtheorem{thm}{Theorem}[chapter]
\newtheorem{quest}{Problem}[chapter]
\newtheorem{exo}{Exercise}[chapter]
\newtheorem{questt}{Problem}[chapter]
\fi
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{propo}[thm]{Proposition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{assm}[thm]{Assumption}
\newtheorem{clm}[thm]{Claim}
\newtheorem{rem}[thm]{Remark}
\newtheorem{examp}[thm]{Example}
\newtheorem{fct}[thm]{Fact}
\newtheorem{sch}[thm]{Scheme}


\newenvironment{theorem}{\begin{thm}\begin{em}}%
{\end{em}~\qedsym\end{thm}}

\newenvironment{problem}{\begin{quest}\begin{rm}}
{\end{rm}\end{quest}}
\newenvironment{exercise}{\begin{exo}\begin{rm}}%
{\end{rm}\end{exo}}

\newenvironment{question}{\begin{questt}\begin{rm}}%
{\end{rm}\end{questt}\hrulefill}
\newenvironment{lemma}{\begin{lem}\begin{em}}%
{\end{em}~\qedsym\end{lem}}
\newenvironment{corollary}{\begin{cor}\begin{em}}%
{\end{em}~\qedsym\end{cor}}
\newenvironment{proposition}{\begin{propo}\begin{em}}%
{\end{em}~\qedsym\end{propo}}
\newenvironment{definition}{\begin{defn}\begin{em}}%
{\end{em}~\qedsym\end{defn}}
\newenvironment{assumption}{\begin{assm}\begin{em}}%
{\end{em}~\qedsym\end{assm}}
\newenvironment{claim}{\begin{clm}\begin{em}}%
{\end{em}~\qedsym\end{clm}}
\newenvironment{remark}{\begin{rem}\begin{em}}%
{\end{em}~\qedsym\end{rem}}
\newenvironment{example}{\begin{examp}\begin{em}}%
{\end{em}~\qedsym\end{examp}}
\newenvironment{fact}{\begin{fct}\begin{em}}%
{\end{em}~\qedsym\end{fct}}
\newenvironment{scheme}{\begin{sch}\begin{em}}%
{\end{em}~\qedsym\end{sch}}

\newcommand{\chapref}[1]{\mbox{Chapter~\ref{#1}}}
\newcommand{\secref}[1]{\mbox{Section~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Appendix~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Theorem~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definition~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corollary~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lemma~\ref{#1}}}
\newcommand{\clref}[1]{\mbox{Claim~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposition~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figure~\ref{#1}}}
\newcommand{\eqref}[1]{\mbox{Equation~(\ref{#1})}}
\newcommand{\egref}[1]{\mbox{Example~\ref{#1}}}
\newcommand{\schref}[1]{\mbox{Scheme~\ref{#1}}}
\newcommand{\factref}[1]{\mbox{Fact~\ref{#1}}}
\newcommand{\remref}[1]{\mbox{Remark~\ref{#1}}}
\newcommand{\probref}[1]{\mbox{Problem~\ref{#1}}}

% deluxe proof environment
\def\qsym{\vrule width0.6ex height1em depth0ex}
\newcount\proofqeded
\newcount\proofended
\def\qedsym{{\hspace{0pt}\rule[-1pt]{3pt}{9pt}}}
\def\qed{\qedsym
\end{rm}\addtolength{\parskip}{-5pt}
\setlength{\parindent}{\saveparindent}
\global\advance\proofqeded by 1 }
\newenvironment{proof}%
 {\proofstart}%
 {\ifnum\proofqeded=\proofended\qed\fi \global\advance\proofended by 1
  \medskip}
\makeatletter
\def\proofstart{\@ifnextchar[{\@oprf}{\@nprf}}
\def\@oprf[#1]{\begin{rm}\protect\vspace{5pt}\noindent{\bf Proof of #1:\
}%
\addtolength{\parskip}{5pt}\setlength{\parindent}{0pt}}
\def\@nprf{\begin{rm}\protect\vspace{5pt}\noindent{\bf Proof:\ }%
\addtolength{\parskip}{5pt}\setlength{\parindent}{0pt}}
\makeatother



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

% General


\setlength{\jot}{6pt}
\newlength{\savejot}
\setlength{\savejot}{\jot}

\newenvironment{newmath}{\begin{displaymath}%
\setlength{\abovedisplayskip}{5pt}%
\setlength{\belowdisplayskip}{5pt}%
\setlength{\abovedisplayshortskip}{3pt}%
\setlength{\belowdisplayshortskip}{3pt} }{\end{displaymath}}

\newenvironment{newequation}{\begin{equation}%
\setlength{\abovedisplayskip}{5pt}%
\setlength{\belowdisplayskip}{5pt}%
\setlength{\abovedisplayshortskip}{3pt}%
\setlength{\belowdisplayshortskip}{3pt} }{\end{equation}}

\newcommand{\E}[1]{\mathbf{E}\left[#1\right]}
\newcommand{\EE}[1]{\mathbf{E}\left[#1\right]}
\newcommand{\Var}[1]{\mathbf{Var}\left(#1\right)}
\newcommand{\SD}[1]{{\sigma}_{#1}}
\newcommand{\probsym}{{\Pr}}
\newcommand{\Prob}[1]{\probsym\left[{#1}\right]}
\newcommand{\CondProb}[2]{\probsym\left[{#1}\left|\right.#2\right]}

\newcommand{\Probb}[2]{\probsym_{#1}\left[{#2}\right]}
\newcommand{\ProbExp}[2]{\probsym\left[\:{#2}\::\:{#1}\:\right]}   

\newcommand{\probexp}[2]{\probsym\left[\:{#1}\::\:{#2}\:\right]}
\newcommand{\CondProbb}[3]{\probsym_{#1}\left[{#2}\left|\right.#3\right]}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil}[1]{\lceil{#1}\rceil}

\setcounter{tocdepth}{1}

\begin{document}

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

\title{Introduction to Modern Cryptography}

\author{\textbf{Mihir Bellare}\thanks{\ 
Department of Computer Science and Engineering,
University of California at San Diego,
La Jolla, CA 92093, USA.  mihir@cs.ucsd.edu, http://www-cse.ucsd.edu/users/mihir}
\and
\textbf{Phillip Rogaway}\thanks{\
Department of Computer Science,
University of California at Davis,
Davis, CA 95616, USA. rogaway@cs.ucdavis.edu, http://www.cs.ucdavis.edu/$\sim$rogaway
}\vspace{0.3in}}

\date{\today}


\maketitle

\section*{Preface}

\vspace{0.3in}

This is a set of class notes that we have been developing jointly for some
years.  We use them for the graduate cryptography courses that we teach at our
respective institutions. Each time one of us teaches the class, he takes the
token and updates the notes a bit.  This is an evolving document, and there are
still lots of gaps, as well as plenty of ``unharmonized'' portions of the notes
as they evolved in random ways.

The viewpoint taken throughout these notes is to emphasize the \textit{theory
of cryptography as it can be applied to practice.}  This is an approach that
the two of us have pursued in our research, and it seems to be a pedagogically
desirable approach as well.

We would like to thank the following students of past versions of our courses
who have pointed out errors and made suggestions for changes: Andre Barroso,
Keith Bell, Alexandra Boldyreva, Michael Burton, Chris Calabro, Sashka Davis,
Alex Gantman, Bradley Huffaker, Chanathip Namprempre, Adriana Palacio, Wenjing
Rao, Fritz Schneider.  We welcome further corrections, comments and
suggestions.

\vspace{0.7in}

\noindent \textbf{Mihir Bellare} \hfill San Diego, California USA

\noindent \textbf{Phillip Rogaway} \hfill Davis, California USA

\vspace{0.7in}

\noindent \copyright Mihir Bellare and Phillip Rogaway, 1997--2002.

\newpage
\tableofcontents
\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\appendix

\chapter{The Birthday Problem}         \label{ap-birthday} 

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


The materiel in this appendix is from \cite{bkr}.

The setting is that we have $q$ balls. View them as numbered, $1,\ldots,q$.  We
also have $N$ bins, where $N\geq q$. We throw the balls at random into the
bins, one by one, beginning with ball~1. At random means that each ball is
equally likely to land in any of the $N$ bins, and the probabilities for 
all the balls are independent. A collision is said to occur if some bin
ends up containing at least two balls. We are interested in $C(N,q)$, 
the probability of a collision.

The birthday paradox is the case where $N=365$. We are asking what is the
chance that, in a group of $q$ people, there are two people with the same
birthday, assuming birthdays are randomly and independently distributed
over the days of the year. It turns out that when $q$ hits $\sqrt{365}$
the chance of a birthday collision is already quite high, around $1/2$.

This fact can seem surprising when first heard.  The reason it is true is that
the collision probability $C(N,q)$ grows roughly proportional to $q^2/N$. This
is the fact to remember. The following gives a more exact rendering, providing
both upper and lower bounds on this probability.

\begin{proposition}\label{fc-bday} Let $C(N,q)$ denote the probability of at 
least one collision when we throw $q\geq 1$ balls at random into $N\geq q$
buckets.  Then
\begin{eqnarray*}
     C(N,q) & \leq & \frac{q(q-1)}{2N} \;.
\end{eqnarray*}
Also
\begin{eqnarray*}
     C(N,q) & \geq & 1- e^{-q(q-1)/2N} \;,
\end{eqnarray*}
and 
\begin{eqnarray*}
 C(N,q) & \geq & 0.3 \cdot \frac{q(q-1)}{N} \;
\end{eqnarray*}
for $1\leq q\leq\sqrt{2N}$.
\end{proposition} 

In the proof we will find the following inequalities useful to make estimates.

\begin{proposition} The inequality
\begin{newmath}
    \left(1-\frac{1}{e}\right)\cdot x \:\leq\:
     1 - e^{-x} \:\leq\:  x \;.
\end{newmath}%
is true for any real number $x$ with $0\leq x\leq 1$.
\end{proposition}

\begin{proof}[\propref{fc-bday}] Let $C_i$ be the event that the $i$-th 
ball collides with one of the previous ones. Then $\Prob{C_i}$ is at most
$(i-1)/N$, since when the $i$-th ball is thrown in, there are at most $i-1$
different occupied slots and the $i$-th ball is equally likely to land in any
of them. Now
\begin{eqnarray*}
C(N,q) & = & \Prob{C_1\vee C_2\vee\cdots\vee C_q} \\
 & \leq & \Prob{C_1} + \Prob{C_2} + \cdots + \Prob{C_q} \\
 & \leq & \frac{0}{N} + \frac{1}{N} + \cdots + \frac{q-1}{N} \\
 & = &  \frac{q(q-1)}{2N} \;.
\end{eqnarray*}
This proves the upper bound.  For the lower bound we let $D_i$ be the event
that there is no collision after having thrown in the $i$-th ball. If there is
no collision after throwing in $i$ balls then they must all be occupying
different slots, so the probability of no collision upon throwing in the
$(i+1)$-st ball is exactly $(N-i)/N$. That is,
\begin{newmath}
 \CondProb{D_{i+1}}{D_{i}} \: = \: \frac{N-i}{N} \: = \: 1-\frac{i}{N} \;.
\end{newmath}%
Also note $\Prob{D_1}=1$. The probability of no collision at the end of the
game can now be computed via
\begin{eqnarray*}
 1 - C(N,q) & = & \Prob{D_q} \\
   & = & \CondProb{D_q}{D_{q-1}}\cdot\Prob{D_{q-1}} \\
    &  \vdots & \vdots \\
 & = & \prod_{i=1}^{q-1} \CondProb{D_{i+1}}{D_{i}} \\
 & = & \prod_{i=1}^{q-1} \left(1-\frac{i}{N}\right) \;.
\end{eqnarray*}
Note that $i/N\leq 1$. So we can use the inequality $1-x\leq e^{-x}$ for each
term of the above expression. This means the above is not more than
\begin{newmath}
 \prod_{i=1}^{q-1} e^{-i/N} \: = \:
 e^{-1/N-2/N-\cdots-(q-1)/N} \: = \:
 e^{-q(q-1)/2N} \;.
\end{newmath}%
Putting all this together we get 
\begin{newmath}
 C(N,q) \:\geq \: 1- e^{-q(q-1)/2N} \;, \protect\vspace{3pt}
\end{newmath}%
which is the second inequality in \propref{fc-bday}. To get the last one, we
need to make some more estimates. We know $q(q-1)/2N\leq 1$ because $q\leq
\sqrt{2N}$, so we can use the inequality $1-e^{-x}\geq (1-e^{-1})x$ to get
\begin{newmath}
 C(N,q) \:\geq \: \left(1-\frac{1}{e}\right)\cdot \frac{q(q-1)}{2N} \;.
\end{newmath}%
A computation of the constant here completes the proof.
\end{proof}




\begin{thebibliography}{LLL}

\bibitem{bkr} {\sc M.~Bellare, J.~Kilian and P. Rogaway.} The security of the
cipher block chaining message authentication code.  \textsl{Journal of Computer
and System Sciences} , Vol.~61, No.~3, Dec 2000, pp.~362--399. 

\end{thebibliography}

\end{document}

