\documentclass[11pt]{article}
\usepackage{amsmath, alltt, amssymb, xspace, times, epsfig}
\usepackage{amssymb}

\setlength{\evensidemargin}{0in} \setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in} \setlength{\textheight}{9in}
\setlength{\topmargin}{-0.15in} \setlength{\headheight}{0in}

\newcommand{\Zn}{\ensuremath{\mathbb{Z}_n}\xspace}
\newcommand{\Zns}{\ensuremath{\mathbb{Z}_n^*}\xspace}
\newcommand{\Zp}{\ensuremath{\mathbb{Z}_p}\xspace}
\newcommand{\Zps}{\ensuremath{\mathbb{Z}_p^*}\xspace}
\newcommand{\Zq}{\ensuremath{\mathbb{Z}_q}\xspace}

\newcommand{\smod}{\ensuremath{\mathrm{mod}\;}}

\newcommand{\DD}{\ensuremath{\mathcal{D}}\xspace}
\newcommand{\EE}{\ensuremath{\mathcal{E}}\xspace}

\newcommand{\Gen}{\ensuremath{\mathsf{Gen}}\xspace}
\newcommand{\Enc}{\ensuremath{\mathsf{Enc}}\xspace}
\newcommand{\Dec}{\ensuremath{\mathsf{Dec}}\xspace}

\renewcommand{\Pr}{\ensuremath{\mathbf{Pr}}\xspace}

\newcommand{\PT}{\ensuremath{\mathsf{PT}}\xspace}
\newcommand{\CT}{\ensuremath{\mathsf{CT}}\xspace}
\newcommand{\Key}{\ensuremath{\mathsf{Key}}\xspace}
\newcommand{\PrivK}{\ensuremath{\mathsf{PrivK}}\xspace}
\newcommand{\eav}{\ensuremath{\mathsf{eav}}\xspace}
\newcommand{\mult}{\ensuremath{\mathsf{mult}}\xspace}

\newcommand{\CC}{\ensuremath{\mathcal{C}}\xspace}
\newcommand{\KK}{\ensuremath{\mathcal{K}}\xspace}
\newcommand{\MM}{\ensuremath{\mathcal{M}}\xspace}
\newcommand{\AAA}{\ensuremath{\mathcal{A}}\xspace}



\newcommand{\note}[1]{\textbf{Note for TA:} #1}\xspace

\begin{document}
%\author{Ninghui Li}
%\date{}
%\maketitle

\thispagestyle{empty}

\noindent \textbf{CS555: Cryptography\hspace*{\fill}Spring 2012}
\begin{center}
{\LARGE Homework \#5}
\end{center}

\paragraph{Due date \& time:} 10:30am on April 5, 2012.
Hand in at the beginning of class (preferred), or email to the TA
(jiang97@purdue.edu) by the due time.

\vspace*{-0.1in}\paragraph{Late Policy:} You have three extra days in
total for all your homeworks.  Any portion of a day used counts as one
day; that is, you have to use integer number of late days each time. If
you emailed your homework to the TA by 10:30am the day after it was due,
then you have used one extra day. If you exhaust your three late days,
any late homework won't be graded.

\vspace*{-0.1in}\paragraph{Additional Instructions:}
The submitted homework must be typed. Using Latex is recommended, but not required.

\begin{description}

 \item[Problem 1 (10 pts)]
(a) Describe the NMAC construction and the HMAC construction. 
(b) Explain in your own words why NMAC offers secure MAC.
(c) In what aspect does HMAC differ from NMAC?\\

 \item[Problem 2 (8 pts)]
(Katz and Lindell.  Page 158.  Exercise 4.17.)  \\

 \item[Problem 3 (8 pts)]
(a) Give a CPA-secure encryption scheme and a secure MAC scheme such that when using them to instantiate the Encryption and Authenticate construction, the resulting construction is \textbf{secure}.  (b) Give a CPA-secure encryption scheme and a secure MAC scheme such that when using them to instantiate the Encryption and Authenticate construction, the resulting construction is \textbf{insecure}.\\

 \item[Problem 4 (8 pts)]
Repeat the previous problem for the Authenticate-then-Encrypt construction.\\

 \item[Problem 5 (8 pts)]
(Katz and Lindell.  Page 237.  Exercise 6.2.)  \textbf{Hint.}  Given a one-way function $g$, you need to construct a function $f$ such that $\forall n\,f(0^n)=0^n$ and prove that $f$ is one-way.\\

 \item[Problem 6 (8 pts)]
(Katz and Lindell.  Page 238.  Exercise 6.4.)  \\


 \item[Problem 7 (10 pts)]
(Katz and Lindell.  Page 296.  Exercise 7.21.)\\

 \item[Problem 8 (5 pts)]
(Katz and Lindell.  Page 295.  Exercise 7.15.) \textbf{Hint.} Show that if there exists an algorithm that can solve DLG, then there exists an algorithm that can solve CDH.\\

 \item[Problem 9 (5 pts)]
(Katz and Lindell.  Page 295.  Exercise 7.16.)\\

 \item[Problem 10 (10 pts)]
(Katz and Lindell.  Page 295.  Exercise 7.18.)  \textbf{Hint.}  The problem given in 7.18 is not hard.  Find an algorithm to compute $g^{1/x} \mod p$.\\

 \item[Problem 11 (10 pts)]
(Katz and Lindell.  Page 231.  Exercise 9.2.)\\

 \item[Problem 12 (10 pts)]
(Katz and Lindell.  Page 231.  Exercise 9.3.)\\


\end{description}

\end{document}
