# Binomial Representation of Cryptographic Binary Sequences and Its Relation to Cellular Automata

Authors: Sara D. Cardell; Amparo Fúster-Sabater
Journal: Complexity
 (2019)

---

## Abstract

The binomial sequences are binary sequences that correspond to the diagonals of the binary Sierpinski’s triangle. They have fancy properties such that all the sequences with period equal to a power of 2 can be represented as the sum of a finite set of binomial sequences. Other structural properties of these sequences (period, linear complexity, construction rules, or relations among the different binomial sequences) have been analyzed in detail. Furthermore, this work enhances the close relation between the binomial sequences and a kind of Boolean networks, known as linear cellular automata. In this sense, the binomial sequences exhibit the same behavior as that of particular Boolean networks. Consequently, the binomial sequences can be considered as primary tools for generating other more complex Boolean networks with applications in communication systems and cryptography.


---

## Body

## 1. Introduction

Pseudorandom binary sequences are simple successions of bits with applications in fields so different as spread-spectrum communications, circuit testing, error-correcting codes, numerical simulations, or cryptography (stream cipher). Most generators producing such sequences are based on Boolean functions and Linear Feedback Shift Registers (LFSRs) [1]. Desirable characteristics for pseudorandom binary sequences are long period, good statistical properties or large linear complexity. Different LFSR-based sequence generators can be found in the literature [2, Chapter 5]. In most of them, the output sequence is a binary sequence generated as the image of a nonlinear Boolean function in the shift register binary stages.On the other hand, the binomial sequences are a family of binary sequences whose terms are binomial numbers reduced modulo 2. More precisely, the binomial sequences correspond to the diagonals of the Sierpinski’s triangle modulo 2. In this way, the binomial sequences exhibit many attractive properties that can be very useful in the analysis and generation of cryptographic sequences. In this work, it is shown that every binary sequence with period2L, L being a positive integer, can be written as a bit-wise XOR of binomial sequences.Since many of the cryptographic sequences have period2L [3–6], then the binomial sequences can be considered as a fundamental tool to analyze the structural properties of all these classes of sequences. In addition, it can be checked that the behavior of some binomial sequence combinations is the same as that of a kind of Boolean networks (namely, one-dimensional cellular automata). In fact, cellular automata with two-state cells is a special kind of Boolean network where all the nodes use the same function and the links are all arranged in a regular bounded integer lattice structure. Boolean networks have attracted great attention in many different areas such as bioinformatics [7], computational processes [8], graph dynamical systems [9], and parallel discrete dynamical systems [10, 11]. This paper shows the subtle relation between binomial sequences and cellular automata. In brief, the binomial sequences and the linear cellular automata make visible the linearity inherent to many cryptographic generators paradoxically designed as strong nonlinear generators.The paper is organized as follows: In Section2, we introduce the basic concepts and definitions needed for the rest of this work. Section 3 studies the characterization and main properties of the binomial sequences. In Section 4, the relation between binomial sequences and linear cellular automata is analyzed. A simple method of recovering the binomial representation of a sequence is developed in Section 5 with an example. Finally, conclusions in Section 6 end the paper.


## 2. Preliminaries

In this section, we present some basic concepts about sequences that we need to know before introducing the main results.


### 2.1. Binary Sequences

