\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{hyperref}
\usepackage{xspace}

        \newtheorem{theorem}{Theorem}
        \newtheorem{lemma}{Lemma}
        \newtheorem{proposition}{Proposition}
        \newtheorem{corollary}{Corollary}
        \newtheorem{definition}{Definition}
        \newtheorem{assumption}{Assumption}
        \newtheorem{claim}{Claim}
        \newtheorem{problem}{Problem}
        \newtheorem{construction}{Construction}
\DeclareMathOperator*{\expe}{\mathbb{E}}

\newcommand{\class}[1]{{\ensuremath{\mathsf{#1}}}}
\newcommand{\enc}{\ensuremath{\class{Enc}}\xspace}
\newcommand{\dec}{\ensuremath{\class{Dec}}\xspace}
\newcommand{\zo}{\ensuremath{\{0,1\}}\xspace}
\newcommand{\poly}{\ensuremath{\class{poly}}\xspace}
\newcommand{\negl}{\ensuremath{\class{ngl}}\xspace}
\newcommand{\mac}{\ensuremath{\class{Mac}}\xspace}
\newcommand{\ver}{\ensuremath{\class{Vfy}}\xspace}
\newcommand{\gen}{\ensuremath{\class{Gen}}\xspace}

\hypersetup{colorlinks,urlcolor=blue}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}

\title{CSE 5852: Problem Set 7}
\date{Due: November 14, 2016}
%\author{You}

\begin{document}
\maketitle

This assignment is different than previous assignments.  Rather than solving problems we are going to read a seminal paper in cryptography.  This was the first paper to propose a public-key cryptosystem:  ``A Method for Obtaining Digital Signatures and Public-Key Cryptosystems'' published in 1977.  It is available \href{http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA606588}{here}.  This paper won the authors the Turing Award in 2002 see info \href{http://amturing.acm.org/award_winners/rivest_1403005.cfm}{here}.

Your assignment is to read the paper and answer the following questions.

\begin{enumerate}
\item \textbf{10 pts} What does the paper claim is the main contribution of the work?
\item \textbf{3 pts} Who are Alice and Bob?
\item \textbf{10 pts} In section II the paper introduces four properties of a public key cryptosystem.  Define (mathematically) each of these properties.
\item \textbf{10 pts} This section mentions the topic of a trapdoor function.  Describe in words what is meant by a trapdoor function.  
\item \textbf{5 pts} What is a public file?  
\item \textbf{5 pts} How does the paper distinguish between authentication and a signature?
\item \textbf{5 pts} What is the proposed method for encryption?   Consider the encryption scheme as presented in Section V.  Provide a mathematical description for the $(\gen, \enc, \dec)$ of this scheme.

\item \textbf{5 pts} How does it compare to the signature algorithm presented in class?  

\item \textbf{3 pts} The paper introduces the concept of a public file.  What is the public file?
\item \textbf{5 pts} Recall we showed that $f_e$ is a permutation on $\mathbb{Z}_N^*$ and showed that $f_d$ is an inverse permutation.  For both signatures and encryption, this work assumes messages are an arbitrary message from $\{0,..., N-1\}$.  What is wrong with treating messages this way?

\item \textbf{5 pts} Give one reason why the scheme is not secure according to the definition of polynomially secure.  The definition is recalled below.

\begin{definition}
A public-key cryptosystem for $1$-bit messages is polynomially-secure if for all polynomial time $\mathcal{A}$ there exists a negligible function $\epsilon(n)$ such that
\[
|\Pr_{pk, sk, \enc}[\mathcal{A}(pk, \enc(pk, 0)) = 1] - \Pr_{pk, sk, \enc}[\mathcal{A}(pk, \enc(pk, 1)) = 1] | <\epsilon(n).
\]
\end{definition} 

\item \textbf{3 pts} How are $e, d$ defined in this paper?  (Its different from how they were defined in class.)

\item \textbf{10 pts} Provide a brief summary of the primality test recommended in the paper.  

\item \textbf{5 pts} To quote the paper ``Since no techniques exist to \emph{prove} than an encryption scheme is secure, the only test available is to see whether anyone can think of a way to break it.''  Based on your experience in the class, do you agree?  Why or why not?

\item \textbf{10 pts} What are the four ways the authors consider that one could compute $f_d$?

\item \textbf{10 pts} Do you think the authors implicitly have a security definition in mind for the encryption scheme, if so what is it? 

\end{enumerate}

\end{document}