In this paper we consider some properties of stream ciphers related to arithmetical dynamical systems defined in [41] over commutative ring K. We modify the stream cipher algorithm proposed in [40] by adding the key management block based on the idea of “hidden discrete logarithm”. The straightforward generalization of such encryption can be used in a public key mode. We introduce much more general algorithms in terms of automata related to Directed Algebraic Graphs with High Girth Indicator. In finite case we use only directed graphs of irreflexive binary relations such that numbers of inputs and outputs are the same for each node (balanced directed graphs). The families of such regular graphs of bounded degree with growing girth indicator and the size which is close to the maximal possible value (or order close to minimum) can be used for the design of encryption algorithm. One of the important parameters of the Turing machine related to the family is the speed of growth of the girth indicator. Natural upper bound for such speed can be obtained in terms of Extremal graph theory for balanced directed graphs which is motivated be Erdös’ Even Circuit Theorem which bounds the size of a simple graph without even cycle. Explicit constructions of such families can be used not only in Cryptography but in the Coding Theory as well.

The family of infinite algebraic directed graphs with the large girth indicator can be defined over infinite commutative ring K. Some theoretical examples of encryption algorithms related to such families are considered in the case of K = Z and Gaussian complex numbers. They use prime generating polynomials (Matijasevic’s polynomials) and can be implemented on classical Turing machine or Probabilistic machine (Quantum computer, in particular).