LetF2 be the Galois field of two elements. We say {an}={a0,a1,a2…} is a binary sequence if its terms an∈F2, for n=0,1,2,…. The sequence {an} is periodic if and only if there exists an integer T such that an+T=an, for all n≥0. In the sequel, all the sequences considered will be binary sequences and the XOR operation among sequences will be denoted by + instead of the symbol ⊕.Letr be a positive integer, and let d1,d2,d3,…,dr be constant coefficients with di∈F2. A binary sequence {an} satisfying the relation(1)an+r=dran+dr-1an+1+⋯+d3an+r-3+d2an+r-2+d1an+r-1,n≥0,is called a (r-th order) linear recurring sequence in F2. The terms {a0,a1,…,ar-1} are referred to as the initial values (or initial state) and determine the rest of the sequence uniquely. A relation of the form given by (1) is called a (r-th order) linear recurrence relationship.The monic polynomial(2)px=dr+dr-1x+⋯+d3xr-3+d2xr-2+d1xr-1+xr∈F2xis called the characteristic polynomial of the linear recurring sequence and {an} is said to be generated by p(x).The generation of linear recurring sequences can be implemented on LFSRs [1]. These structures handle information in the form of binary elements and they are based on shifts and linear feedback. In fact, an LFSR is an electronic device with r memory cells (stages) with binary contents. At each time instant, each element is shifted to the adjacent stage and a new element is computed via a linear feedback to fill the empty stage (see Figure 1). If the characteristic polynomial of the linear recurring sequence is primitive [1], then the LFSR is a maximal-length LFSR and its output sequence, the so-called PN-sequence, has period T=2r-1.Figure 1
LFSR of lengthr.The linear complexity,LC, of a sequence {an} is defined as the length of the shortest LFSR that generates such a sequence or, equivalently, as the lowest order linear recurrence relationship that generates such a sequence.In cryptographic terms, the linear complexity must be as large as possible. The recommended value is approximately half the periodLC≃T/2.LetE be the shifting operator that acts on the terms of a sequence {an}; that is, (3)Ekan=an+k,for  allintegerk≥0.The linear recurrence relationship given in (1) can be written in terms of the operator E as a linear difference equation:(4)Er+∑j=1rdjEr-jan=0,forn≥0.If the characteristic polynomial p(x) is a primitive polynomial of degree r and α∈F2r is one of its roots, then α,α2,α22,…,α2r-1 are the r roots of such a polynomial. In this case, the binary solutions of (4) are a linear combination of the r roots of the form (5)an=∑j=0r-1ci2jα2jn,that is, an is the n-th term of a PN-sequence with characteristic polynomial p(x) and whose initial values are determined by the coefficient ci∈F2r.Next, let us consider a bit more complex difference equation of the form(6)Er+∑j=1rdjEr-jmzn=0,forn≥0,whose characteristic polynomial is pm(x)=p(x)m=(xr+∑j=1rdjxr-j)m, m being a positive integer. Now, the roots of pm(x) are the same as those of p(x) but with multiplicity m. Therefore, the binary solutions of (6) are given by(7)zn=∑i=0m-1ni∑j=0r-1ci2jα2jn,where the coefficients ci∈F2r and ni are binomial coefficients reduced modulo 2 (see [12]). Since(8)∑j=0r-1ci2jα2jnis the n-th term of a PN-sequence with characteristic polynomial p(x) and initial values determined by ci, then zn is the sum of m terms of a unique PN-sequence starting at different points and where each one of these m terms is weighted by a binary binomial coefficient ni.


## 2.1. Binary Sequences

LetF2 be the Galois field of two elements. We say {an}={a0,a1,a2…} is a binary sequence if its terms an∈F2, for n=0,1,2,…. The sequence {an} is periodic if and only if there exists an integer T such that an+T=an, for all n≥0. In the sequel, all the sequences considered will be binary sequences and the XOR operation among sequences will be denoted by + instead of the symbol ⊕.Letr be a positive integer, and let d1,d2,d3,…,dr be constant coefficients with di∈F2. A binary sequence {an} satisfying the relation(1)an+r=dran+dr-1an+1+⋯+d3an+r-3+d2an+r-2+d1an+r-1,n≥0,is called a (r-th order) linear recurring sequence in F2. The terms {a0,a1,…,ar-1} are referred to as the initial values (or initial state) and determine the rest of the sequence uniquely. A relation of the form given by (1) is called a (r-th order) linear recurrence relationship.The monic polynomial(2)px=dr+dr-1x+⋯+d3xr-3+d2xr-2+d1xr-1+xr∈F2xis called the characteristic polynomial of the linear recurring sequence and {an} is said to be generated by p(x).The generation of linear recurring sequences can be implemented on LFSRs [1]. These structures handle information in the form of binary elements and they are based on shifts and linear feedback. In fact, an LFSR is an electronic device with r memory cells (stages) with binary contents. At each time instant, each element is shifted to the adjacent stage and a new element is computed via a linear feedback to fill the empty stage (see Figure 1). If the characteristic polynomial of the linear recurring sequence is primitive [1], then the LFSR is a maximal-length LFSR and its output sequence, the so-called PN-sequence, has period T=2r-1.Figure 1
LFSR of lengthr.The linear complexity,LC, of a sequence {an} is defined as the length of the shortest LFSR that generates such a sequence or, equivalently, as the lowest order linear recurrence relationship that generates such a sequence.In cryptographic terms, the linear complexity must be as large as possible. The recommended value is approximately half the periodLC≃T/2.LetE be the shifting operator that acts on the terms of a sequence {an}; that is, (3)Ekan=an+k,for  allintegerk≥0.The linear recurrence relationship given in (1) can be written in terms of the operator E as a linear difference equation:(4)Er+∑j=1rdjEr-jan=0,forn≥0.If the characteristic polynomial p(x) is a primitive polynomial of degree r and α∈F2r is one of its roots, then α,α2,α22,…,α2r-1 are the r roots of such a polynomial. In this case, the binary solutions of (4) are a linear combination of the r roots of the form (5)an=∑j=0r-1ci2jα2jn,that is, an is the n-th term of a PN-sequence with characteristic polynomial p(x) and whose initial values are determined by the coefficient ci∈F2r.Next, let us consider a bit more complex difference equation of the form(6)Er+∑j=1rdjEr-jmzn=0,forn≥0,whose characteristic polynomial is pm(x)=p(x)m=(xr+∑j=1rdjxr-j)m, m being a positive integer. Now, the roots of pm(x) are the same as those of p(x) but with multiplicity m. Therefore, the binary solutions of (6) are given by(7)zn=∑i=0m-1ni∑j=0r-1ci2jα2jn,where the coefficients ci∈F2r and ni are binomial coefficients reduced modulo 2 (see [12]). Since(8)∑j=0r-1ci2jα2jnis the n-th term of a PN-sequence with characteristic polynomial p(x) and initial values determined by ci, then zn is the sum of m terms of a unique PN-sequence starting at different points and where each one of these m terms is weighted by a binary binomial coefficient ni.


