% $OpenXM: OpenXM/doc/calc2000p/reliable.tex,v 1.1 2000/07/22 08:11:09 noro Exp $
\documentclass{slides}
\usepackage{color}
\usepackage{rgb}
%{\color{red} Asir}
\begin{document}
\parskip 5pt
\fbox{{\huge \color{blue} We Are Reliable}}

{\color{red} Compute GB on a client $\Rightarrow$ Verify it on a server}

{\color{red} $\{g_i\}$ is a GB of $\{f_j\}$} 
$\Leftrightarrow$ $\{g_i\}$ is a GB (trivial)\\
and {\color{green} $\{g_i\}$ is generated by $\{f_j\}$ (non trivial)}.

\vskip 10pt

{\color{red} Check of the generation}\\
Find {\color{turquoise} polynomials} $c_j$ s.t.$g_i = \sum c_jf_j$ : {\color{red} hard}.

{\color{orange} Alternatively}

$\{h_k\}$ : intermediate bases ($\{f_j\}, \{g_i\}\subset \{h_k\}$)\\
Find {\color{turquoise} monomials} $m_l$ s.t. $h_k = \displaystyle{\sum_{l<k} m_l h_l}$ : {\color{SeaGreen} trivial}.

\medbreak

\begin{tabbing}
{\color{red} Verification}\\
After each normal form computation,\\
{\color{green} Client} \=: \= sends a list $\{h,\{l_1,m_1\},\ldots,\{l_s,m_s\}\}$.\\
\>\>where $h$ is the normal form.\\
{\color{green} Server}  \>: \> checks whether  $h=\sum m_k h_{l_k}$, then\\
\>\> registers $h$ as a new basis element.
\end{tabbing}

\medbreak

{\color{red} Implementation of the verifier} : {\color{SeaGreen}easy}\\
\quad It requres only polynomial arithmetics.

{\color{red} Reliability} : {\color{SeaGreen} higher than simple double check}
\vskip 20pt
\rightline{ {\color{red} {\tt http://www.openxm.org} }}
\end{document}