documentclass[12pt,a4paper]{article}




\textheight 22cm \textwidth 14.5cm \oddsidemargin 1cm \topmargin
-0.5cm



\begin{document}

\title{On Algebraic Directed Graphs and
 Polynomial Public Key Cryptography}

\author{A. Wroblewska}

\date{University of Maria Curie Sklodowska, Lublin, Poland}

\maketitle


The girth of the simple graph is the length of its smallest cycle.
Let   $ex(v, C_3, C_4, \dots, C_n)$ be the maximal value size
 (number of edges)
of a
graph on $v$ vertices
of the girth $>n$.

According to the well known Even Circuite Theorem $ex(v, C_3, C_4, \dots, C_n)= O(v^{1+1/[n/2]})$.
This bound is known to be sharp for $n=2, 3$ and 5 only.

The  best general lower bounds of kind

$ex(v, n) \ge C(v^{1+c/([n/2])})$   (1),

where $c\le 1$ and $C$ are positive constant had been obtained in
[1] ($c \ge 3/4$). The infinite sequence of $k$-regular simple
graphs
 is a family of large graphs if its  size evaluated from  below by

The examples of algebraic graphs of large girth from [1] were used
in [2]  for the construction of polynomial public key maps
${F_q}^n$ onto itself  of kind $x_1 \rightarrow g_1(x_1, x_2,
\dots, x_n), x_2 \rightarrow g_2(x_1, x_2, \dots, x_n), \dots, x_n
\rightarrow g_n(x_1, x_2, \dots, x_n)$

In [5] we proved that degree of each $g_i$ is 3 independently on
the size of the map.

In the paper [3] the concept of the family of directed graphs of
large girth had been introduced together with examples of such a
families defined over finite commutative rings $K$. Such examples
were used for the construction of several polynomial public maps
of $K^n$ onto itself.

We announce here that the degrees of that  keys maps are bounded
by 4. It means that the rules as above are feasible for the public user.

REMARK. The security of algorithms are bounded from below by the
complexity of discrete logarithm problem for the affine algebraic
group of graph automorphisms [4].





\renewcommand{\refname}{\vspace{-12mm}}
\begin{thebibliography}{99}
\small\itemsep=0pt

\bibitem{1} F. Lazebnik, V. A. Ustimenko and A. J. Woldar, {\em A
New Series of Dense Graphs of High Girth}, Bull (New Series) of
AMS, v.32, N1, (1995), 73-79.

\bibitem{2} V. Ustimenko, {\em   Maximality of affine group and hidden graph
cryptsystems}, Journal of Algebra and Discrete Mathematics,
October, 2004, v.10, pp. 51-65.


\bibitem{3} V. Ustimenko, {\em On the cryptographical properties
 of extremal algebraic graphs}, in T. Shaska, E. Hasimaj (editors),
Algebraic Aspects of Digital Communications, Volume 24, NATO Science for Peace and
Security Series - D: Information and Communication Security, IOS Press,
July 2009.

\bibitem{4} V. Ustimenko, {\em On some results of Extremal Digraph
theory and their applications to Information Security}, Proceedings
of the 9th Central European Conference on Cryptology (to appear)

\bibitem{5} A. Wroblewska, {\em On some properties of  graph based public key}, Albanian J. Math.,
vol. 2, No 3 (2008), Special Issue "New Challenges of Digital
Communications", Proc. of NATO Advanced Studies Institute, Vlora,
2008, pp. 229-234.

\end{thebibliography}
\noindent
\end{document}