## 3. Binomial Sequences

Previous to the introduction of the binomial sequence concept, let us consider some general features of the binomial coefficients.The binomial coefficientni is the coefficient of the power xi in the polynomial expansion of (1+x)n. For every positive integer n, it is a well-known fact that n0=1 and ni=0 for i>n. Moreover, it is worth noticing that if we arrange these binomial coefficients into rows for successive values of n=0,1,2,…, then the generated structure is the Pascal’s triangle (see Figure 2(a)). The most-left diagonal is the identically 1 sequence, the next diagonal is the sequence of natural numbers {1,2,3,…}, the next one is the sequence of triangular numbers {1,3,6,10,…}, etc. Other fascinating sequences (tetrahedral numbers, pentatope numbers, hexagonal numbers, Fibonacci sequence, etc.) can be found in the diagonals of this triangle. On the other hand, if we color the odd numbers of the Pascal’s triangle and shade the even numbers, then we get the Sierpinski’s triangle (see Figure 2(b)).Figure 2
Binomial coefficients arranged as triangles.
(a)
Pascal’s triangle (b)
Sierpinski’s triangle (c)
Sierpinski’s triangle mod 2The binomial coefficients reduced modulo 2 allow us to introduce the concept of binomial sequence.Definition 1.
Given a fixed integerk≥0, the sequence bnkn≥0 given by (9)bnk=0ifn<knkmod⁡2ifn≥k is known as thebinaryk-th binomial sequence.Table1 shows the binomial sequences and their corresponding periods and linear complexities, denoted by Ti and LCi, respectively, for the first 8 binomial coefficients ni, i=0,1,…,7; see [12]. The linear complexities of the binomial sequences are defined in Theorem 13 (Section 4). Recall that the successive binomial sequences correspond to shifted versions of the successive diagonals in the Sierpinski’s triangle reduced modulo 2 (see Figure 2(c)).Table 1
Binomial sequences, first eight terms, period, and linear complexity.
Binomial coeff. Binomial sequences Period Linear complexity n0 1   1   1   1   1   1   1   1 T 0 = 1 L C 0 = 1 n1 0   1   0   1   0   1   0   1 T 1 = 2 L C 1 = 2 n2 0   0   1   1   0   0   1   1 T 2 = 4 L C 2 = 3 n3 0   0   0   1   0   0   0   1 T 3 = 4 L C 3 = 4 n4 0   0   0   0   1   1   1   1 T 4 = 8 L C 4 = 5 n5 0   0   0   0   0   1   0   1 T 5 = 8 L C 5 = 6 n6 0   0   0   0   0   0   1   1 T 6 = 8 L C 6 = 7 n7 0   0   0   0   0   0   0   1 T 7 = 8 L C 7 = 8Next, the relation between binomial sequences and binary sequences with period which is a power of 2 is defined in the following result.Theorem 2.
Let{zn} be a binary sequence with period T=2L, L being a positive integer. Then, every binary sequence {zn} can be written as a linear combination of binomial sequences.Proof.
Since the period of{zn} is a power of 2, then the next equation holds:(10)E2L+1zn=E+12Lzn=0,which is a simplified version of (6) with m=2L and the characteristic polynomial pm(x)=p(x)m=(x+1)m. Therefore, its binary solutions are given by (7), which has now the following simplified form:(11)zn=n0c0+n1c1+⋯+nT-1cT-1forn≥0, where 1 is the unique root of the polynomial (x+1)T with multiplicity T=2L, the coefficients ci∈F2 and ni are binomial coefficients modulo 2. When n takes successive values n=0,1,2,…, then each binomial coefficient modulo 2 defines a different binomial sequence. Thus, the sequence {zn} is just the bit-wise XOR of such binomial sequences weighted by binary coefficients ci.Different choices ofci will produce different sequences {zn} with distinct characteristics and properties, but all of them with period 2l, 0≤l≤L.


