\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{textcomp} % to get \textcent
\usepackage{epsfig}

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query


\newcommand{\textboxa}[1]{
  \begin{center}\fbox{\begin{minipage}[t]{6.6in}
  \setlength{\parindent}{3ex}
  \setlength{\parskip}{\medskipamount}
  \vspace{0.3ex} #1 \vspace{0.3ex}
  \end{minipage}}\end{center}}

\newcommand{\floatingtextboxa}[1]{
  \begin{figure}[htbp]
  \textboxa{#1}
  \end{figure}}

\begin{document} 
\inclassproblems{4, Fri.}                    % !! start the paper

\begin{problem}
\bparts

\ppart\label{fhat} For any vertex, $v$, in a graph, let $\widehat{v}$ be
the set of vertices adjacent to $v$, that is,
\[
\widehat{v} \eqdef \set{v' \suchthat \edge{v}{v'}\text{ is an edge of the
graph}}.
\]
Suppose $f$ is an isomorphism from graph $G$ to graph $H$.  Carefully
prove that $f(\widehat{v}) = \widehat{f(v)}$.

\solution{
We first show that $\widehat{f(v)} \subseteq f(\widehat{v})$ by showing that if $w
\in \widehat{f(v)}$, then $w \in f(\widehat{v})$.

Now $w \in \widehat{f(v)}$ means that $\edge{w}{f(v)}$ is an edge of $H$.
Since $f$ is an isomorphism, there must be some $v'$ such that $w= f(v')$.
So $\edge{f(v')}{f(v)}$ is an edge of $H$, and therefore $\edge{v'}{v}$ is
an edge of $G$, by definition of isomorphism.  This means $v' \in
\widehat{v}$, and so $f(v') \in f(\widehat{v})$ by definition of
$f(\widehat{v})$.  So $w = f(v') \in f(\widehat{v})$, as required.

Conversely, we show that $f(\widehat{v}) \subseteq \widehat{f(v)}$ by
showing that if $w \in f(\widehat{v})$, then $w \in \widehat{f(v)}$.

But $w \in f(\widehat{v})$ means that $w= f(v')$ for some $v'$ adjacent to
$v$ in $G$.  This means $\edge{v}{v'}$ is an edge of $G$, and so
$\edge{f(v)}{f(v')}$ is an edge of $H$ by definition of isomorphism.  So $w
= f(v')$ is adjacent to $f(v)$; in other words, $w \in \widehat{f(v)}$, as
required.
}

\ppart Conclude that if $G$ and $H$ are isomorphic graphs, then for each
$k \in \naturals$, they have the same number of degree $k$ vertices.

\solution{By definition, $\degr{v}= \card{\widehat{v}}$.  Since an
isomorphism is a bijection, a set and its image will be the same size (by
the Mapping Rule from Week 2 Notes), so the Lemma of part~\eqref{fhat}
implies that an isomorphism, $f$, maps degree $k$ vertices to degree $k$
vertices.  This means that the image under $f$ of the set of degree $k$
vertices of $G$ is precisely the set of degree $k$ vertices of $H$.  So by
the Mapping Rule again, there are the same number of degree $k$ vertices
in $G$ and $H$.}

\eparts

\end{problem}


\begin{problem}
For each of the following pairs of graphs, either define an isomomorphism
between them, or prove that there is none.  (We write $ab$ as shorthand
for $\edge{a}{b}$.)

\bparts

\ppart
\begin{align*}
G_1\text{ with }& V_1 = \set{1,2,3,4,5,6},\ E_1= \set{12,23,34,14,15,35,45}\\
G_2\text{ with }& V_2 = \set{1,2,3,4,5,6},\ E_2= \set{12,23,34,45,51,24,25}
\end{align*}

\solution{Not isomorphic: $G_2$ has a node, 2, of degree 4, but the maximum degree
in $G_1$ is 3.}

\ppart
\begin{align*}
G_1\text{ with } &V_1 = \set{1,2,3,4,5,6},\ E_1= \set{12,23,34,14,45,56,26}\\
G_2\text{ with } &V_2 = \set{a,b,c,d,e,f},\ E_2= \set{ab,bc,cd,de,ae,ef,cf}
\end{align*}

\solution{
Isomorphic with the vertex correspondence: $1f, 2c, 3d, 4e, 5a, 6b$
}

\ppart
\begin{align*}
G_1\text{ with } & V_1 = \set{a,b,c,d,e,f,g,h},\ E_1= \set{ab,bc,cd,ad,ef,fg,gh,he,dh,bf}\\
G_2\text{ with } & V_2 = \set{s,t,u,v,w,x,y,z},\ E_2=
\set{st,tu,uv,sv,wx,xy,yz,wz,sw,vz}
\end{align*}

\solution{
Not isomorphic: they have the same number of vertices, edges, and set of
vertex degrees.  But the degree 2 vertices of $G_1$ are all adjacent to
two degree 3 vertices, while the degree 2 vertices of $G_2$ are all
adjacent to one degree 2 vertex and one degree 3 vertex.
}

\eparts

\end{problem}


%\instatements{\newpage}

\floatingtextboxa{
\textboxtitle{The Graph Isomorphism Authentication Protocol}

\begin{enumerate}

\item I choose a graph, $G$, with a set, $V$, of 1000 vertices and 100,000
randomly placed edges.

\item Then I choose a random bijection, $f: V \to V$, and apply it to the
vertices of $G$ to obtain a graph, $G_f$, such that $f$ is an isomorphism
from $G$ to $G_f$.  \textbf{Assuming graph isomorphism for random graphs
of this size involves an impossibly time-comsuming calculation}, I will be
the only person who can find an isomorphism between $G$ and $G_f$.

\item I tell the Discover card company that the pair of graphs $G$ and $G_f$
will provide my signature, and I ask them to publish this pair on their
website with my name and mailing address.

\item When I want a merchant to charge a purchase to my Discover card, I
``sign'' the card by convincing the merchant that I know an isomorphism
between the published pair of graphs.  This shows the merchant I know a
secret known only to the person who had these graphs published, so he
knows it's me who signed.

\begin{quote}
To convince the merchant I know an isomorphism between the published
graphs without revealing any information about what the isomorphism is (so
he can't later forge my signature), I create a brand new random bijection,
$e: V \to V$, and apply it to the
vertices of $G$ to obtain another graph, $G_e$, such that $e$ is an
isomorphism from $G$ to $G_e$.

I then show the merchant graph $G_e$ (I could email it to him), and offer
to show him an isomorphism between $G_e$ and either of my published graphs
---his choice.  Then I show him the isomorphism between $G_e$ and
whichever published graph he chose.  (It should seem reasonable that
knowing an isomorphism between my random $G_e$ and either one of my
published graphs gives the merchant no help in finding an isomorphism to
my other published graph.  Proving this ---in fact, even defining
precisely what ``no help'' means ---goes beyond what we can cover in
6.042.  Take an introduction to cryptography such as 6.875 to learn more.)

Notice that an imposter could easily have applied his own permutation,
$p$, to either one of my published graphs.  This would give him his own
graph, $H_p$, and an isomorphism, $p$, from one of my graphs to $H_p$.  Of
course, the imposter would have no clue about finding an isomorphism
between his $H_p$ and my other published graph.  But the merchant might
legitimately worry about this: if a lucky imposter had made the same
choice of published graph as the merchant, the imposter could pretend to
be me and use $p$ to satisfy the merchant's request for an isomorphism.

To rule out such lucky fraud, the merchant and I simply repeat the
procedure: I generate random $G_e$'s another 99 times, and each time he
requires me to show him an isomorphism between $G_e$ and his random
choice of published graph.  I will always be able to show the merchant an
isomorphism, but the odds of an imposter fooling the merchant because the
merchant and imposter chose the same published graph every time would only
be 1 in $2^{100}$.  So the probabilility is negligible that a lucky
imposter could fool the merchant in this way.
\end{quote}
\end{enumerate}
}

\instatements{\newpage}
\begin{problem}
Answer the following questions about the Graph Isomorphism Authentication
Protocol.

\bparts 

\ppart How do I find an isomorphism between $G_e$ and $G_f$?

\solution{The isomorphism $f$ goes from $G$ to $G_f$ and $e$ goes from $G$
to $G_e$.  Let $d$ be the function from $V$ to $V$ such that $d(e(v)) = v$
for all $v \in V$.  (That is, $d = e^{-1}$.)  Then $d$ is an isomorphism
from $G_e$ to $G$, and the composition of $f$ and $d$, that is, the
function that maps $v$ to $f(d(v))$, is the desired isomorphism from $G_e$
to $G_f$.}

\ppart Why don't I show the merchant an isomorphism between $G_e$ and $G$
\emph{and also} $G_e$ and $G_f$ instead of making him choose?

\solution{
If I showed him both isomorphisms then he could combine them to
find and an isomorphism between $G$ and $G_f$, and then he could forge my
signature.
}

\ppart Should I worry that a dishonest employee of the Discover card
company could forge my signature?

\solution{
The Discover card company doesn't know the isomorphism $f$ either, so
can't find an isomorphism between the published graphs any easier than
anyone else.  There might be a problem if an dishonest employee changed
the signature (replacing $G$ and $G_f$ with other graphs), but I could
protect myself against that by keeping a verifiable record of the
signature graphs I sent to the company.}

\ppart This signature scheme is a neat idea, but really it isn't any good
because \textbf{we don't know how to generate isomorphic graphs whose
isomorphism is hard to find}.  In fact, given a random pair of isomorphic
graphs, an isomorphism on average is easy to find.  However, there is a
fix, based on the fact that \emph{subgraph} isomorphism \emph{is} hard to
find on average.

The fix is that, instead of choosing a random isomorphism from $G$, I will
choose a random subset of 300 vertices of $G$, and let $G'$ be the
subgraph obtained by restricting to these 300 vertices and the edges
between them.  Now I proceed as before using $G'$ instead of $G$, to
obtain a graph, $G'_f$, isomorphic to $G'$.  I then ask the Discover card
company to publish the big, 1000 vertex graph, $G$, and the smaller, 300
vertex, $G'_f$.

Then as before, I convince the merchant I know an isomorphism from a
subgraph of my big published graph and my smaller published graph by
showing him a random $G_e$ isomorphic to my big graph, and asking him to
choose between either seeing an isomorphism between my big published graph
and $G_e$, or else seeing an isomorphism between my small published graph
and a \emph{subgraph} of $G_e$.  This revised protocol has all the desired
properties and will really work.

Of course, I could alternatively have decided to show the merchant a
random $G'_e$ isomorphic to my \emph{small} published graph, and then
let him choose to see an isomorphism between my small published graph and
$G'_e$, or between a subgraph of my big published graph and $G'_e$.
But if I did this, he could forge my signature!  Explain.

\solution{If I showed him the isomorphism between $G'_e$ and a subgraph
of my big published graph, he would know exactly where there was a
subgraph of my big graph that was isomorphic to my smaller graph.  Since
graph isomorphism is easy, he could then find an explicit isomorphism
between that subgraph of my big published graph and my smaller published
graph, which is the signature that I wanted to keep secret.}

\eparts
\end{problem}


\begin{problem}  \textbf{Extra Problem.}

\bparts \ppart\label{3t} Exhibit three nonisomorphic, connected graphs
with five vertices and four edges.

\ppart Argue that every connected graph with five vertices and four edges
is isomomorphic to one of the three in part~\eqref{3t}.

\eparts
\end{problem}


\iffalse
\instatements{\newpage}
\section*{Appendix}
\fi

\end{document}
