\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\eqdef}{\stackrel{def}{=}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\indist}{\approx}
\newcommand{\dist}{\Delta}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\Adv}{\ensuremath{\mathsf{Adv}}}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{SAT}}}
\newcommand{\COL}{\ensuremath{\mathsf{3COL}}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\Time}{\cclass{Time}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Handout 8: Digital Signatures}
\author{Boaz Barak}
\date{Total of 115 points. \\ Exercises due November 22nd, 2005 1:30pm.}
\begin{document}
\maketitle
\begin{exercise}[Simple RSA-based Signatures are not secure, 15 points] Consider the following
simple signature schemes based on the RSA permutation, where signing is by decrypting/inverting
the permutation: \textbf{Public key:} $n=pq$ for $p,q$ random primes, $e \in \Z^*_{\phi(n)}$,
\textbf{Private key:} $d = e^{-1} \mod{\phi(n)}$ \textbf{Signing:} signature for $m$ is $m^d \pmod{n}$
\textbf{Verifying:} to verify $\sigma$ is a signature for $m$, verify that $m=\sigma^e$.
\begin{enumerate}
\item Prove that this scheme is \emph{not} a secure signature scheme.
\item Prove that this scheme is insecure even if we consider a weaker definition
of security where the attacker has to forge a message given to it as
input. That is, the attacher first gets an input message $m$, during
the attack can query the signing oracle only on messages $m' \neq m$
and at the end to succeed needs to output a valid signature for $m$.
\end{enumerate}
\end{exercise}
\begin{exercise}[Collision resistant hash functions for arbitrary length, 20 points]
Prove the following: if there exists a collision resistant hash
function collection mapping $n+1$ bit strings into $n$ bits strings,
then there exists a collection mapping arbitrary length bit strings
into $n$ bit strings.
\end{exercise}
\begin{exercise}[Hash functions have at most $2^{n/2}$ security, 20 points]
Prove that that there is no collection of functions $\{ h_k \}_{k
\bits^*}$ with $h_k:\bits^{2n}\To\bits^n$ that is
$(102^{n/2},1/10)$-collision resistant.
\end{exercise}
\begin{exercise}[Signatures for identification protocols, 60 points]
Consider the identification problem (i.e., there's a ``box'' that
controls access to some resource and authorized people are given
some secret information that enables them to use the resource, but
unauthorized people cannot do so, even if the know the contents of
the box).
\begin{enumerate}
\item Consider the weakest security definition of this problem
where the only attack
we're considering is an adversary that knows the contents of the box
(but can't construct a ``fake box'' or listen on conversations
between honest users and the box). Construct a non-interactive
(i.e., a protocol consisting of a single message from the user to
the box) protocol solving the identification problem and prove its
security.
\item Construct a non-interactive identification protocol
that remains secure under the stronger attack where an adversary may
listen in on other conversations and also construct ``fake boxes''.
Prove the security for your protocol. You may assume that all
parties have access to a perfectly synchronized global clock.
\item One problem in identification protocols is that authorized people may provide
their secret information to their friends (or sell it) to allow them
also to access the resource. Can you design a (possibly interactive)
protocol where there's a strong disincentive for them to do so? (You
may assume that each person has a secret, such as their
social-security number, that is known also to the central authority,
but they are reluctant to give to their friends. However, the
protocol should not allow an eavesdropping adversary or even a fake
box adversary to learn this secret.)
\end{enumerate}
\end{exercise}
\end{document}