## 4. Properties of the Binomial Sequences

From now on, we denote thek-th binomial sequence bnkn≥0 as nkn≥0 or simply nk, while nk denotes a binomial coefficient.In this section we study the properties of this family of binomial sequences.Next result shows that the binomial sequences can be obtained one from another.Proposition 3.
Given the sequencen2L+k, with 0≤k<2L, we have that (a)
the sequence has periodT=2L+1;(b)
the first period of the sequence has the following structure:(12)n2L+k0≤n<2L+1=0if0≤n<2L+k,nkif2L+k≤n<2L+1.Proof.
(b) We consider the first2L+1 bits of the sequence n2L+k.
We know thatn2L+k=0 when n<2L+k. Then, the first 2L+k bits are 0s; in particular, this means that the first 2L elements of the sequence are zero.
Ifn≥2L+k, then n is of the form n=2L+k+t, for 0≤t<2L-k. We want to prove that the other 2L bits are the first 2L bits of nk. This idea is illustrated in Figure 3.
In order to prove that the other2L bits are the first 2L bits of nk, it is enough to prove that 2L+k+t2L+k≡k+tk(mod⁡2).
Thus, we compute both binomial coefficients(13)2L+k+t2L+k=2L+k+t!2L+k!t!=2L+k+t⋯2L+k+1t!,k+tk=k+t⋯k+1t!
Let2pi be the maximum power of 2 in the prime factorization of k+i, with 0<i≤t and qi the odd number such that k+i=2piqi. Notice that when k+i is odd, then k+i=qi and pi=0.
Then, we have(14)2L+k+t2L+k=2pt+pt-1+⋯+p12L-pt+qt2L-pt-1+qt-1⋯2L-p1+q1t!,(15)k+tk=2pt+pt-1+⋯+p1qt·qt-1⋯q1t!
Sincek+i<2L, then 2piqi<2L and, as a consequence, pi<L. Now, the inequality L-pi>0 implies that 2L-pi+qi is always an odd number. Finally, since both (14) and (15) have the same denominator, then they exhibit the same powers of two. Thus, (14) is odd (even) iff (15) is odd (even) and the previous congruence holds.
(a) It is enough to prove now that(16)2L+m+t2L+k≡2L+m+1+t2L+kmod⁡2
We consider both binomial coefficients:(17)2L+m+t2L+k=2L+m+t·2L+m+t-1⋯2L+m+t-2L-k+12L+k!2L+m+1+t2L+k=2L+m+1+t·2L+m+1+t-1⋯2L+m+1+t-2L-k+12L+k! Consider 2pi the maximum power of 2 in the prime factorization of i, with t-2L-k+1≤i≤t and qi the odd number such that 2pi·qi=i. Notice that when i is odd, then pi=0 and i=qi. With this new notation, we have that(18)2L+m+t2L+k=2pt·pt-1⋯pt-2L-k+12L+m-pt+qt·2L+m-pt-1+qt-1⋯2L+m-pt-2L-k+1+qt-2L-k+12L+k!(19)2L+m+1+t2L+k=2pt·pt-1⋯pt-2L-k+1qt·qt-1⋯qt-2L-k+12L+k!
Note thatL+m-pi>0 and then 2L+m-pi+qi is always an odd number. Now, since both expressions (18) and (19) have the same denominator and the same powers of two in the prime factorization of the numerator, we know that (18) is odd (even) iff (19) is odd (even).
We have proven thatn2L+k=n+2L+12L+k, for n≥0. Then we know that the period divides 2L+1. Since the first 2L bits of the sequence are 0s (item b), then the period must be T=2L+1.Figure 3
Structure of the binomial sequencesnk and n2L+k.In Figure8, we can see the structure of the first 32 binomial sequences. It is easy to observe the pattern and the periods mentioned in Proposition 3.It is worth noticing that the binomial sequences match exactly with the diagonals of the binary Sierpinski’s triangle (see Figure4) but starting in a different bit (shifted versions of such diagonals). For example, the encircled sequence in Figure 4 corresponds to the shifted binomial sequence n4.Figure 4
Binary Sierpinski’s triangle where the circled bits correspond to the sequencen4.We know that the sequencenk is a solution of the difference equation of the form (10). Therefore, every sequence of period 2L can be obtained by XORing diagonals of the binary Sierpinski’s triangle.Corollary 4.
The sequencesn2L(L=0,1,2,…) have period T=2L+1 and the following structure:(20)n2L0≤n<2L+1=0if0≤n<2L,1if2L≤n<2L+1.Corollary 5.
The sequencesn2L(L=0,1,2,…) are balanced; that is to say, they contain the same number of 1s and 0s.Remark 6.
(a) The sequences of the formn2L have the following structure:(21)00…0︸2Lzeros11…1︸2Lones
(b) The sequences of the formn2L+k have the following structure:(22)00…0︸2Lzeros…………︸2Lfirst  termsofnk
According to Theorem2, a binary sequence of period power of 2 is the bit-wise XOR of binomial sequences. Therefore, we introduce the following definition.Definition 7.
The set of binomial sequences necessary to obtain a binary sequence of period power of 2 is called thebinomial representation of such a sequence.The binomial representation of a sequence is of the form∑i=0Mcini, with ci∈F2 and M an integer such that M≥0.Since our sequences are periodic, they can start in different points. Next we see that, depending on the starting point, the binomial representations of the same sequence will be different.Lemma 8.
Given two positive integersn and t with n>t, we have the following:(23)nt+nt-1=n+1tProof.
(24) n t + n t - 1 = n ! t ! n - t ! + n ! t - 1 ! n - t + 1 ! = n - t + 1 · n ! + t · n ! t ! n - t + 1 ! = n + 1 ! t ! n + 1 - t ! = n + 1 tLemma 9.
Given the binomial sequencent, t≥1, if we shift cyclically such a sequence one bit to the left, then we obtain the sequence nt+nt-1. If t=0, the sequence remains the same (in this case the sequence is the identically 1 sequence).Proof.
According to the construction rule for binomial sequences given in Definition1, the sequences nt and n+1t are the same but starting in different points.
Now, according to Lemma8, we know that nt+nt-1=n+1t, then the sequence n+1t equals the sequence nt+nt-1. Therefore, the sequences nt and nt+nt-1 are the same but starting in different bits.Example 10.
Consider the following sequences:(25)n2:00110011…n2+n1:01100110…Both sequences n2 and n2+n1 are the same, but starting in different positions. We can check that the starting point of the sequence n2+n1 (bit in bold) is the second bit of sequence n2.In order to prove the linear complexity of the binomial sequences, we need to introduce the following results.Proposition 11.
Given the binomial sequencent, with a fixed t≥1, the sequence represented by nt+n+1t can be also represented by nt-1. If t=0, the sequence nt+n+1t is the identically zero sequence.Proof.
According to Lemma8, we know that nt+nt-1=n+1t. Since we are working over the binary field, we have that the sequence nt+nt+1 can be also represented by nt-1.Theorem 12 ([13], Theorem 1).
Let{si}i≥0 be a binary sequence whose characteristic polynomial is (1+x)n. Then, the characteristic polynomial of the sequence {ui}i≥0, where ui=si+si+1, is (1+x)n-1.Now, we are ready to study the linear complexity of the binomial sequences.Theorem 13.
The linear complexity of the sequencenk is k+1.Proof.
We prove this result by induction.
Fork=0, the sequence n0={11111…} has LC0=1 and the characteristic polynomial is (1+x).
Fork=1, the sequence n1={0101…} represented by n1 has LC1=2 and the characteristic polynomial is (1+x)2.
Let us suppose that the sequencenk has LCk=k+1 and the characteristic polynomial is (1+x)k+1.
According to Proposition11, we have that nk=nk+1+n+1k+1. Now, according to Theorem 12, the characteristic polynomial of nk+1 is (1+x)k+2 and, thus, LCk+1=k+2.As a consequence of the previous theorem, we have the following result.Corollary 14.
Given a sequence with binomial representation∑k=1tnik, where i1<i2<⋯<it are integer indices, then the linear complexity of such a sequence is it+1.As a consequence of Lemma9, we obtain the following result.Theorem 15.
Let∑i=0LC-1cini with ci∈F2 be the binomial representation of a sequence. If we shift cyclically such a sequence one bit to the left, then its binomial representation is(26)∑i=1LC-1cini+ni-1+c0n0.Corollary 16.
Binary sequences with period2L have 2L different binomial representations.Proof.
Since the period of the sequence is2L, we can perform 2L left shifts before getting the same starting point of the sequence. Therefore, we can obtain 2L different binomial representations.Example 17.
Consider the sequence with binomial representationn3+n1. In Figure 5, we can see graphically the method followed to obtain the different binomial representations of this sequence. From one representation and via Theorem 15, we obtain the next representation corresponding to the same sequence left-shifted one bit. Finally, we have 4 different representations (the ones in bold contained in the grey boxes) including the initial one: (27)n3+n1,n3+n2+n1+n0,n3,n3+n2.Since the period of this sequence is 4, we can obtain 4 different binary representations. Furthermore, one can observe that after four steps we obtain again the initial representation n3+n1.Figure 5
Binomial representations of the 4 shifted versions of the sequencen3+n1.Now, consider again Figure4. We know that the binomial sequence n4 showed in the binary Sierpinski’s triangle starts in a different bit compared with the sequence n4 given in Table 1. In particular, in the binary Sierpinski’s triangle the sequences start in the first nonzero bit; thus their binomial representations are different. For instance, consider Table 3 where we can observe the different representations of a unique binomial sequence n15. Each row represents the coefficients {c0,c1,…,c15} of each different binomial representation. The binomial representation of the sequence n15 in the binary Sierpinski’s triangle is the last row of Table 3: ∑i=015cini, with ci=1, for i=0,1,…,15.


