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

% Page styles

\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0.2in}
\setlength{\headsep}{0.55in}
\setlength{\footskip}{0.55in}
\renewcommand{\baselinestretch}{1}
\renewcommand{\arraystretch}{1.2}

\setlength{\fboxsep}{10pt}
\setcounter{tocdepth}{2}

\setlength{\parskip}{5pt}
\setlength{\parindent}{0pt}

\newlength{\saveparindent}
\setlength{\saveparindent}{\parindent}
\newlength{\saveparskip}
\setlength{\saveparskip}{\parskip}
\pagestyle{myheadings}
\markboth{{\protect\small\rm {6.87s: \handoutname}}}%
{{\protect\small\rm Goldwasser and Bellare}}

\def\blankpage{\newpage\thispagestyle{empty}\mbox{ }}

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


%
% For references. Long form
% Adaptation and extension of stuff by Richard Beigel and Nick Reingold.
% Last updated: Mihir (Aug 96)
%

\newif\ifshortconferences
\shortconferencesfalse

\def\ending#1{{\count1=#1\relax
% mod out by 100 first
\count2=\count1
\divide\count2 by 100
\multiply\count2 by 100
\advance\count1 by -\count2
%
\ifnum\count1=11
th%
\else \ifnum\count1=12
th%
\else \ifnum\count1=13
th%
\else
\count2=\count1
\divide\count1 by 10
\multiply\count1 by 10
\advance\count2 by -\count1
\ifnum\count2=1
st%
\else \ifnum\count2=2
nd%
\else \ifnum\count2=3
rd%
\else th%
\fi\fi\fi\fi\fi\fi
}}

\def\Proceedings{\ifshortconferences {\sl Proc.}\else {\sl Proceedings}\fi}

\newcounter{confnum}

