Abstract
Cellular automata (CA) is universally known as very good pseudorandom sequence generator. It has wide applications in several fields like VLSI design, error-correcting codes, test pattern generation, cryptography etc. Most of these applications use 3-neighborhood one dimensional CA. Cellular automata have been chosen as a better crypto-primitives for providing very good pseudorandom sequences and their high diffusion property. The randomness and diffusion properties can be increased with the increase of the size of neighborhood radius of the CA cell. In this work, we study a class of 5-neighborhood null boundary linear CA. We present an algorithm for synthesizing 5-neighborhood linear CA from its characteristic polynomial by assuming that some of the CA sub-polynomials are available.
Access provided by CONRICYT-eBooks. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Cellular Automata (CA) have long been of interest to researchers for their theoretical properties and practical applications. It was initiated in the early 1950’s by John von Neumann [12] and Stan Ulam as a general framework for modeling complex structures capable of self-reproduction and self-repair. In 1986, Wolfram first applied CA in pseudorandom number generation [15]. CA has made understanding of many occurrences in nature easier. The simple and regular structure of CA has attracted researchers and practitioners of different fields. In the last two decades, one-dimensional (1-D) CA based Pseudorandom Number Generators (PRNGs) have been extensively studied [2, 5, 10, 11]. Though the recent interest is more focused on two-dimensional (2-D) CA PRNGs [9, 13] since it seems that their randomness is much better than that of 1- D CA PRNGs, but considering the design complexity and computation efficiency, it is quite difficult to conclude which one is better. Compared to 2-D CA PRNGs, 1-D CA PRNGs are easier to be implemented in a large scale [3, 8, 14]. Random bit generators play an important role in different computer simulation methods such as Monte Carlo techniques, Browmian dynamics, stochastic optimization, computer-based gaming, test pattern generation for VSLI circuit test, error-correcting codes, image processing, neural networks and cryptography etc. Most of these works are devoted to the study of cellular automata as pseudorandom bit generators. A central problem in any stream cipher scheme is to generate long, unpredictable random key sequences and Cellular Automata resolves this problem.
In most of all these applications, 1-D elementary cellular automata (i.e. three-neighborhood CA) are used. There are also some applications [6, 9, 13] of five or more neighborhood 2-D CA but that need more hardware complexity. In [7], it has been shown a 4-neighborhood nonlinear 1-D CA as a better cryptographic primitive. The randomness and diffusion properties of the CA can be developed with the increase of the size of neighborhood radius of the CA cell. More diffusion property of CA can make fast initialization of a stream cipher. In this paper, we study 5-neighborhood linear 1-D CA for providing very good pseudorandom sequences and high diffusion. We present an algorithm for synthesizing the CA.
This paper is organized as follows. Following the introduction, the basics of CA are presented in Sect. 2. In Sect. 3, we present 5-neighborhood Linear Hybrid Cellular Automata with the CA transition matrix and the characteristic polynomial. A recurrence relation is introduced for determining the characteristic polynomial and a CA synthesis algorithm is presented. We also present the randomness and diffusion properties of 5-neighborhood CA rule vectors and the comparison of their properties with 3/4 neighborhood CA. Finally, the paper is concluded in Sect. 4.
2 Basics of Linear Cellular Automata
Cellular Automata are studied as mathematical model for self organizing statistical systems [12]. CA can be one-dimensional or multi-dimensional. One-dimensional CA random number generators have been extensively studied in the past [4, 11, 15]. In one-dimensional CA, they can be considered as an array of cells where each cell is a one bit memory element. The neighbor set N(i) is defined as the set of cells on which the state transition function of the i-th cell is dependent on each iteration. In three-neighborhood CA, each cell evolves in every time step based on some combinatorial logic on the cell itself and its two nearest neighbors. More formally, for a three-neighborhood CA, the neighbor set of i-th cell is defined as \(N(i) = \{s_{i-1}, s_i, s_{i+1}\}\). The state transition function of is i-th cell of 3-neighborhood CA is as follows:
where, \(s_i^{t}\) denotes the current state of the i-th cell at time step t and \(s_i^{t+1}\) denotes the next state of the i-th cell at time step t+1 and \(f_i\) denotes some combinatorial logic for i-th cell. The set of all feedback functions is considered as ruleset for the CA. Since, a three-neighborhood CA having two states (0 or 1) in each cell, can have \(2^3 = 8\) possible binary states, there are total \(2^{2^3} = 256\) possible boolean functions, called rules. Each rule can be represented as an decimal integer from 0 to 255. If the combinatorial logic for the rules have only Boolean XOR operation, then it is called linear or additive rule. Some of the three-neighborhood additive CA rules are 0, 60, 90, 102, 150 etc. Moreover, if the combinatorial logic contains AND/OR operations, then it is called non-linear rule. An n cell CA with cells \(\{s_1, s_2,\cdots , s_n\}\) is called null boundary CA if \(s_{n+1} = 0\) and \(s_0 = 0\). Similarly for a periodic boundary CA \(s_{n+1} = s_1\). A CA is called uniform, if all its cells follow the same rule. Otherwise, it is called non-uniform or hybrid CA. If all the ruleset of a hybrid CA are linear, then we call the CA a linear one. However, out of all possible Boolean functions, called rules, only two are of prime interest i.e. Rule 90 and 150 (ascertained from the decimal value of their position in the truth table). The state of the i-th cell at time instant t can be expressed as:
Thus, an LHCA can be completely specified by a combination of Rule 90 and 150, denoted as an n-tuple \( [d_1, d_2,\cdots , d_n] \). An example of a 5-cell CA \(\mathcal {L}\) can be found in Fig. 1, specified by the rule vector [1, 1, 1, 1, 0]. Further details of CA can be found in [4].
3-neighborhood null boundary LHCA \(\mathcal {L}\) with rule vector [1, 1, 1, 1, 0]
3 5-Neighborhood Linear Cellular Automata
In the previous section, we have studied 1D elementary CA (i.e. 3-neighborhood CA) [4, 11]. In this section, we consider a 5-neighborhood null boundary n-cell Linear Hybrid CA (LHCA) denoted by \(\{s_1, s_2, \cdots , s_n\}\), where the state of a cell at a given instant is updated based upon its five neighboring cells including itself and because of null boundary \(s_{-1}=s_0=0\), \(s_{n+1}=s_{n+2}=0\). More formally, for a five-neighborhood CA, the neighbor set of i-th cell is defined as \(N(i) = \{s_{i-2}, s_{i-1}, s_i, s_{i+1},s_{i+2}\}\). The state transition function of is i-th cell of 5-neighborhood CA is as follows:
where, \(s_i^{t}\) denotes the current state of the i-th cell at time step t and \(s_i^{t+1}\) denotes the next state of the i-th cell at time step t+1 and \(f_i\) denotes some combinatorial logic for i-th cell. Since, a 5-neighborhood CA having two states (0 or 1) in each cell, can have \(2^5 = 32\) possible binary states, there are total \(2^{2^5} = 2^{32}\) possible boolean functions. Out of all possible Boolean functions, called rules, there are total \(2^5 = 32\) possible linear rules. Based on neighborhood radius exactly 5, there are only \(2^3 = 8\) liner rules shown in Table 1.
For all possible pair of these 8 linear rules, maximum period 5-neighborhood CA rule vectors can be obtained. Table 2 shows the number of rule vectors obtained for maximum period 5-bit 5-neighborhood CA against each pair of the linear rules shown in Table 1. From Table 2, we see that only the pair of rule combinations, (\(Rule_5\), \(Rule_7\)), provides largest number of rule vectors (i.e. 8). Therefore, we consider these two linear rules (i.e. \(Rule_5\), \(Rule_7\)), denoted as \(R_0\) and \(R_1\), respectively, to design 5-neighborhood LHCA. These two linear rules can again be specified as follows:
where, \(s_i^t\) is the current state and \(s_i^{t+1} \) is the next state of the i-th cell of the CA. Thus, the state transition function of i-th cell of the CA can be expressed as:
Thus, a five-neighborhood n-cell LHCA \(\mathcal {L}\) denoted by \(\{s_1, s_2, \cdots , s_n\}\), can be completely specified by a combination of these two rules \(R_0\) and \(R_1\), denoted as an n-tuple \( [d_1, d_2,\cdots , d_{n}]\), called the rule vector of the CA. An example of a 5-cell null boundary 5-neighborhood CA can be found in Fig. 2, specified by the rule vector [1, 1, 1, 0, 0].
5-neighborhood null boundary LHCA \(\mathcal {L}\) with rule vector [1, 1, 1, 0, 0]
A five-neighborhood n-cell LHCA \(\mathcal {L}\) can be characterised by an \(n\times n\) matrix, called characteristic matrix. The characteristic matrix A for the n-cell CA rule vector \( [d_1, d_2,\cdots , d_{n}]\) is as follows:
The state of a CA at time step t is an n-tuple formed from the states of the individual cells. The CA state is expressed in matrix form as follows
The next state of the CA is denoted as
The next-state of the CA, \(S^{t+1}\), is computed as
where, A is the CA transition matrix and \((S^{t})^T=[s_1^{t},\cdots ,s_n^{t}]^T\) (the superscript T represents the transpose of the vector) and the product is a matrix-vector multiplication over GF(2). It has been shown that \(A\cdot (S^{t})^T\) is indeed the next state of the CA. Therefore, the next state of the \(i^{th}\) cell is computed as the product of the \(i^{th}\) row of A and \((S^{t})^T\) as follows:
The characteristic polynomial \(\varDelta _n\) of the n-cell CA is defined by
where, x is an indeterminate, \(\mathcal {I}\) is the identity matrix of order n, and A is the CA transition matrix. The matrix \(x\mathcal {I}-A\) is called the characteristic matrix of the CA. The characteristic polynomial is a degree n polynomial in x.
The following example clearly illustrates how the characteristic polynomial of a 5-neighborhood linear CA can be computed using the characteristic matrix of the CA.
Example 1: Let us consider a 5-cell null boundary 5-neighborhood linear CA with the rule vector [1, 1, 1, 0, 0]. We have \([d_1, d_2, d_3, d_4, d_5]=[1, 1, 1, 0, 0]\). The transition matrix A is as follows:
The corresponding characteristic matrix is as follows:
where, x is an indeterminate, \(\mathcal {I}\) is the identity matrix with dimension 5, and A is the CA transition matrix shown above. The characteristic polynomial \(\varDelta _5\) of the 5-cell CA is defined as follows:
Theorem 1
Let \(\varDelta _n\) be the characteristic polynomial of a n-cell null boundary 5-neighborhood Linear CA with rule vector \( [d_1, d_2,\cdots , d_{n}]\). \(\varDelta _n\) satisfies the following recurrence relation:
Proof: Consider the transition matrix A for the n-cell null boundary 5-neighborhood Linear CA with rule vector \( [d_1, d_2,\cdots , d_{n}]\)
The characteristic polynomial \(\varDelta _n\) of the CA is defined by
By expanding the determinant shown above with respect to the last row, we can compute \(\varDelta _n\) as follows: \(\varDelta _n=(x+d_n)*\varDelta _{n-1}+1*B+1*C\), where B and C with dimension \((n-1)\times (n-1)\) are as follows:
and
By expanding the determinant B with respect to the last column, we can compute B as follows: \(B=\varDelta _{n-2}+D\), where D with dimension \((n-2)\times (n-2)\) is as follows:
By expanding the determinant C with respect to the last column, we can compute C as follows: \(C=E+F\), where E and F with dimension \((n-2)\times (n-2)\) are as follows:
and
By expanding the determinant F with respect to the last column, we can compute F as follows:
Note that the determinant E can be easily found by changing rows into columns and columns into rows of the determinant D, therefore, D and E determines the same polynomial and so, D+E determines zero in GF(2). Finally, we have
Theorem 1 provides an efficient algorithm to compute the Characteristic polynomial of a CA. Initially, \(\varDelta _{-3}\), \(\varDelta _{-2}\), \(\varDelta _{-1}\) are all set to zero and \(\varDelta _0\) is set to one. Equation (1) is applied to obtain \(\varDelta _1\). It is then reapplied to calculate \(\varDelta _2\) from \(\varDelta _{-2}\) to \(\varDelta _1\), Continuing, the polynomials \(\varDelta _3,\varDelta _4,\cdots ,\varDelta _n \) are computed.
The following example clearly illustrates how the characteristic polynomial of a 5-neighborhood linear CA can be computed using the recurrence relation shown above. Table 3 shows characteristic polynomials of a 5-cell null boundary 5-neighborhood linear CA.
Example 2: Let us consider a 5-cell null boundary 5-neighborhood linear CA with the rule vector [1, 1, 1, 0, 0]. We have, \([d_1, d_2, d_3, d_4, d_5]=[1, 1, 1, 0, 0]\)
3.1 Synthesis of 5-Neighborhood Linear CA
In this section, we present an algorithm Algorithm 1 for synthesizing 5-neighborhood CA from its characteristic polynomial.
Explanation: Suppose, \(\varDelta _{n-1}\), \(\varDelta _{n-2}\) and \(\varDelta _{n-3}\) are known. Here, all operations are done in GF(2). We consider the recurrence relation:
Now, we follow the Table 4. In the step 1, \(\varDelta _n\) and \(\varDelta _{n-1}\) are known. By the polynomial division algorithm, considering \(\varDelta _n\) as dividend and \(\varDelta _{n-1}\) as divisor, the degree 1 quotient polynomial \((x+d_n)\) is uniquely determined and easily calculated; since, the remainder polynomial in the relation (i.e. \(\varDelta _{n-2}+(x+d_{n-1})\varDelta _{n-3}+\varDelta _{n-4}\)) is of degree less than \(n-1\). In the step 2, \(\varDelta _n\), \(\varDelta _{n-1}\), \(\varDelta _{n-2}\) and \(\varDelta _{n-3}\) are known. In the above relation, the polynomial \(\varDelta _n+(x+d_n)\varDelta _{n-1}+\varDelta _{n-2}\) is of degree \(n-2\). Now, if the polynomial division algorithm is again applied considering \(\varDelta _n+(x+d_n)\varDelta _{n-1}+\varDelta _{n-2}\) as dividend and \(\varDelta _{n-3}\) as divisor then, it will calculate \((x+d_{n-1})\) as quotient and \(\varDelta _{n-4}\) as remainder from the above relation. In the step 3, we consider the relation:
Now, \(\varDelta _{n-1}\), \(\varDelta _{n-2}\), \(\varDelta _{n-3}\) and \(\varDelta _{n-4}\) are known and \((x+d_{n-1})\) is also known as it is computed in the previous step. If we apply the division algorithm considering \(\varDelta _{n-1}+(x+d_{n-1})\varDelta _{n-2}+\varDelta _{n-3}\) as dividend and \(\varDelta _{n-4}\) as divisor, it can calculate \((x+d_{n-2})\) as quotient and \(\varDelta _{n-5}\) as remainder from the above relation. In this way, if we proceed for n steps, then we get the sequence of degree 1 quotient polynomials as follows:
where \(d_k (1 \le k \le n)\) is either 0 or 1. By taking the constant terms of these quotient polynomials and reversing, we get the rule vector \([d_1, d_2, \cdots , d_n]\) for a 5-neighborhood LHCA with the characteristic polynomial \(\varDelta _n\). The total number of polynomial divisions performed is O(n), where, n is degree of the characteristic polynomial \(\varDelta _n\) of n-bit CA. Each polynomial division needs O(\(n^2\)) time. Therefore, the required time complexity for this algorithm is O(\(n^3\)).
3.2 Randomness of 5-Neighborhood Linear CA Rule Vectors
A statistical test suite is developed by National Institute of Standards and Technology (NIST) that is known as NIST-statistical test suite [1]. The NIST Test Suite is a statistical package consisting of 15 tests that were developed to test the randomness of (arbitrarily long) binary sequences produced by either hardware or software based cryptographic random or pseudorandom number generators. To test the randomness of 5-neighborhood linear CA rule vectors, we consider a 24-bit 5-neighborhood maximum period LHCA with rule vector
where \(d_i=0\) in the rulevector \([d_0, \cdots , d_{23}]\) represents that \(i^{th}\) cell of the CA follows rule \(R_0\) and \(d_i=1\) in the rulevector \([d_0, \cdots , d_{23}]\) represents that \(i^{th}\) cell of the CA follows rule \(R_1\). 100 bit-streams with each stream of 1,00,000 bits are generated from the middle cell (\(12^{th} cell\)) of this 24-bit LHCA and stored in a data file, and then the data file is fed to NIST test suite. The generated bit-streams show high randomness property as depicted in Table 5.
3.3 Diffusion Property of 5-Neighborhood Linear CA Rule Vectors
To test the diffusion property of 5-neighborhood linear CA rule vectors, we consider a 24-bit 5-neighborhood maximum period LHCA \([s_0, \cdots , s_{23}]\) with the same rule vector
as considered in the previous section, and some CA initial values and we notice the status of the CA cells in some clock cycles. The result of the CA states for some clock cycles is depicted in Table 6. The result shows that the diffusion rate of CA cell contents is 2 times faster than 3-neighborhood CA. For the sake of simplicity, the rule value of the CA is given in hexadecimal notation i.e. a CA rule value 0xA5 denotes the rule vector [1, 0, 1, 0, 0, 1, 0, 1] and a CA initial value 0xA5 denotes the CA value [10100101].
3.4 Comparison of Properties of 5-Neighborhood Linear CA with 3/4 Neighborhood Linear CA
In this section, we study the comparison of properties of 5-neighborhood linear CA with 3/4 neighborhood linear CA, shown in Table 7. Delay will obviously increase for 5-neighborhood CA with respect to 3-neighborhood CA. On the other hand, one clock cycle period is at least the time period required for one time CA evolving and the average diffusion rate for 5-neighborhood CA is 2 times faster than 3-neighborhood CA. Therefore, because of high diffusion rate, 5-neighborhood CA is also suitable for high speed application.
4 Conclusion
In this paper, we have studied 5-neighborhood null boundary linear CA with two linear rules. The characteristic polynomial has been realized from 5-neighborhood rule vector of the CA. We have presented an algorithm for synthesizing the 5-neighborhood CA from its characteristic polynomial by assuming some CA sub-polynomials. We have shown the randomness and diffusion properties of the 5-neighborhood CA rule vectors and the comparison of their properties with 3/4 neighborhood CA. At present, we are working on how the CA can be synthesized from its characteristic polynomial without the knowledge of CA sub-polynomials.
References
NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. U.S. Department of Commerce (2010)
Bardell, P.H.: Analysis of cellular automata used as pseudorandom pattern generators. In: Proceedings IEEE International Test Conference 1990, Washington, D.C., USA, 10–14 September 1990, pp. 762–768 (1990)
Bouganim, L., Guo, Y.: Database Encryption in Encyclopedia of Cryptography and Security, 2nd edn. Springer, New York (2010)
Chaudhuri, P.P., Roy Chowdhury, D., Nandi, S., Chattopadhyay, S.: Additive Cellular Automata: Theory and Applications. IEEE Computer Socity Press, New York (1997)
la Guaz-Martinez, D., Fuster-Sabater, A.: Cryptographic design based on cellular automata In: Proceedings of IEEE International Symposium on Information Theory, p. 180 (1997)
Ikenaga, T., Ogura, T.: Real-time morphology processing using highly parallel 2-D cellular automata. IEEE Trans. Image Process. 9(12), 2018–2026 (2000)
Jose, J., Roy Chowdhury, D.: Four neighbourhood cellular automata as better cryptographic primitives. IACR Cryptology ePrint Archive 2015, 700 (2015)
Kumar, K.J.J., Sudharsan, S., Karthick, V.: FPGA implementation of cellular automata based stream cipher: Yugam-128. IJAREEIE 3 (2014)
Tomassini, M., Sipper, M., Perrenoud, M.: On the generation of high-quality random numbers by two-dimensional cellular automata. IEEE Trans. Comput. 49, 1146–1151 (2000)
Matsumoto, M.: Simple cellular automata as pseudorandom m-sequence generators for built-in self-test. ACM Trans. Model. Comput. Simul. 8(1), 31–42 (1998)
Nandi, S., Kar, B.K., Chaudhuri, P.P.: Theory and applications of cellular automata in cryptography. IEEE Trans. Comput. 43(12), 1346–1357 (1994)
Neumann, J.V.: The Theory of Self- Reproducing Automata. University of Illinois Press Urbana (1966). (Edited by Burks, A.W.)
Roy Chowdhury, D., Sengupta, I., Chaudhuri, P.P.: A class of two-dimensional cellular automata and their applications in random pattern testing. J. Electron. Test. 5(1), 67–82 (1994)
Sudhakar, P., Chinnarao, B., Latha, D.M.M.: Optimization of 1D and 2D cellular automata for pseudo random number generator. IOSR J. VLSI Sig. Proc. (IOSR-JVSP) 4, 28–33 (2014)
Wolfram, S.: Theory and Applications of Cellular Automata (Including Selected Papers 1983–1986). World Scientific Pub. Co., Inc., River Edge (1986)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Maiti, S., Roy Chowdhury, D. (2017). Study of Five-Neighborhood Linear Hybrid Cellular Automata and Their Synthesis. In: Giri, D., Mohapatra, R., Begehr, H., Obaidat, M. (eds) Mathematics and Computing. ICMC 2017. Communications in Computer and Information Science, vol 655. Springer, Singapore. https://doi.org/10.1007/978-981-10-4642-1_7
Download citation
DOI: https://doi.org/10.1007/978-981-10-4642-1_7
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-4641-4
Online ISBN: 978-981-10-4642-1
eBook Packages: Computer ScienceComputer Science (R0)