## 5. Cellular Automata

Cellular automata (CA) are discrete structures composed of a finite number of cells whose content is updated according to arule or function with k variables [14]. The state of the cell in position i at time t+1, notated xit+1, depends on the state of the k neighbour cells at time t. If these rules are composed exclusively of XOR operations, then the CA arelinear. Here, the CA we consider areregular (every cell follows the same rule),cyclic (extreme cells are adjacent), and one-dimensional. For k=3, rules 102 and 60 are given in Table 2.Table 2
Rules 102 and 60.
(a)
Rule  102:  xit+1=xit+xi+1t
111 110 101 100 011 010 001 000 0 1 1 0 0 1 1 0  (b)
Rule  60:  x i t + 1 = x i - 1 t + x i t
111 110 101 100 011 010 001 000 0 0 1 1 1 1 0 0Table 3
Binomial representations of the 16 shifted versions ofn15.
n0 n 1 n 2 n 3 n 4 n 5 n 6 n 7 n 8 n 9 n 10 n 11 n 12 n 13 n 14 n 15 c0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 10 c 11 c 12 c 13 c 14 c 15  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0  0  0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0  0 0 0  0 0 0 0 0 0 0 0 0 0   0 0  0 0 0 0 0 0 0 0 0  0  0  0  0 0 0 0 0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0 0  0 0 0 0 0 0   0 0 0 0 0 0  0 0 0 0 0  0  0 0 0 0 0  0  0 0 0 0     0 0 0 0  0 0 0  0 0 0  0 0 0  0 0 0  0 0   0 0   0 0   0 0  0  0  0  0  0  0  0  0The number 01100110 (00111100) is the binary representation of the decimal number 102 (60). In Figure6, these rules are depicted according to Wolfram terminology [15]: a white square represents the digit 0 and a black square represents the digit 1.Figure 6
Rules 102 and 60 depicted in Wolfram’s notation.Consider again Table3. If we color the 1s, the general structure of the set of characterizations is the same as that one of the CA-image generated by rule 102 after having applied 15 iterations to the one-dimensional cellular automata (see Figure 7). In general, due to the observed form of the binomial sequences (see Figure 8 and Proposition 3), it can be assured that the complete set of binomial representations of n2L-1 coincides with the 102-CA of length and 2L and initial state {00…01}. This is due to the fact that the recursive method to obtain the different binomial representations of a sequence matches with the generation rule of 102-CA (depicted in Table 2).Figure 7
CA-images generated with rules 102 and 60.Figure 8
The first 32 binomial sequences.As a consequence, we can introduce the following result.Theorem 18.
Consider a sequence{uj}j≥0 with binomial representation ∑i=0LC-1cini. If we put this sequence in the leftmost column of a 102-CA (rightmost column of a 60-CA), then the binomial representation of the next sequence {uj+uj+1}j≥0 in the CA is(28)∑i=0LC-2ci+1ni.Proof.
Let us denote the binomial sequenceni by {bni}n≥0. Then, we have that(29)uj=∑i=0LC-1cibji,j≥0uj+uj+1=∑i=0LC-1cibji+∑i=0LC-1cibj+1i=∑i=0LC-1cibji+bj+1i,j≥0. According to Proposition 11,(30)uj+uj+1=∑i=1LC-1cibji-1=∑k=0LC-2ck+1bjk Then, {uj+uj+1}j≥0 is represented by ∑i=0LC-2ci+1ni.Remark 19.
If the termn0 is included in the binomial representation, it is discarded for the next sequence. See, for example, Table 4. In this table, we have two examples of one-dimensional linear CAs. The first one is a 102-CA. At the bottom of the CA, we can observe the binomial representations of the generated vertical sequences. We can check that the binomial representations of the sequences can be obtained following the process mentioned in Theorem 18. It is worth noticing that the given 60-CA generates exactly the same sequences, but they appear in reverse order.Table 4
Examples of 102-CA and 60-CA and the binomial representation of the generated vertical sequences.
(a) 102 102 102 102 102 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1  n 4 + n 2 n 3 + n 1 n 2 + n 0 n 1 n 0  (b) 60 60 60 60 60 1 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 0  n 0 n 1 n 2 + n 0 n 3 + n 1 n 4 + n 2Finally, observe that the set of binomial representations of a sequence follows the same pattern as the 102-CA.Theorem 20 ([13], Theorem 4).
Given a sequence with period2L and linear complexity LC, then the CA that generates this sequence using the rule 102 has (i)
one sequence of period 1 (the identically 1 sequence),(ii)
2i-1 sequences of period 2i, for 1≤i≤L-2,(iii)
LC-2L-2 sequences of period 2L-1.Consider, for example, the sequence represented byn0+n2+n3+n5+n12. This sequence has period T=16. In Table 5, we can observe the 16 different representations of this sequence. The rows of the table represent the coefficients {c0,c1,…,c12} that accompany each binomial coefficient, for each representation. That means, the column j represents the coefficients that accompany nj for each one of the 16 representations.Table 5
Binomial representations of the 16 shifted versions of the sequencen0+n2+n3+n5+n12.
n0 n 1 n 2 n 3 n 4 n 5 n 6 n 7 n 8 n 9 n 10 n 11 n 12 c0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 10 c 11 c 12  1 0 1 1 0 1 0 0 0 0 0 0 1  1 1 0 1 1 1 0 0 0 0 0 1 1  0 1 1 0 0 1 0 0 0 0 1 0 1  1 0 1 0 1 1 0 0 0 1 1 1 1  1 1 1 1 0 1 0 0 1 0 0 0 1  0 0 0 1 1 1 0 1 1 0 0 1 1  0 0 1 0 0 1 1 0 1 0 1 0 1  0 1 1 0 1 0 1 1 1 1 1 1 1  1 0 1 1 1 1 0 0 0 0 0 0 1  1 1 0 0 0 1 0 0 0 0 0 1 1  0 1 0 0 1 1 0 0 0 0 1 0 1  1 1 0 1 0 1 0 0 0 1 1 1 1  0 1 1 1 1 1 0 0 1 0 0 0 1  1 0 0 0 0 1 0 1 1 0 0 1 1  1 0 0 0 1 1 1 0 1 0 1 0 1  1 0 0 1 0 0 1 1 1 1 1 1 1  T = 16 T = 16 T = 16 T = 16 T = 16 T = 8 T = 8 T = 8 T = 8 T = 4 T = 4 T = 2 T = 1If we observe the behavior of the coefficients in the columns, we can check that the columns follow the same structure proposed in Theorem20:(i)
One sequence of period 1 (rightmost sequence).(ii)
One sequences of period 2.(iii)
Two sequences of period 4.(iv)
Four sequences of period 8.(v)
Five sequences of period 16.Furthermore, it is possible to check that Table5 is a 102-CA. This is due to the formation rule of the binomial representations given in (26), which coincides with the formation procedure of Rule 102.


