\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{\la}{{\leftarrow}}
\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{Assumption}{Assumption}
\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{\bits}{\{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}}
\newcommand{\bbZ}{\mathbb{Z}}
\noindent {\bf \LARGE Final}\hfill (60 points)
\noindent {\bf \large Your name here}\\
\noindent Due on {\bf 11:59pm Dec. 19th}.
\noindent Solution must be typed, preferably using LaTeX. \\
It should be submitted via email to \textrm{rachel.lin@cs.ucsb.edu}.\\
\noindent You must complete this final on your own. In particular, you
cannot collaborate with anyone else, nor reference public
resources. The only materials you can use during solving the final are
your own notes and homeworks, homework solutions, slides, and scribe
notes distributed and created during this class, and lecture notes and
textbooks linked to in the course webpage.
%%%%%%%%%%%%%%%%%% PART 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Part{Basics}{19}
\begin{enumerate}[{\bf a)}]
\item {\bf [6 pts]} Consider the group $\bbZ^*_{17}$ with
multiplication modulo $17$. Compute the following:
\begin{center}
{\bf (i)} $9^{-1}$ mod $17$, \;\; {\bf (ii)} $7^{-1}$ mod $17$,
\;\; {\bf (iii)} $7^{16}$ mod $17$
\end{center}
Justify your answers!
\item {\bf [9 pts]} Which ones of the following functions are
negligible? Justify your answers!
\begin{center}
{\bf (i)} $f_1(n) = 2^{-200 \cdot \log(n)}$,\;\;\; {\bf (ii)} $f_2(n) =
2^{-\sqrt{n}}$,\;\;\; {\bf (iii)} $f_3(n) = 1/\log(n)$.
\end{center}
In particular, to show that a function $f(n)$ is negligible, prove
that for all constants $c \ge 1$ there exists some value $n_0 =
n_0(c)$ such that $f(n) \le \frac{1}{n^c}$ for all $n \ge n_0$. To
show that a function is {\em not} negligible, give a $c \ge 1$ such
that $f(n) \ge \frac{1}{n^c}$ for infinitely many values of $n$.
\item {\bf [4 pts]} Let $\eps_1, \eps_2, \eps_3, \cdots$ be an
infinitely long sequence of negligible functions. Define the following function $\mu$:
\[\mu(n) = \Sigma_{i \in [n]} \eps_i(n)\]
Is $\mu$ necessarily a negligible function? (i.e., Is $\mu$
negligible no matter which negligible functions $\eps_1, \eps_2,
\cdots$ are?) Justify your answer!
\end{enumerate}
%%%%%%%%%%%%%%%%%% PART 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Part{One-Way Function}{6}
\begin{enumerate}[{\bf a)}]
\item {\bf [4 pts]} Let $f: \bits^k \to \bits^k$ be an
efficiently computable permutation, i.e., $f$ is one-to-one. Now,
recall that a hardcore predicate $P: \bits^k \to \bits$ is an
efficiently computable function such that for every PPT adversary
$\advA$ there exists a negligible function $\epsilon = \epsilon(k)$
such that $\advA$ guesses $P(x)$ given $f(x)$ with probability at
most $\frac{1 + \epsilon(k)}{2}$. \\
Prove that if $f$ has a hardcore predicate $P$, then $f$ is one-way.
\noindent {\bf Hint:} Given an inverter for $f$ with non-negligible
success probability, recall that you need to build an adversary
predicting $P(x)$ from $f(x)$ with probability non-negligibly higher
than $1/2$. Make sure your strategy always performs better than with
probability $\frac{1}{2}$.
\item {\bf [2 pts]} Does the above statement hold true if $f$ is not
necessarily a permutation, but can be an arbitrary function?
\end{enumerate}
%%%%%%%%%%%%%%%%%% PART 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Part{Pseudo-Random Functions and Generators}{19}
Let $G: \bits^k \to \bits^{2k}$ be a length-doubling PRG, and let us
explicitly write $G(x) = G_0(x) \| G_1(x)$ for two maps $G_0, G_1:
\bits^k \to \bits^k$ and every input seed $x$ (i.e., $G_0$ outputs the
first $k$ bits of the output of $G$ and $G_1$ outputs the second $k$
bits). In class, we presented a construction of a PRF from a
length-doubling PRG using a tree---this is called the {\em GGM
construction}.
In this exercise, we consider the following construction of a keyed
function $F: \bits^k \times \bits^{*} \to \bits^k$ which is a variant
of the {\em GGM construction}, adapted to the case of messages of {\em
arbitrary} length. For key $K \in \bits^k$ and input $M \in
\bits^*$, the construction parses $M$ as $M = m_1, m_2, \ldots,
m_{|M|}$, where $m_i \in \bits$ for all $i = 1, \ldots, |M|$. (Recall
that $|M|$ denotes the bit length of the message $M$.) Then, it sets
$y_0 \gets K$, and for all $i = 1, \ldots, |M|$ computes $y_i \gets
G_{m_i}(y_{i-1})$. Finally, it outputs $y_{|M|} = F(K, M)$.
The security of a PRF for arbitrary-length inputs, is defined as in
the case of fixed-length inputs (e.g., $n$ bits for some given $n$),
except that we compare the PRF function $F_K$, with a random function
$RF_{*, k}$ that takes an input of arbitrary length and maps it to a
random $k$ bit string. The PRF function is secure if no non-uniform
PPT distnguishers can distinguish an interaction with $F_k$ with $k$
sampled at random, from an interaction with $RF_{*,k}$.
\begin{enumerate}[{\bf a)}]
\item {\bf [4 pts]} Prove that $F$ described above is not a PRF. In
particular, analyze your attack and show that it achieves
non-negligible advantage in distinguishing $F_k$ with a randomly
sampled $k$ from $RF_{*,k}$.
{\bf Hint:} Find a non-trivial yet easily verifiable relation
between outputs $Y = F_K(M)$ and $Y' = F_K(M')$ for two carefully
chosen messages $M$ and $M'$ which is not satisfied if $Y, Y'$ are
random and independent, except with negligible probability.\\[0.2ex]
\item {\bf [3 pts]} In class, we showed that a MAC scheme can be
constructed from a keyed function. Show that the MAC scheme
instantiated using the above keyed function is not unforgeble. In
particular, analyze your attack and show that it breaks
unforgebility. \\[0.2ex]
\item {\bf [5 pts]} Present a fix to the above construction that
prevents the attacks shown in {\bf a)}. Argue (informally!) that the
construction is now a secure PRF.
{\bf Hint:} Encode the input $M$ so that the above attack is not
possible.\\[0.2ex]
\item {\bf [3 pts]} How can we make the above construction more
efficient if we are given a PRG $G: \bits^k \to \bits^{2^r \cdot
k}$?
{\bf Hint:} The construction will process now $r$ bits for every PRG
invokation.\\[0.2ex]
\item {\bf [4 pts]} Assume that we are given now a block cipher $E:
\bits^k \times \bits^k \to \bits^k$ which is assumed to be a secure PRF, how can
we modify the construction idea given in {\bf b-c)} to obtain a new
construction using $E$ instead of $G$ and processing $k$ bits per
invokation of $E$?
{\bf Hint:} Think of using $E$ to build a PRG which expands from $k$
bits to $2^k \cdot k$ bits. (Of course, such a ``PRG'' would not be
efficient, but we will not need to compute the whole output when
evaluating the construction and it helps to conceptually think this
way to obtain the right approach.)\\[0.2ex]
\end{enumerate}
%%%%%%%%%%%%%%%%%% PART 4 %%%%%%%%%%%%%%%%%%%%%
\Part{Public Key Encryption (PKE)}{6}
In class we saw the RSA assumption. This exercise considers a
different assumption:
\begin{Assumption}\label{assump:1}
There is a generation process $\Gen'$ that samples a multiplicative
group $G$ with prime order $q$ and a generator $g$ of $G$, such
that, the following ensembles are indistinguishable.
\begin{eqnarray*}
& \set{(G, q, g)\la \Gen'(1^n), x \la \bbZ_q, y \la \bbZ_q\ :\ G, q, g,
g^x, g^y, g^{xy} }_{n \in \bbN} \\
& \set{(G, q, g)\la \Gen'(1^n), x \la \bbZ_q, y \la \bbZ_q, z \la \bbZ_q\ :\ G, q, g,
g^x, g^y, g^{z} }_{n \in \bbN}
\end{eqnarray*}
\end{Assumption} {\bf Note:} A group $G$ with prime order $q$ is a
group with $q$ elements, and a generator $g$ of $G$ is simply an
element in $G$ with the property that $\set{g^0, g^1, \cdots g^{q-1}}
= G$. In other words, powers of $g$ ``generates'' the whole group. The
concrete choice of $G$, $q$, and $g$ is important for the assumption
to hold (as captured inside $\Gen'$), but not particularly important for
constructing a bit public key encryption from this assumption, which
is the focus of this exercise.
Consider the following construction of a {\em bit} public key
encryption $\Pi = (\Gen, \Enc, \Dec)$ scheme based on the above
assumption.
\begin{itemize}
\item {$\Gen(1^n)$:} Sample $(G, q, g)\la \Gen'(1^n)$ and $x \la
\bbZ_q$; compute $h = g^x$; and set $\pk = (G, q, g, h)$ and $\sk =
x$.
\item {$\Enc(\pk, b)$:} Parse $\pk = (G, q, g, h)$; sample random $y
\la \bbZ_q$; compute $\alpha = g^y$ and $\beta = h^y$; output
ciphertext $c = (\alpha,\ \beta \cdot g^b)$.
\item {$\Dec(\sk, b)$:} Parse $\sk = x$ and $c = (\alpha,\gamma)$;
compute $\beta = \alpha^x$ and $g^b = \gamma \cdot \beta^{-1}$;
output $0$ if $g^b = 1$ and $1$ if $g^b = g$.
\end{itemize}
Prove that $\Pi$ is multi-message secure under
Assumption~\ref{assump:1}. (You can directly use theorems proven in
class.)
\newpage
%%%%%%%%%%%%%%%%% Part 5 %%%%%%%%%%%%%%%%%%%%%
\Part{Digital Signatures}{10}
\Task{6}{Strong one-time signature scheme}
A {\bf strong} one-time signature scheme $(\Gen, \Sign, \Ver)$
satisfies the following (informally): A pair of keys $(\pk, \sk)
\rsample \Gen(1^n)$ is sampled; an adversary $\advA$ receiving $\pk$
requests to see a signature $\sigma$ on a message $m$ of its choice;
it is infeasible for $\advA$ to then output $(m',\sigma')$ satisfying
that $\sigma'$ is a valid signature for $m'$ and $(m, \sigma) \ne (m',
\sigma')$ (except with negligible probability).
{\bf Note} that different from one-time security introduced in class,
for {\em strong} one-time security, $\advA$ is allowed to output $m' = m$, as long as $\sigma' \ne \sigma$
(there could be multiple signatures for the same message).
\begin{enumerate}[{\bf a)}]
\item{\bf [3 pts]} Assuming the existence of one-way functions, show a one-way
function f for which Lamportâ€™s scheme is not a strong one-time
signature scheme.
\item{\bf [3 pts]} Construct a strong one-time signature scheme using any
assumption we have seen in class. (Hint: Use a particular one-way
function in Lamportâ€™s scheme.)
\end{enumerate}
\Task{4}{Relation between signature scheme and one-way function}
Prove that the existence of a one-time signature scheme for 1-bit
messages implies the existence of one-way functions.
\end{document}