On the complexity of analysis of automata over a finite ring
- PDF / 167,992 Bytes
- 13 Pages / 595.276 x 793.701 pts Page_size
- 58 Downloads / 183 Views
ON THE COMPLEXITY OF ANALYSIS OF AUTOMATA OVER A FINITE RING V. V. Skobeleva† and V. G. Skobeleva‡
UDC 519.713+512.552
Abstract. A general scheme is investigated that is destined for obtaining estimates based on the cardinality of subsets of a fixed set of automata over some finite commutative-associative ring with unit element. A scheme is proposed to solve parametric systems of polynomial equations based on classes of associated elements of the ring. Some general characteristics of automata over the ring are established. Keywords: finite automaton, finite ring, symmetric stream cipher. INTRODUCTION Despite a wide variety of mathematical models (frequently incomparable with one another) that are recently used in cryptography, a stable trend has been outlined that lies in the passage from purely combinatorial models to mathematical models constructed on the basis of finite algebraic systems. At the same time, numerous attempts of direct application of chaotic dynamic systems [1] to the solution of cryptographic problems have shown that, in this case, the problem arises that consists of the choice of the accuracy of computations that provides the correctness of the process “enciphering–deciphering.” From the mathematical viewpoint, its solution is not very complicated for piecewise linear chaotic mappings [2, 3]. However, even for concrete types of nonlinear chaotic dynamic systems, the solution of this problem is not found yet. A natural way of avoiding errors connected with rounding is the passage (in equations specifying a chaotic dynamic system) to operations in a finite algebraic system. The mentioned factors have recently stimulated an interest in the investigation of automata represented by systems of equations over finite algebraic systems. The fundamentals of the theory of linear automata over a field GF ( p k ) (where p is a prime number, k Î N) from the position of the theory of systems are developed almost 40 years ago [4, 5]. However, these investigations have not produced efficient results for the solution of problems of cryptography by virtue of the following reasons. The property “to be a linear automaton” imposes essential constraints on the automaton mapping realized by an initial automaton (apparently, the most significant application of linear autonomous automata is their use as generators of pseudorandom sequences). In [4, 5], problems that would substantiate the computational resistance of stream ciphers constructed on the basis of automata over a field GF ( p k ) are not considered from the viewpoint of the theory of algorithms. Such problems form a special line of investigations in the theory of experiments with automata (some types of experiments with automata over finite fields are considered in [6–8]). The subject of its investigation is the analysis of complexity of identification of parametrically adjustable reversible automata, sets of fixed points of the mapping realized by an initial reversible automaton, and also changes in the behavior of a reversible automaton with varying its pa
Data Loading...