## 6. Recovering the Binomial Representation

Givent intercepted bits of a sequence of period 2L, Algorithm 1 introduces a method to recover a part of the binomial representation of such a sequence depending on the number t. Let us denote by s the set of intercepted bits. In round j, the algorithm compares sj with the corresponding bit in the sequence represented by ∑i=0jni. If they match, then nj is part of the binomial representation. Otherwise, the term nj is discarded and the algorithm continues. This method is based on the fact that the first j bits of the sequence represented by nj are 0s.Algorithm 1:Constructing the binomial representation of a given sequence.
Input: s: Intercepted bits 01:repr={0000…}; 02:t=length(v); 03:for  j=0  to  t-1  do 04:if  sj≠reprj  then 05:repr=repr+nj; 06:endif 07:endfor Output: r e p r: Binomial representation of the intercepted bitsLet us introduce now an illustrative example.Example 21.
Consider the set of intercepted bitss={110111}. The first two bits (s0=1 and s1=1) match with the first two bits of the sequence n0={1111…}. This means that one of the binomial representations of the sequence starts with ∑i=01cini=n0(c0=1,c1=0).
The bits2=0 matches with the corresponding bit of the sequence n0+n2:(31)
n
0
:
1
1
1
1
1
1
1
1
…
n
2
:
0
0
1
1
0
0
1
1
…
1
1
0 Then, the binomial representation we are considering starts with ∑i=02cini=n0+n2(c0=1,c1=0,c2=1).
Finally, the bitss3=1, s4=1, and s5=1 match with the corresponding bits of the sequence n0+n2+n3:(32)
n
0
:
1
1
1
1
1
1
1
1
…
n
2
:
0
0
1
1
0
0
1
1
…
n
3
:
0
0
0
1
0
0
0
1
…
1
1
0
1
1
1 Therefore, we have that the first part of the considered binomial representation is ∑i=05cini=n0+n2+n3 with coefficients as in Table 6. In case of having more intercepted bits and proceeding in the same way, we would complete the whole representation.Table 6
Coefficients in Example21.
c0 c 1 c 2 c 3 c 4 c 5 1 0 1 1 0 0Next, we introduce a result on the number of bits required to recover the binomial representation of a sequence. Notice that if we know the binomial representation of a sequence, we can recover the whole sequence.Proposition 22.
GivenLC-1 intercepted bits of a sequence with linear complexity LC and period 2L, it is possible to recover the complete the binomial representation of the sequence.Proof.
According to Corollary14, the binomial representation of a sequence with linear complexity LC and period 2L is of the form ∑i=0LC-1cini, with cLC-1=1. Now, according to the method explained in Algorithm 1, we need LC-1 bits to recover each one of the coefficients ci, i=0,1,…,LC-1.At any rate, the application of the traditional Berlekamp-Massey algorithm [16] needs 2·LC intercepted bits to recover the whole sequence. Thus, the method here developed makes use of half the bits needed by the Berlekamp-Massey algorithm. Consequently, the amount of intercepted bits has been reduced by a factor 2, which is quite favorable in terms of cryptanalysis.


## 7. Conclusions

The family of binary sequences considered in this work, sequences whose period is a power of 2, has good cryptographic properties such as long period and large linear complexity. However, we have seen that such sequences are simple solutions of linear difference equations with constant coefficients and can be obtained by XORing binomial binary sequences corresponding to diagonals of Sierpinski’s triangle reduced modulo 2. Although different nonlinear procedures, e.g., irregular decimation, are introduced to break the linearity of the LFSR-based sequence generators, this linearity is still visible in their output sequences. Consequently, such linearity makes the generators producing the previous sequences vulnerable against cryptanalysis and makes them not suitable as part of more complex cryptographic structures. In this sense, we conjecture that given a sequence there exists a minimal binomial representation, that is, a representation with a minimum number of binomial terms.On the other hand, we showed that there exists a close relation between one-dimensional linear cellular automata (102-CAs or 60-CAs) and the binomial sequences. Furthermore, there exists another family of cellular automata (150/90-CAs) that also generate sequences of period2L with good cryptographic properties. Therefore, in order to complete this study, the analysis of the relation of this family of cellular automata with binomial sequences is proposed as future work.



---

*Source: 2108014-2019-03-24.xml*