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