\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{\Gen}{\mathsf{G}}
\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 11: Forward Security}
\author{Boaz Barak}
\date{Total of 100 points + 20 bonus points. \\ Exercises due December 13th, 2005 1:30pm. \\
Last homework of the term!}
\begin{document}
\maketitle
\begin{exercise}[60 points] The notion of forward security has a natural
generalization to \emph{signature schemes}.
\begin{enumerate}
\item State informally the goals for a forward-secure digital
signature scheme, and provide a formal definition for this notion.
\item Suppose that $(\Gen,\Sign,\Ver)$ is a construction for
standard (not forward-secure) chosen-message attack secure signature
schemes, where the length of the private and public keys, and also
the length of the signatures is $n$ (and the length of messages to
be signed can be arbitrary, i.e., works for any message $\bits^*$).
Construct a forward-secure signature scheme with lengths of private
and public keys is $O(n)$, and the length of each signature is at
most $O(T n)$, where $T$ is the maximum number of time periods
allows. (If it makes things simpler for you, the signature scheme
you construct can be defined only for messages of length $n$.)
\item Under the same assumption, construct a signature scheme where
the length of the public key and signatures is $O(n)$, but the
length of the private key can be $O(T \cdot n)$.
\item (\emph{20 point bonus question}) Can you construct a forward secure signature
scheme with better parameters? (Ideally, we'd like private key,
public key, and signature length to be at most $O(n\log T)$ or
perhaps even $O(n + \log T)$).
\end{enumerate}
\end{exercise}
\begin{exercise}[40 points] Another issue in protecting cryptographic keys, is
how to make sure that they are generated at random. In a simplified
scenario, suppose that you have two machines but one of them might
be faulty --- can you run an interaction between them that results
in an unbiased coin toss?
More formally, a \emph{secure coin-tossing protocol} is defined as
follows: it is a two-party protocol with the two parties named Alice
and Bob. There is a polynomial-time function $result$ that takes as
input the transcript of the protocol (i.e., the sequence of all
messages exchanged between the two parties), and outputs a bit $b\in
\bits$. Note that if the two parties are probabilistic, the
transcript $trans = \trans \angles{A(1^n),B(1^n)}$ of the execution
of the protocol (where both Alice and Bob are given as input the
security parameter $n$) is a random variable. We require that as
long as at least one party follows the protocol, for every $b\in
\bits$, the probability that $result(trans)=b$ is between
$\tfrac{1}{2}-\e(n)$ and $\tfrac{1}{2}+\e(n)$ where $n$ is the
security parameter for the protocol, and $\e(\cdot)$ is a function
such that $\e(n)=n^{-\omega(1)}$.
An example for a simple protocol attempting to solve this problem
would be for Alice to choose $b$ at random and to send it to Bob,
and for the result function to simply output $b$. This would work in
the case that both Alice and Bob are honest (i.e., follow the
protocol) and also if just Alice is honest, but not in the case that
just Bob is honest. Hence this is not a secure coin-tossing
protocol.
Construct a secure coin-tossing protocol.
See footnote for hint.\footnote{\textbf{Hint:} {\tiny You might want
to handle the case in which one party refuses to send a valid
message, by defining the $result$ function in such a way that in
this case the other party gets to choose the output $b$.}}
\end{exercise}
\end{document}