Return to reliable.tex CVS log

Up to [local] / OpenXM / doc / calc2000p

Annotation of OpenXM/doc/calc2000p/reliable.tex, Revision 1.2

1.2     ! noro        1: % $OpenXM: OpenXM/doc/calc2000p/reliable.tex,v 1.1 2000/07/22 08:11:09 noro Exp $
1.1       noro        2: \documentclass{slides}
                      3: \usepackage{color}
                      4: \usepackage{rgb}
                      5: %{\color{red} Asir}
                      6: \begin{document}
                      7: \parskip 5pt
1.2     ! noro        8: \fbox{{\large \color{blue} Reliable Computation with OpenXM}}
        !             9: \vskip 3pt
1.1       noro       10: {\color{red} Compute GB on a client $\Rightarrow$ Verify it on a server}
                     11:
                     12: {\color{red} $\{g_i\}$ is a GB of $\{f_j\}$}
                     13: $\Leftrightarrow$ $\{g_i\}$ is a GB (trivial)\\
                     14: and {\color{green} $\{g_i\}$ is generated by $\{f_j\}$ (non trivial)}.
                     15:
                     16: \vskip 10pt
                     17:
                     18: {\color{red} Check of the generation}\\
                     19: Find {\color{turquoise} polynomials} $c_j$ s.t.$g_i = \sum c_jf_j$ : {\color{red} hard}.
                     20:
                     21: {\color{orange} Alternatively}
                     22:
                     23: $\{h_k\}$ : intermediate bases ($\{f_j\}, \{g_i\}\subset \{h_k\}$)\\
                     24: Find {\color{turquoise} monomials} $m_l$ s.t. $h_k = \displaystyle{\sum_{l<k} m_l h_l}$ : {\color{SeaGreen} trivial}.
                     25:
                     26: \medbreak
                     27:
                     28: \begin{tabbing}
                     29: {\color{red} Verification}\\
                     30: After each normal form computation,\\
                     31: {\color{green} Client} \=: \= sends a list $\{h,\{l_1,m_1\},\ldots,\{l_s,m_s\}\}$.\\
                     32: \>\>where $h$ is the normal form.\\
                     33: {\color{green} Server}  \>: \> checks whether  $h=\sum m_k h_{l_k}$, then\\
                     34: \>\> registers $h$ as a new basis element.
                     35: \end{tabbing}
                     36:
                     37: \medbreak
                     38:
                     39: {\color{red} Implementation of the verifier} : {\color{SeaGreen}easy}\\
                     40: \quad It requres only polynomial arithmetics.
                     41:
                     42: {\color{red} Reliability} : {\color{SeaGreen} higher than simple double check}
                     43: \vskip 20pt
                     44: \rightline{ {\color{red} {\tt http://www.openxm.org} }}
                     45: \end{document}