\section{$Strongly \; Universal_2$ and Authentification Code}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%%%%%%%%%%%%  Cours 9

A message authentification code (MAC) is essentialy a scheme where $Alice$ may
append a tag (a MAC) to a message in such a way that $Bob$ may verify the tag so 
as to  convince himself that $Alice$ was in fact the one that sent the message.
Since CBC and CFB modes propogate error, these can be used for MAC's.
We describe how $Alice$ can use CBC mode to produce a MAC for a message $m = x_1x_2 \ldots x_n$.  
$Alice$ begins by using an  $IV$ consisting of all zeroes. Then $Alice$ computes
the ciphertext $y_1y_2 \ldots y_n$ using CBC mode of operation with a secret key $K$
that she shares with $Bob$,  $y_n$ is the MAC.
Alice sends the plaintext $m$ along with the MAC $y_n$ to $Bob$.  When $Bob$ receives
the message with the tag, he can verify that $m$ was realy sent by $Alice$ by computing
$y_n$ the same way $Alice$ did, if the $y_n$ is the same as the MAC he received, he is
convinced that $Alice$ was the one that sent $m$.  $Bob$ is conviced since it would be
highly unlikely for $Oscar$ to produce a MAC since he does not know the key $K$ and since
modifying $m$ even slightly causes the MAC to be modified greatly.  Of cours, the security
relies in the trust of DES (or whatever block cipher algorithm beeing used).

\scalebox{0.5}{\includegraphics{L9.eps}}

%In section \ref{MAC}, we saw how to construct a MAC using a block cipher for authentification 
%purposes.  The weak point in the scheme described is that it's security relies on the block
%cipher algorithm in use (such as DES).

In this section, we will present an authentification code
that is unconditionaly secure.  The main results in this section come from \cite{WC81}.

\begin{definition}[$\SU{2}$\\]
Let $H$ is a set of hash functions from set $A$ to $B$.\\
$H$ is {\bf $\SU{2}$} if for all $a_1, a_2$, distinct elements of $A$,
and all $b_1,b_2$, elements (not necessarily distinct) of $B$, we have
     $$    |\{h \in H : h(a_1) = b_1, h(a_2) = b_2\}| = |H|/|B|^2 $$
 
\end{definition}

\begin{remark} An equivalent definition is the following,
$H$ is {\bf $\SU{2}$} if for any $h$ picked randomly (uniformaly) from $H$ we have that
\begin{enumerate}
  \item $\forall_{a \in A, b\in B}$ $ Pr[h(a) = b] = 1/|B|$ 
  \item $\forall_{a_1, \not= a_2 \in A, b_1, b_2 \in B} Pr[h(a_1)=b_1, h(a_2) = b_2] = 1/|B|^2 $
  \item $\forall_{a_1, \not= a_2 \in A, b_1, b_2 \in B} Pr[h(a_2)=b_2 | h(a_1) = b_1] = 1/|B| $
\end{enumerate}
\end{remark}

We need 1 and 3 for authentification.\\

The definition can be generalized
\begin{definition}[$\SU{n}$\\]
Let $H$ is a set of hash functions from set $A$ to $B$.\\
$H$ is {\bf $\SU{n}$} if for all $a_1, a_2,...,a_n$, distinct elements of $A$,
and all $b_1,b_2,...,b_n$, elements (not necessarily distinct) of $B$, we have
     $$    |\{h \in H : h(a_1) = b_1,...,h(a_n) = b_n\}| = |H|/|B|^n $$
\end{definition}

\begin{remark} If $H$ is $\SU{n}$ then it is $\SU{n-1}$
\end{remark}



\begin{example}
Let $A = B$ be a finite field.  Let $H$ be the class of polynomials of
degree 
less than $n$. $H$ is $\SU{n}$ since given any $n$ distinct elements of
 $A$ and corresponding elements of $B$, there is exactly one polynomial of 
degree less than $n$ which interpolates through the designated pairs.
\end{example}


We can create an authentification system that is unbreakable with
certainty $p$.  To do this, we simply choose $\T$ such that 
 $|\T| \geq 1/p$ and $F$ to be a $\SU{2}$ class of hash functions from
 $\Plain$ to $\T$.  Someone who sees $m \in \Plain$ and $t = f(m)$ knows
only that $f \in H'$ where $H' = \{g \in H \; | \; g(m) = t\}$, so then,
by definition of $\SU{2}$, guessing a correct function that maps an 
 $m' \not= m \in \Plain$ happens with probability $\leq p$ since only $1/|\T|$
