\documentclass[11pt]{article} \usepackage{palatino}
\usepackage[letterpaper,hmargin=1in,vmargin=1.1in]{geometry}
\usepackage{fancyhdr}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue]{hyperref}
\usepackage{url,amsmath,setspace,amssymb}
\usepackage{mathtools}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage[font=small,labelfont=bf]{caption}
\lhead{\Large CS290G --- Introduction to Cryptography}
\rhead{\Large Huija Lin} \chead{} \lfoot{} \cfoot{\thepage}
\rfoot{} \renewcommand{\headrulewidth}{1.0pt}
\pagestyle{fancy}
\usepackage[dvips]{graphicx}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{color}
\usepackage{multicol}
\definecolor{rvone}{RGB}{139,34,82}
\definecolor{rvtwo}{rgb}{0.00,0.62,0.22}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\rsample}{\stackrel{\mbox{\tiny $\$$}}{\leftarrow}}
\newcommand{\entropy}{\mathsf{H}}
\newcommand{\err}{\zeta}
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\BPP}{\mathsf{BPP}}
\newcommand{\poly}{\mbox{poly}}
\newcommand{\advA}{{\mathcal A}}
\newcommand{\distD}{{\mathcal D}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Exp}[1]{\mathsf{E}\left[#1\right]}
\newcommand{\abs}[1]{|#1|}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\setd}[2]{\left\{ #1 \,:\, #2 \right\}}
\newcommand{\inter}[1]{\ensuremath{\langle #1 \rangle}}
\newtheorem*{definition}{Definition}
\newtheorem{Definition}{Definition}
\newtheorem*{theorem}{Theorem}
\newtheorem{Theorem}{Theorem}
\newtheorem*{proposition}{Proposition}
\newtheorem{Proposition}{Proposition}
\newtheorem*{claim}{Claim}
\newtheorem{Claim}{Claim}
\newtheorem*{lemma}{Lemma}
\newtheorem{Lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem{Corollary}{Corollary}
\begin{document}
\makeatletter
\newcommand\parag{%
\@startsection{paragraph}{4}{\z@}%
{-3\p@ \@plus -1\p@ \@minus -1\p@}%
{-0.2em \@plus -0.12em \@minus -0.05em}%
{\normalfont\normalsize\scshape}}
\newcommand{\heading}[1]{\parag{#1}}
\makeatother
\renewcommand{\labelitemi}{-}
\newcommand{\zo}{\{0,1\}}
\newcommand{\inp}{\set{I}}
\newcommand{\out}{\set{O}}
\newcommand{\PKE}{\mathsf{PKE}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Enc}{\mathsf{Enc}}
\newcommand{\Dec}{\mathsf{Dec}}
\newcommand{\pk}{\mathsf{pk}}
\newcommand{\sk}{\mathsf{sk}}
\newcommand{\getsr}{\rsample}
\newcommand{\st}{\mathsf{st}}
\newcommand{\indcpa}{\mathrm{ind}\mbox{-}\mathrm{cpa}}
\newcommand{\true}{\texttt{true}}
\renewcommand{\null}{\texttt{null}}
\renewcommand{\Pr}{\mathbf{Pr}}
\newcommand{\Prob}[1]{[#1]}
\renewcommand{\mod}{\textrm{ mod }}
\newcommand{\algtable}[1]{
\begin{center}
\begin{minipage}[c]{1.0\linewidth}
\hrule\vspace{.2cm}
#1
\hrule
\end{minipage}
\end{center}
}
\newcommand{\fullseparate}{\noindent\rule{\linewidth}{0.4pt}}
\newcommand{\bigseparate}{\noindent\rule{8cm}{0.4pt}}
\newcommand{\smallseparate}{\noindent\rule{4cm}{0.4pt}}
\newcounter{PartCounter}
\setcounter{PartCounter}{1}
\newcounter{TaskCounter}
\newcommand{\Part}[2]{\vspace{1cm}\noindent{\Large {\bf Part
\arabic{PartCounter}} --- #1}\hfill(#2 points)
\fullseparate
\stepcounter{PartCounter}
\setcounter{TaskCounter}{1}
}
\newcommand{\Task}[2]{\vspace{.5cm}\noindent{\underline{{\bf Task
(\alph{TaskCounter})} --- {#2}}\hfill(#1
points)\stepcounter{TaskCounter}}\\}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\xor}{\oplus}
\newcommand{\Expr}{\mathsf{Exp}}
\newcommand{\Tag}{\mathsf{Tag}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\F}{\mathcal{F}}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\CRH}{\mathsf{CRH}}
\newcommand{\Advt}{\mathsf{Adv}}
\newcommand{\eps}{\epsilon}
\newcommand{\bbN}{\mathbb{N}}
\noindent {\bf \LARGE Homework 3}\hfill (38 points)
\noindent Due on 11:59pm Dec. 9th.
\noindent Solution must be typed, preferably using LaTeX.
\noindent It can be submitted via email to \textrm{rachel.lin@cs.ucsb.edu} or in class.
\noindent You can collaborate with one other student in class. Please
acknowledge your collaborator and all public resources that you use.
%%%%%%%%%%%%%%%%%% PART 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Part{Message Authentication Codes (MAC)}{6}
%%%%%%%%%%%%%%%%%% Task a %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Task{6}{Message Authentication Codes (MAC) for Broadcasting}
Suppose user $A$ is broadcasting packets to $n$ recipients $B_1,\cdots
B_n$. Each of the recipient $B_i$ wants to be assured that the message he
receives is indeed from $A$ and not from anyone else. They decided to
use a MAC scheme $(\Gen, \Tag, \Ver)$ to ensure this.
\begin{enumerate}
\item[(i)]{\bf (2 pts)} Suppose that $A$ shares a key $k$ with all the recipients
$B_1,\cdots, B_n$. For every message $m$ that $A$ broadcases, he
also sends a MAC of that message $\sigma \rsample \Tag(k, m)$; each
receipient can then verify the MAC. Explain in two sentences, why
this scheme is insecure, that is, a recipient $B_i$ cannot be sure
that a message and tag pair she receives is indeed from $A$?
\item[(ii)]{\bf (2 pts)} Suppose user $A$ has a set $S = \set{k_1, \cdots, k_\ell}$ of
$\ell$ secret keys. Each user $B_i$ has some subset $S_i \subseteq S$
of the keys. When $A$ broadcasts a message $m$, it also broadcasts
$\ell$ MACs, $\sigma_1, \cdots, \sigma_\ell$, where $\sigma_i\rsample
\Tag(k_i, m)$ is the MAC generated using the $i$'th key. A
recipient $B_i$ now accepts a message if all the MACs correspoinding
to the keys she holds in $S_i$ accepts. So what property should the set
$S_1\cdots S_n$ satisfy so that the attack from (i) above no longer
applies? (We assume that different recipients are far apart and do
not collude.)
\item[(iii)]{\bf (2 pts)} Show that when $n = 10$, that is, there are 10
recipients, the broadcaster $A$ only needs to append 5 MACs to every
message to satisfy the condition of part (ii). Describe the sets
$S_1,\cdots, S_{10} \subseteq \set{k_1,\cdots, k_5}$ you would use.
\end{enumerate}
%%%%%%%%%%%%%%%%%% PART---CRH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Part{Collision Resistant Hash Function (CRHF)}{12}
\Task{4}{The Relation between CRH and OWF.}
\noindent Let $\F = \set{f_i\ :\ D_i \rightarrow R_i}_{i \in I}$ be a
family of CRHFs with a function sampling algorithm $\Gen$, such that,
for every function $f_i$ in the support of $\Gen(1^n)$ (i.e., the
probability that $\Gen(1^n)$ outputs $i$ is non-zero), $D_i =
\zo^{2n}$ and $R_i = \zo^{n}$. That is, $\F$ is a family of CRHFs that
{\bf halves} the length of the inputs. Show that $\F$ is a collection of
OWFs.
\begin{itemize}
\item {\bf (2 pts)} Argue informally why this is the case.
\item {\bf (2 pts)} Prove this fomally.
{\bf Hint:} The statement can be shown by contra-positive. That is,
if there is an adversary $A$ that can invert $y = f_i(x)$ with
polynomial probability $1/p(n)$, when the function $f_i$ and input
$x$ are sampled at random (i.e., $i \rsample \Gen(1^n)$ and $x
\rsample \zo^{2n}$), then there is an adversary $B$ that can find a
collision of $f_i$ with polynomial probability $1/q(n)$, when the
function $f_i$ is sampled at random. Note that to invert $y$, $A$
succeeds as long as it finds any $x'$, such that $y = f_i(x')$; in
particular, $x'$ does not necessarily equal to $x$. Can you exploit
this fact to construct $B$ that finds collisions?
\end{itemize}
\Task{8}{Merkle Hash Trees.}
\noindent Merkle suggested a parallelizable way of constructing a hash
function that compresses inputs by many bits, from a hash function
that halves the length of the inputs. More specifically, let's say that $f$ is a
compressing function that maps 2 $n$-bit strings, or blocks, into one
$n$-bit block. Then, consider the following hash function $h$ for
compress $2^k$ $n$-bit blocks into one $n$-bit long block, in a
tree-fashion as described below.
To compute $h(M)$ with $M = m_0, \cdots m_{2^k-1}$, consider a binary
tree with $2^k$ leaves; its depth is exactly $k$, with the root
at level 0 and leaves at level $k$. Each tree node is labelled with a
$n$-bit block. For the leaves, the $i$'th leaf is labelled with the
$i$'th block $m_i$; for an intermediate node, its label is calculated
from the labels $l_0, l_1$ of it's two children, as $f(l_1,
l_2)$. According to this definition, the labels of all nodes on level
$k-1$ can be calculated from $M$, then one can compute labels of all
nodes on level $k-2$, so on and so forth, until the label of the root
is computed. The label of the root defines the value of $h(M)$.
\begin{enumerate}
\item[(i)] {\bf (2 pts)} Show that if an adversary can find a collision
for hash function $h$ (i.e., $M_1 \ne M_2$ such that $h(M_1) =
h(M_2)$). Then one can use $M_1$ and $M_2$ to find a collision of
$f$ (i.e., $m\ne m'$ and $f(m) = f(m')$).
\item[(ii)] {\bf (2 pts)} Consider extending the hash function $h$ to
handle messages of different lengths; for simplicity, consider only
message consisting of a power of two number of blocks (i.e., $|M| =
2^k \cdot n$ for some $k$, rather than a fixed $k$). More
precisely, the output of function $h'$ for an input $M$ of length
$2^k\cdot n$ is defined exactly as above; its output for an input
$M'$ of length $2^l\cdot n$ with $l\ne k$ is defined as above except
that the tree will have depth $l$ instead of $k$.
Now is this new hash function $h'$ that accepts inputs of different
lengths collision resistant?
{\bf Hint:} Try to find two messages $M$ and $M'$ with different
lengths that match to the same value.
\item[(iii)] {\bf (4 pts)} How can we fix function $h'$ described
above so that the property of (i) is true again, i.e., any collision
$(M, M')$ of $h'$ can be used to find a collision of $h$.
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%% PART---PRF %%%%%%%%%%%%%%%%%%%%%
\Part{Public Key Encryption (PKE)}{10}
%%%%%%%%%%%%%%%%% Task 1%%%%%%%%%%%%%%%%%%%%%
\Task{10}{Stronger Security of PKE}
\noindent In class, we introduced many message security, that is,
\begin{Definition}
We say that a public key encryption scheme $\Pi = (\Gen, \Enc,
\Dec)$ for $n$-bit messages is many message secure if for every
polynomial $q$, and every two sequences $\set{\vec m_0}_n$ and
$\set{\vec m_1}_n$, where $q = q(n)$, $\vec m_0 =
m_{0}[1], \cdots m_0[q]$ and $\vec m_1 = m_{1}[1],
\cdots m_1[q]$, with $|m_b[i]| = n$ for all $b, i$, the following
two ensembles are indistinguishable.
\begin{itemize}
\item $\set{(\pk, \sk)\rsample Gen(1^n) \ : \ pk, \Enc(\pk, m_0[1]),
\cdots, \Enc(\pk, m_0[q])}_n$
\item $\set{(\pk, \sk)\rsample Gen(1^n) \ : \ pk, \Enc(\pk, m_1[1]),
\cdots, \Enc(\pk, m_1[q])}_n$
\end{itemize}
Furthermore, we say that $\Pi$ is single message secure if the above
condition holds w.r.t.\ $q(n)=1$ for all $n \in \bbN$.
\end{Definition}
In class we showed that the following theorem holds.
\begin{Theorem}\label{thm:SMS-MMS}
Any encryption scheme that is single message secure is also
multi-message secure.
\end{Theorem}
Let us now consider another definition of security called IND-CPA
security, which stands for INDistinguishability based, Chosen
Plaintext Attack security. This definition considers an adversary who
chooses what messages he wants to see encryption of adaptively. More
precisely, consider the following experiment $\Expr^b(n)$ defined
by an adversary $A$, an encryption scheme $\Pi$, and a parameter $n$.
\noindent {\bf Experiment $\Expr^b(n)$:}
\begin{enumerate}
\item $(\pk, \sk) \rsample \Gen(1^n)$;
\item $A$ receives $\pk$ and can issue many queries (as many as
he wants) to an encryption oracle $\O$, which on input query $q_i =
(m^0_i, m^1_i)$, returns an encryption $c$ of message $m^b_i$ (i.e.,
$c \rsample \Enc(\sk, m^b_i)$).
\item Finally $A$ outputs a bit $b'$.
\end{enumerate}
Define the advantage of $A$ to be the difference in the probabilities
that $A$ outputs 1 in experiments $\Expr^0(n)$ and $\Expr^1(n)$, that
is, \[\Advt_A(n) = |\Pr[A \mbox{ outputs 1 in } \Expr^0(n)] - \Pr[A
\mbox{ outputs 1 in } \Expr^1(n)] |\]
\begin{Definition}
We say that a public key encryption scheme $\Pi = (\Gen, \Enc,
\Dec)$ for $n$-bit messages is IND-CPA secure if for all non-uniform
PPT adversary $A$, there is a negligible function $\eps$, such that,
the advantage of $A$ $\Advt_A(n) \le \eps(n)$ for all $n \in \bbN$.
Furthermore, we say that $\Pi$ is one-time secure if the above
condition holds for all non-uniform PPT adversary $A$ that asks for
at most one query to the encryption oracle in experiment
$\Expr^b(n)$, for all $b \in \zo$ and all $n \in \bbN$.
\end{Definition}
Consider a theorem similar to Theorem~\ref{thm:SMS-MMS}.
\begin{Theorem}\label{thm:OTS-CPA}
Any encryption scheme that is one-time secure is IND-CPA secure.
\end{Theorem}
\begin{enumerate}
\item[(i)]{\bf (2 pts)} Argue informally why Theorem~\ref{thm:OTS-CPA}
is true.
\item[(ii)]{\bf (2 pts)} Prove Theorem~\ref{thm:OTS-CPA}
formally.
{\bf Hint:} For both (i) and (ii), the argument and proof is similar
to that for Theorem~\ref{thm:SMS-MMS}. It needs to use a sequence of
hybrid experiments. The hybrid experiments here are just slightly
more complicated, since they will be interactive similar to
$\Expr^b(n)$.
\item[(iii)] {\bf (2 pts)} Argue informally that IND-CPA security
implies many-message security.
\item[(vi)] {\bf (4 pts)} Is IND-CPA security strictly stronger than
many-message security? If your answer is Yes, you need to show a
counter-example---an encryption scheme that is many-message secure,
but not IND-CPA secure. If you answer is No, you need to show that
if an encryption is many-message secure, then it is also IND-CPA
secure.
\end{enumerate}
\Part{Digital Signatures}{10}
\Task{10}{Improving efficiency of Lamport's signature scheme}
\noindent In class, we gave a construction of a one-time secure
signature scheme from one-way function. This construction is due to
Lamport, so we refer to it as the Lamport's signature scheme below.
Let $f: \zo^k \to \zo^k$ be a one-way function, and let
$\ell$ be an even number. Recall that when using $f$ to instantiate
Lamport's signature scheme for messages of length $\ell/2$ (thus
allowing us to sign $2^{\ell/2}$ messages), the signing and
verification keys consist of $\ell$ $k$-bit strings. \medskip
\noindent In this task, we are going to construct a signature scheme
$\Pi = (\Gen, \Sign, \Ver)$ which is meant to achieve an efficiency
improvement over Lamport's scheme presented in class. For keys
consisting of $k$ $\ell$-bit strings, we can sign a larger set of
messages consisting of roughly $2^{\ell}/\sqrt{\ell}$ messages.
\begin{enumerate}[{\bf c)}]
\item {\bf [4 pts]} Let $S_{\ell}$ be the set of $\ell$-bit strings
with exactly $\ell/2$ bits equal one. (E.g., for $\ell = 4$, strings
like $1100$, $0101$, etc are elements of $S_{\ell}$.) Also, note
that $S_{\ell}$ has $\binom{\ell}{\ell/2}$ elements, which is
approximately $2^{\ell}/\sqrt{\ell}$ elements.
Argue that for all distinct $\ell$-bit strings $X, X' \in S_{\ell}$,
i.e., $X \neq X'$, there exist $i \neq j$ such that $X[i] = 1$,
$X'[i] = 0$, and $X[j] =0$, $X'[j] = 1$.
\item {\bf [6 pts]} Show how to use $f$ to build a signature scheme
$\Pi = (\Gen, \Sign, \Ver)$ with message space $\set{M} = S_{\ell}$
and with both verification and signing keys consisting of $\ell$
$k$-bit strings. Argue (informally) that the resulting scheme is {\em one-time}
secure.
{\bf Hint:} Use the same ideas behind Lamport's signature scheme.
\end{enumerate}
\end{document}