\def\conf#1#2{%
\setcounter{confnum}{#2}%
\addtocounter{confnum}{-\csname #1zero\endcsname}%
\ifnum\value{confnum}=1%
\expandafter\ifx\csname #1One\endcsname\relax%
\Proceedings\ {\sl of the} \arabic{confnum}\ending{\value{confnum}}\ 
\csname #1name
\endcsname,\ \csname #1pub\endcsname,\ 19#2%
\else \csname #1One\endcsname\fi%
\else\ \Proceedings\ {\sl of the}
\arabic{confnum}\ending{\value{confnum}}\ \csname #1name\endcsname,\ %
\csname #1pub\endcsname,\ 19#2\fi}

\def\stoc{\conf{STOC}}
\def\STOCname{\ifshortconferences ACM STOC\else {\sl Annual Symposium on 
the Theory of Computing}\fi}
\def\STOCzero{68}
\def\STOCpub{ACM}

\def\focs{\conf{FOCS}}
\def\FOCSname{\ifshortconferences IEEE FOCS\else {\sl Symposium on Foundations
of Computer Science}\fi}
\def\FOCSzero{59}
\def\FOCSpub{IEEE}

\def\structures{\conf{Structures}}
\def\Structuresname{{\sl Annual Conference on Structure in Complexity Theory}}
\def\Structureszero{85}
\def\StructuresOne{{\sl Structure in Complexity Theory}}
\def\Structurespub{IEEE}

\def\soda{\conf{SODA}}
\def\SODAname{\ifshortconferences {\sl Symp. on Discrete Algorithms}\else 
{\sl Annual Symposium on Discrete Algorithms}\fi}
\def\SODAzero{89}
\def\SODApub{ACM-SIAM}


\newcommand{\istcs}[1]{\ifnum#1=
93{{\sl Proceedings of the Second Israel Symposium on Theory 
and Computing Systems\/}, IEEE, 1993}\else{\ifnum#1=
95{{\sl Proceedings of the Third Israel Symposium on Theory 
and Computing Systems\/}, IEEE, 1995}\else
This ISTCS not yet defined!
\fi}\fi}

% For conferences with Springer Verlag LNCS proceedings.

\def\svconf#1#2{%
\csname #1name\endcsname~#2 {\sl Proceedings}, 
Lecture Notes in Computer Science Vol.~\csname #1vol\endcsname{#2},
\csname #1ed\endcsname{#2} ed., Springer-Verlag, 19#2}

\def\crypto{\svconf{CRYPTO}}
\def\CRYPTOname{{\sl Advances in Cryptology -- Crypto}}

\def\CRYPTOvol#1{\ifnum#1=
84{196}\else{\ifnum#1=
85{218}\else{\ifnum#1=
86{263}\else{\ifnum#1=
87{293}\else{\ifnum#1=
88{403}\else{\ifnum#1=
89{435}\else{\ifnum#1=
90{537}\else{\ifnum#1=
91{576}\else{\ifnum#1=
92{740}\else{\ifnum#1=
93{773}\else{\ifnum#1=
94{839}\else{\ifnum#1=
95{963}\else{\ifnum#1=
96{1109}\else{\ifnum#1=
97{??}\else{\ifnum#1=
98{??}\else{\ifnum#1=
99{??}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}


\def\CRYPTOed#1{\ifnum#1=
84{R.~Blakely}\else{\ifnum#1=
85{H.~Williams}\else{\ifnum#1=
86{A.~Odlyzko}\else{\ifnum#1=
87{C.~Pomerance}\else{\ifnum#1=
88{S.~Goldwasser}\else{\ifnum#1=
89{G.~Brassard}\else{\ifnum#1=
90{A.~J.~Menezes and S.~Vanstone}\else{\ifnum#1=
91{J.~Feigenbaum}\else{\ifnum#1=
92{E.~Brickell}\else{\ifnum#1=
93{D.~Stinson}\else{\ifnum#1=
94{Y.~Desmedt}\else{\ifnum#1=
95{D.~Coppersmith}\else{\ifnum#1=
96{N.~Koblitz}\else{\ifnum#1=
97{B.~Kaliski}\else{\ifnum#1=
98{H.~Krawczyk}\else{\ifnum#1=
99{}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}

\def\eurocrypt{\svconf{EUROCRYPT}}
\def\EUROCRYPTname{{\sl Advances in Cryptology -- Eurocrypt}}

\def\EUROCRYPTvol#1{\ifnum#1=
84{209}\else{\ifnum#1=
85{219}\else{\ifnum#1=
86{??}\else{\ifnum#1=   % Seems there was no Eurocrypt 86
87{304}\else{\ifnum#1=
88{330}\else{\ifnum#1=
89{434}\else{\ifnum#1=
90{473}\else{\ifnum#1=
91{547}\else{\ifnum#1=
92{658}\else{\ifnum#1=
93{765}\else{\ifnum#1=
94{950}\else{\ifnum#1=
95{921}\else{\ifnum#1=
96{1070}\else{\ifnum#1=
97{1233}\else{\ifnum#1=
98{??}\else{\ifnum#1=
99{??}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}

\def\EUROCRYPTed#1{\ifnum#1=
84{T.~Beth}\else{\ifnum#1=
85{F.~Pichler}\else{\ifnum#1=
86{??}\else{\ifnum#1=    %  Seems there was no Eurocrypt 86
87{D.~Chaum}\else{\ifnum#1=
88{C.~Gunther}\else{\ifnum#1=
89{J-J.~Quisquater, J.~Vandewille}\else{\ifnum#1=
90{I.~Damg{\aa}rd}\else{\ifnum#1=
91{D.~Davies}\else{\ifnum#1=
92{R.~Rueppel}\else{\ifnum#1=
93{T.~Helleseth}\else{\ifnum#1=
94{A.~De~Santis}\else{\ifnum#1=
95{L.~Guillou and J.~Quisquater}\else{\ifnum#1=
96{U.~Maurer}\else{\ifnum#1=
97{W.~Fumy}\else{\ifnum#1=
98{K.~Nyberg}\else{\ifnum#1=
99{??}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}

\def\auscrypt{\svconf{AUSCRYPT}}
\def\AUSCRYPTname{{\sl Advances in Cryptology -- Auscrypt}}
\def\AUSCRYPTvol#1{\ifnum#1=
92{718}\fi}
\def\AUSCRYPTed#1{\ifnum#1=
92{}\fi}

\def\asiacrypt{\svconf{ASIACRYPT}}
\def\ASIACRYPTname{{\sl Advances in Cryptology -- ASIACRYPT}}

\def\ASIACRYPTvol#1{\ifnum#1=
91{739}\else{\ifnum#1=
94{917}\else{??}\fi}\fi}

\def\ASIACRYPTed#1{\ifnum#1=
91{H.~Imai, R.~Rivest and T.~Matsumoto}\else{\ifnum#1=
94{J.~Pieprzyk and R.~Safavi-Naini}\else{??}\fi}\fi}

\def\icalp{\svconf{ICALP}}
\def\ICALPname{ICALP}

\def\ICALPvol#1{\ifnum#1=
78{62}\else{\ifnum#1=
79{??}\else{\ifnum#1=
80{??}\else{\ifnum#1=
81{115}\else{\ifnum#1=
82{??}\else{\ifnum#1=
83{??}\else{\ifnum#1=
84{??}\else{\ifnum#1=
85{??}\else{\ifnum#1=
86{226}\else{\ifnum#1=
87{267}\else{\ifnum#1=
88{317}\else{\ifnum#1=
89{372}\else{\ifnum#1=
90{443}\else{\ifnum#1=
91{510}\else{\ifnum#1=
92{623}\else{\ifnum#1=
93{700}\else{\ifnum#1=
94{820}\else{\ifnum#1=
95{??}\else{\ifnum#1=
96{??}\else{\ifnum#1=
97{??}\else{\ifnum#1=
98{??}\else{\ifnum#1=
99{??}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}
\fi}\fi}\fi}\fi}\fi}

\def\ICALPed#1{\ifnum#1=
78{??}\else{\ifnum#1=
79{??}\else{\ifnum#1=
80{??}\else{\ifnum#1=
81{??}\else{\ifnum#1=
82{??}\else{\ifnum#1=
83{??}\else{\ifnum#1=
84{??}\else{\ifnum#1=
85{??}\else{\ifnum#1=
86{L.~Kott}\else{\ifnum#1=
87{T.~Ottman}\else{\ifnum#1=
88{T.~Lepisto}\else{\ifnum#1=
89{G.~Ausiello}\else{\ifnum#1=
90{M.~Paterson}\else{\ifnum#1=
91{A.~Leach}\else{\ifnum#1=
92{W.~Kuich}\else{\ifnum#1=
93{A.~Lingas}\else{\ifnum#1=
94{S.~Abiteboul}\else{\ifnum#1=
95{??}\else{\ifnum#1=
96{??}\else{\ifnum#1=
97{??}\else{\ifnum#1=
98{??}\else{\ifnum#1=
99{??}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}
\fi}\fi}\fi}\fi}\fi}

\def\svvconf#1#2{%
{\sl Proceedings of the\/} 19#2\ \csname #1name\endcsname,
Lecture Notes in Computer Science Vol.~\csname #1vol\endcsname{#2},
\csname #1ed\endcsname{#2} ed., Springer-Verlag, 19#2}

\def\fsttcs{\svvconf{FSTTCS}}
\def\FSTTCSname{{\sl Symposium on the Foundations of Software Technology and 
Theoretical Computer Science}}
\def\FSTTCSvol#1{\ifnum#1=
94{880}\fi}
\def\FSTTCSed#1{\ifnum#1=
94{P.~Thiagarajan}\fi}

\def\stacs{\svvconf{STACS}}
\def\STACSname{{\sl Symposium on Theoretical Aspects of Computer Science}}

\def\STACSvol#1{\ifnum#1=
84{166}\else{\ifnum#1=
85{182}\else{\ifnum#1=
86{210}\else{\ifnum#1=
87{247}\else{\ifnum#1=
88{294}\else{\ifnum#1=
89{349}\else{\ifnum#1=
90{415}\else{\ifnum#1=
91{480}\else{\ifnum#1=
92{577}\else{\ifnum#1=
93{665}\else{\ifnum#1=
94{775}\else{\ifnum#1=
95{900}\else{\ifnum#1=
96{??}\else{\ifnum#1=
97{??}\else{\ifnum#1=
98{??}\else{\ifnum#1=
99{??}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}

\def\STACSed#1{\ifnum#1=
84{M.~Fontet}\else{\ifnum#1=
85{K.~Melhorn}\else{\ifnum#1=
86{B.~Monien}\else{\ifnum#1=
87{F.~Brandenburg}\else{\ifnum#1=
88{R.~Cori}\else{\ifnum#1=
89{B.~Monien}\else{\ifnum#1=
90{C.~Choffrut}\else{\ifnum#1=
91{C.~Choffrut}\else{\ifnum#1=
92{A.~Finkel}\else{\ifnum#1=
93{A.~Finkel}\else{\ifnum#1=
94{P.~Enjalbert}\else{\ifnum#1=
95{E.~Mayr}\else{\ifnum#1=
96{??}\else{\ifnum#1=
97{??}\else{\ifnum#1=
98{??}\else{\ifnum#1=
99{??}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}\fi}

\newcommand{\ccs}[1]{\ifnum#1=
93{{\sl Proceedings of the First Annual Conference on
Computer and Communications Security\/}, ACM, 1993}\else{\ifnum#1=
94{{\sl Proceedings of the Second Annual Conference on
Computer and Communications Security\/}, ACM, 1994}\else{\ifnum#1=
95{No CCS this year!}\else{\ifnum#1=
96{{\sl Proceedings of the Third Annual Conference on
Computer and Communications Security\/}, ACM, 1996}\else{\ifnum#1=
97{{\sl Proceedings of the Fourth Annual Conference on
Computer and Communications Security\/}, ACM, 1997}\else
This CCS not yet defined!
\fi}\fi}\fi}\fi}\fi}

\newcommand{\isoc}[1]{ISOC~{#1}}

\newcommand{\dimacs}[1]{\ifnum#1=
89{{\sl Distributed Computing and Cryptography\/},
DIMACS Series in Discrete Mathematics and Theoretical Computer
Science, Vol.~2, ACM, 1991}\else
This DIMACS not yet defined!
\fi}

\newcommand{\isaac}[1]{\ifnum#1=
92{{\sl Proceedings of ISAAC~92,\/} Lecture Notes in
Computer Science Vol.~650, Springer Verlag, 1992}\else
This ISAAC not yet defined!
\fi}

\newcommand{\colt}[1]{\ifnum#1=
92{{\sl Proceedings of the Fifth Annual Workshop on Computational Learning 
Theory\/}, ACM, 1992}\else
This COLT not yet defined!
\fi}




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

% Theorem environments

\newtheorem{thm}{Theorem}
\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}{Example}

\newenvironment{theorem}{\begin{thm}\begin{em}}%
{\end{em}\end{thm}}
\newenvironment{lemma}{\begin{lem}\begin{em}}%
{\end{em}\end{lem}}
\newenvironment{corollary}{\begin{cor}\begin{em}}%
{\end{em}\end{cor}}
\newenvironment{proposition}{\begin{propo}\begin{em}}%
{\end{em}\end{propo}}
\newenvironment{definition}{\begin{defn}\begin{em}}%
{\end{em}\end{defn}}
\newenvironment{assumption}{\begin{assm}\begin{em}}%
{\end{em}\end{assm}}
\newenvironment{claim}{\begin{clm}\begin{em}}%
{\end{em}\end{clm}}
\newenvironment{remark}{\begin{rem}\begin{em}}%
{\end{em}\end{rem}}
\newenvironment{example}{\begin{examp}\begin{em}}%
{\end{em}\end{examp}}

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

% deluxe proof environment
\def\qsym{\vrule width0.6ex height1em depth0ex}
\newcount\proofqeded
\newcount\proofended
\def\qed{ {\hspace{5pt}\rule[-1pt]{3pt}{9pt}}
\end{rm}\addtolength{\parskip}{-0pt}
\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{0pt}\noindent{\bf Proof of #1:\
}%
\addtolength{\parskip}{0pt}\setlength{\parindent}{0pt}}
\def\@nprf{\begin{rm}\protect\vspace{0pt}\noindent{\bf Proof:\ }%
\addtolength{\parskip}{0pt}\setlength{\parindent}{0pt}}
\makeatother



\newcommand{\verylongrightarrow}[1]		%longleft and rightgoing arrows
	{\setlength{\unitlength}{.01in}		%for protocols
	 \begin{picture}(#1,1) \put(0,0){\vector(1,0){#1}} \end{picture}}
\newcommand{\rightgoing}[2]{{\stackrel{{\displaystyle #1}} {\verylongrightarrow{#2}}}}

\newcommand{\verylongleftarrow}[1]
	{\setlength{\unitlength}{.01in} \begin{picture}(#1,1) \put(#1,0){\vector(-1,0){#1}} \end{picture}}

\newcommand{\leftgoing}[2]{{\stackrel{{\displaystyle #1}} {\verylongleftarrow{#2}}}}

\newcommand{\verylongline}[1]			%longleft and rightgoing arrows
	{\setlength{\unitlength}{.01in}		%for protocols
	 \begin{picture}(#1,1)
	  \put(0,0){\line(1,0){#1}}
	 \end{picture}}
\newcommand{\stackline}[2]{{\stackrel{{\displaystyle{#1}}}
			    {\verylongline{#2}}}}

\newcommand{\leftgoinga}[1]{\leftgoing{#1}{400} }
\newcommand{\rightgoinga}[1]{\rightgoing{#1}{400} }

\def\kds{S}
\def\encKA{K_A^e}
\def\encKB{K_B^e}
\def\macKA{K_A^m}
\def\macKB{K_B^m}
\def\data{{\rm Text}}
\newcommand{\newconcat}{\,.\,}

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

% Lists

\newcounter{ctr}
\newcounter{ectr}
\newcounter{eectr}

\newenvironment{newenum}{%
\begin{list}{{\rm (\arabic{ctr})}\hfill}{\usecounter{ctr} \labelwidth=18pt%
\labelsep=7pt \leftmargin=25pt \topsep=0pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{0pt}}}{\end{list}}

\newenvironment{onelist}{%
\begin{list}{{\rm (\arabic{ctr})}\hfill}{\usecounter{ctr} \labelwidth=15pt%
\labelsep=6pt \leftmargin=21pt \topsep=4pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{4pt} }}{\end{list}}

\newenvironment{twolist}{%
\begin{list}{{\rm (\arabic{ctr}.\arabic{ectr})}%
\hfill}{\usecounter{ectr} \labelwidth=22pt%
\labelsep=6pt \leftmargin=28pt \topsep=2pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{2pt} }}{\end{list}}

\newenvironment{threelist}{%
\begin{list}{{\rm (\arabic{ctr}.\arabic{ectr}.\arabic{eectr})}%
\hfill}{\usecounter{eectr} \labelwidth=29pt%
\labelsep=6pt \leftmargin=35pt \topsep=2pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{2pt} }}{\end{list}}

\newenvironment{newitemize}{%
\begin{list}{$\bullet$}{\labelwidth=19pt%
\labelsep=7pt \leftmargin=26pt \topsep=3pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{3pt} }}{\end{list}}

\newenvironment{indentlist}{%
\begin{list}{\mbox{}}{\labelwidth=20pt%
\labelsep=0pt \leftmargin=20pt \topsep=10pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{10pt} }}{\end{list}}

\newenvironment{tiret}{%
\begin{list}{\hspace{2pt}\rule[0.5ex]{6pt}{1pt}\hfill}{\labelwidth=11pt%
\labelsep=4pt \leftmargin=15pt \topsep=0pt%
\setlength{\listparindent}{\saveparindent}%
\setlength{\parsep}{\saveparskip}%
\setlength{\itemsep}{0pt}}}{\end{list}}

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

% 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}}

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

\def\from{\mbox{from}\ }
\def\From{\mbox{From}\ }


\renewcommand{\choose}[2]{{{#1}\atopwithdelims(){#2}}}
\def\poly{\mathop{\rm poly}\nolimits}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}
\def\plus{{\;+\:}}
\def\e{\epsilon}
\def\d{\delta}
\newcommand{\then}{{;\;\;}}   % for [ ; ; ; : ] notation
\newcommand{\andthen}{{\;:\;\;}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\alg}[1]{\langle\:#1\:\rangle}
\newcommand{\sfrac}[2]{{\textstyle \frac{#1}{#2}}}
\def\a{\alpha}
\newcommand{\xor}{{\oplus}}
\newcommand{\concat}{\|}
\newcommand{\Concat}{\;\|\;}
\newcommand{\Colon}{{:\;\;}}
\def\eqq{{\:=\:}}
\def\geqq{{\:\geq\:}}
\def\leqq{{\:\leq\:}}
\def\gets{\leftarrow}
\def\getsr{\stackrel{{\scriptscriptstyle R}}{\leftarrow}}
\def\emptystring{\epsilon}

\newcommand{\calC}{{\cal C}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calE}{{\cal E}}
\newcommand{\calF}{{\cal F}}
\newcommand{\calS}{{\cal S}}
\newcommand{\calG}{{\cal G}}
\newcommand{\calM}{{\cal M}}
\newcommand{\Z}{{\hbox{\sf Z}}}
\newcommand{\R}{{\hbox{\rm\bf R}}}
\newcommand{\N}{{\hbox{\bf N}}}
\newcommand{\set}[2]{\{\:#1 \suchthat #2\:\}}
\def\next{\: ; \:}

\newcommand{\headingg}[1]{{\sc{#1}}}
\newcommand{\headinggg}[1]{{\noindent\sc{#1}}}
\newcommand{\heading}[1]{{\vspace{5pt}\noindent\sc{#1}}}
\newcommand{\goesto}{\mapsto}

\newcommand{\abs}[1]{{\displaystyle \left| {#1} \right| }}

\newcommand{\Prob}[1]{{{\Pr}\left[{#1}\right]}}
\newcommand{\CondProb}[2]{{{\Pr}\left[{#1}\:\left|\right.\:#2\right]}}
\newcommand{\Probb}[2]{{\textstyle\Pr_{#1}}\left[{#2}\right]}
\newcommand{\Probbstar}[2]{{\textstyle\Pr^*_{#1}}\left[{#2}\right]}
\newcommand{\CondProbb}[3]{{\textstyle\Pr_{#1}}\left[{#2}\:\left|\right.#3%
\right]}
\newcommand{\ProbExp}[2]{{{\Pr}\left[{#1}\: : \:#2\right]}}
\newcommand{\probb}[1]{{\textstyle\Pr_{#1}}}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil}[1]{\lceil{#1}\rceil}

\def\next{\:;\:}
\newcommand{\suchthat}{\::\:}
\newcommand{\qquadd}{{\quad\qquad}}               % \quad or \qquad
\def\cross{\times}
\def\union{\cup}
\def\intersection{\cap}
\newcommand{\complement}[1]{\overline{#1}}

% Complexity classes

\newcommand{\cclass}[1]{\mbox{\bf #1}}
\newcommand{\reduces}[1]{\,\leq_{\scriptscriptstyle #1}\,}

\def\MIP{\cclass{MIP}}
\newcommand{\PCP}[3]{\cclass{PCP}_{#1}[\,#2,\,#3\,]}
\newcommand{\AFPCP}[2]{\overline{\cclass{FPCP}}[\,#1,\,#2\,]}
\def\P{\cclass{P}}
\def\NP{\cclass{NP}}
\def\coNP{{\rm co}\cclass{NP}}
\def\BPP{\cclass{BPP}}
\def\coRP{{\rm co}\cclass{RP}}
\def\coRQP{{\rm coR}\tilde{\rm P}}
\def\PSPACE{\cclass{PSPACE}}
\def\NPSPACE{\cclass{NPSPACE}}
\def\L{\cclass{L}}
\def\NL{\cclass{NL}}
\def\RP{\cclass{RP}}
\def\ZPP{\cclass{ZPP}}
\def\NEXP{\cclass{NEXP}}
\def\EXP{\cclass{EXP}}
\def\BPEXP{\cclass{BPEXP}}
\newcommand{\FPCP}[3]{\cclass{FPCP}_{#1}[\,#2,\,#3\,]}
\def\MAXSNP{\mbox{Max-SNP}}
\def\TIME{\cclass{TIME}}
\def\SPACE{\cclass{SPACE}}
\def\NTIME{\cclass{NTIME}}
\def\NSPACE{\cclass{NSPACE}}
\def\IP{\cclass{IP}}

\def\iv{{\rm IV}}
\def\cf{{\rm CF}}

\def\Tag{{\it Tag}}
\def\MAC{{\it MAC}}
\def\Verify{{\it Vf}}
\newcommand{\bin}[1]{\langle #1\rangle}
\def\cxor{{\rm counter-xor}}
\def\rxor{{\rm random-xor}}
\def\XORtag{{\rm XOR}}
\def\e{\epsilon}
\def\d{\delta}
\def\Adv{{\sf Adv}}
\def\enc{{\cal E}}
\def\dec{{\cal D}}
\def\cbc{{\rm CBC}}
\def\DES{{\rm DES}}
\def\order{{\rm ord}}
\def\sstest{\mbox{SS-Primality-Test}}
\def\succ{{\rm Succ}}
\def\pk{{\sl pk}}
\def\sk{{\sl sk}}

\def\keygen{{\rm KeyGen}}
\def\sign{{\rm Sign}}
\def\verify{{\rm Verify}}
\def\hash{{\sl Hash}}
\def\qsig{q_{\rm sig}}
\def\qhash{q_{\rm hash}}

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

\newcommand{\courseheader}{%
Massachusetts Institute of Technology \hfill Department of Computer Science \\
{\bf Course:} 6.87s  \hfill \handoutdate \\
{\bf Instructors:} S.~Goldwasser and M.~Bellare \hfill % {\bf TA:} T.~Malkin 
\\
{\bf \handoutname} \hfill {\bf Handout No:} \handoutnumber \\
\vspace{-18pt}

\mbox{}\hrulefill\mbox{}}

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