functions from $H$ satisfy this property. \\
\\
The problem with this protocol is that all know $\SU{2}$ sets are very 
large (see \cite{GWS74} for such sets), and specifying a certain function
from these sets requires a key at least as long as the original message.
A second problem is that only one message can be sent with a certain key,
knowledge of two message-tag pairs may give information on the values
of the function of some third message.\\
We can do better than this.  We will first show a protocol that solves
the first problem, and then one that solves the second, both come from
\cite{WC81}.\\

We first define the following class:
 $$ H_2 = \{h: \F{q} \map \F{q} | h(a) = ia + j \; for some \, i, j \in \F{q}\} $$

here,  $A = B = \F{q} $, $|A| = |B| = q$, $|H| = q^2$.

\begin{theorem}  $H_2$ is $\SU{2}$.
\end{theorem}

\begin{proof}\\
Consider $a \not= a'$, and a $b$ and $b'$, \\
$
\begin{array}{clcr}
& &  ia + j = b\\
&-&  \underline{ia' + j = b'}\\
& &  i(a-a') = (b-b') \\
\end{array}
$\\


 $\implies i=(b-b')(a-a')^{-1}$  (we are in a field: $(a-a')$ exists and is unique) \\
and so $j = b - ia$

These unique values of $i$ and $j$ define a unique $h$ such that $h(a) = b$.\\
We thus have that
$$\forall_{a \not= a', b,b'} \{h : \, h(a)=b, h(a') = b' \} = 1 = |H_0|/|B|^2 $$
\end{proof}

We now define
$$H_{cut} = \{h: \F{2^m} \map \F{2^n} | h(a) = (ia + j)_{[last \, n \, bits]} , \; i,j \in \F{2^m}\}$$

here $A = \F{2^m}, |A| = 2^m$ and $B = \F{2^n}, |B| = 2^n$

\begin{theorem} $H_{cut}$ is $\SU{2}$.      
\end{theorem}

\begin{proof} 
We leave the proof to the reader.
\end{proof}

We will construct a class $H^*$ of fuctions that map from $A^*$ to $B^*$.
Let $w = |B^*| + log \, log(|A^*|)$. Each member of $H^*$ will be constructed from
a sequence of $log(|A^*|) - log(|B^*|)$ functions of ${H'}_{cut}$ and one function 
from ${H''}_{cut}$, where \\
 $${H'}_1 = \{h: \F{2^{2w}} \map \F{2^w} | h(a) = (ia + j)_{[last \, w \, bits]} , \; i,j \in \F{2^{2w}}\}$$
 ${H'}_{cut}$ is a specific instance of the classes of the form $H_{cut}$, here we are using 
 ${A'}_1= \F{2^{2w}}, {B'}_1= \F{2^{w}}$ so that $|{A'}_1| = 2^{2w}, |{B'}_1| = 2^w$ 
 and thus  $|{H'}_{cut}| = 2^{4w}$\\
 and $${H''}_{cut} = \{h: \F{2^{n + log \, log(m)}} \map \F{2^n} | h(a) = (ia + j)_{[last \, n \, bits]} ,
        \; i,j \in \F{2^{n + log \, log(m)}}\}$$
 with ${A'}_1= \F{2^{n + log \, log m}}, {B'}_1= \F{2^{n}}$ so that $|{A'}_1| = 2^{n + log \, log m} = 2^w, |{B'}_1| = 2^{n}$. \\
 $H^*$ will be almost $\SU{2}$ and we will use it for authentification schemes where
 $\Plain = A^*$ and $\T = B^*$.\\

We explain how to apply a function $f \in H^*$, defined by \\
 $\{ f_1, f_2,..., f_l | f_is \, are \, from \, {H'}_{cut} \, and \; l = log(|A^*|) - log(|B^*|) \}$, 
to an element $m \in A^*$:  We start by breaking the message $m$ in blocks of size $2w$
(padd the last block with blanks if necessary).  We then apply $f_1$ each block and
concatenate the results.  This gives us a word of size $|m|/2$.  We repeat the process
with $f_2, f_3, ...., f_l$. It is easily seen that after applying $f_i$ to the blocks and
concatenating the result, we get a message of size $|m|/2^i$, so after applying $f_l$
we end-up with a message of length $w$ (this explains the choice of $l$). Finally, we apply
 $f_{l+1}$ to this last substring, obtaining the result $f(m)$ (the 
{\it tag} if used as an authentification scheme).

\begin{theorem}
We want to proove that for an $h$ picked at random (uniform) from $H^*$ we have that\\
\begin{enumerate}
\item
 $\forall_{x_0 \in A^*, y \in B^*} Pr[f(x_0) = y] = 1/|B^*|$
\item 
 $\forall_{x_0 \not= {x'}_0, y, y'} Pr[f({x'}_0) = y' | f(x_0) = y ] \leq 2/|B|$
\end{enumerate}
(this will prove that $H^*$ is ``almost'' $\SU{2}$)
\end{theorem}

\begin{proof}

 $1.$ is easy because $\forall_{x_0 \in A^*, y \in B^*}  Pr(f(x_0) = y) = Pr(h_{l+1}(x_l) = y) = 1/|B^*| = 1/2^n$
 ($h_{l+1} \in {H''}_{cut}: \F{2^w} \map B^*$ and ${H''}_{cut}$ is $\SU{2}$).


 $2. $ will be proved by examining two possible cases:\\

 (case $1$)  $ y \not = y'  \; (\implies x_l \not x_l')$\\
\begin{eqnarray*}
   Pr(f(x_0') = y' | f(x_0) = y) & = & Pr(x_l' \not = x_l | x_o' \not = x_0) \, 
                                        Pr(h_{l+1}(x_l') = y' | h_{l+1}(x_l) = y) \\
                                & \leq & Pr(h_{l+1}(x_l') = y' | h_{l+1}(x_l) = y) \\
                                & = & 1/|B| \\
  \end{eqnarray*}

  (case $2$) $y = y'$\\
\begin{eqnarray*}
   Pr(f(x_0') = y | f(x_0) = y) & \leq & \underbrace{Pr(x_l' = x_l)}_{\leq 1/2^n \; *} + 
                                         Pr(h_{l+1}(x_l') = y |h_{l+1}(x_l) = y) \; Pr(x_l' \not = x_l)\\
                                & \leq & 1/|B^*| + 1/|B^*| = 2/|B^*| \\ 
\end{eqnarray*}

\begin{eqnarray*}
    *: \; Pr(x_l' = x_l | x_0' \not = x_0) & = & Pr(x_1' = x_1 | x_0'\not= x_0) +
                                          Pr(x_l'=x_l|x_1' \not= x_1) \; Pr(x_l'\not=x_l|x_0'\not= x_0) \\
                                           & \leq & Pr(x_1' = x_1|x_0' \not= x_0) +
                                                    Pr(x_l' = x_l | x_1' \not= x_1) \\
                                           & \leq & \sum_{i=1}^l Pr(x_i'=x_i|x_{i-1}'\not= x_{i-1}) \; (recursion) \\
                                           & \leq & l \; 1/2^w  \\
                                           & \leq & lg \, (|A^*|)  / 2^w \; (l = log(|A^*|) - log(|B^*|)) \\
                                           & = &    lg \,(|A^*|) / (|B^*| + lg \, lg \,(|A^*|))  \\
                                           & = & lg \,(|A^*|) / (|B^*| lg\,(|A^*|)) \\
                                           & = & 1/|B^*| \; (this \; explains \; the \; choice \; of \; w) \\
\end{eqnarray*}
\end{proof}


\subsection{Multiple Messages}
Using the above method, if an adversary sees two message-tag pairs, he may be able to 
determine more such pairs (by solving linear equations). One way around the problem
is to use $\SU{n}$ functions, so that we can send $n-1$ messages.  But there is a more
elegant way:   Let $F$ be a $\SU{2}$ set of functions from $A$ to $B$. To each message in
 $M$ that we send, we append an unique number $i$ between $1$ and $n$.  The sender ($Alice$) 
randomly choses a $f \in F$ and randomly choses $n$, $log \, |B|$ sized,
one-time pads $b_1, b_2,..., b_n$.  She secretly shares these values $(f, b_1, b_2,...,b_n)$
with the receiver ($Bob$).  To create a tag $t_i$ for message $m_i$ (a message with $i$
appended in front of it), $Alice$ computes $f(m_i) \xor b_i$.  When $Bob$ receives a
message $i \| m$ with a tag $t_i$, he accepts it iff $t_i \xor b_i = f(i \| m)$.

\begin{theorem}
  In the context of the above protocol, an adversary knowing only the set $F$ and $n$ pairs 
 $(m_1, t_1), (m_2, t_2),...,(m_n, t_n), m_i \not = m_j$ for $i \not j$, cannot create a tag
 $\bar{t_i}$ for a different message $\bar{m_i}$ (containing $i$ at the beginning) with probability
 of success greater then $1/|B|$
\end{theorem}

\begin{proof}
  The proof is left to the reader.
\end{proof}

