On the extremal graph theory for directed graphs and its cryptographical applications
The paper is devoted to the graph based cryptography. The girth of a directed graph (girth indicator) is defined via its smallest commutative diagram. The analogue of Erdøos's Even Circuit Theorem for directed graphs allows to establish upper bound on the size of directed graphs with a fixed girth indicator. Size of members of infinite family of directed regular graphs of high girth is close to an upper bound.
Finite automata related to members of such a family of algebraic graphs over chosen commutative ring can be used effectively for the design of cryptographical algorithm for different problems of data security (stream ciphers, data base encryption, public key mode an digital signatures).
The explicit construction of infinite family of algebraic graphs of high girth defined over the arbitrarily chosen ring is given. Some results on their properties, based on theoretical studies or software implementations are given.