Interrelation Between the Class of Bent-Sequences and the Class of Perfect Binary Arrays

Abstract

The paper is devoted to the research of the interrelation between classes of such perfect algebraic constructions as perfect binary arrays and bentsequences. The algebraic normal form of bent-sequences of length n  16 that generate perfect binary arrays of order N  4 , are presented. The exact number of perfect binary arrays in the full set of bent-sequences of length n  64 is found. The lower bound of cardinality of the full class of perfect binary arrays of order N  8 is improved.

Keywords

• perfect binary array
• 2DPACF
• bent-sequence
• Walsh-Hadamard transform

Introduction and problem statement

Perfect binary arrays (PBA) are an important class of algebraic constructions that have found numerous applications in the tasks of cryptographic information protection [ 1 ], the synthesis of error correction codes [ 2 ], construction of orthogonal and biorthogonal signal systems, antenna aperture synthesis, as well as in many other applications of science and technology [ 3 ].

Nevertheless, despite the numerous applications and a large number of publications devoted to the problems of the synthesis of PBA, in the general case, there are no methods for constructing their full classes for the derived value of the PBA order N . Moreover, today there is not even an accurate estimation of the cardinality of the full class of PBA of practically valuable orders N  4 , in particular order N  8 . Significant progress in solving the problem of synthesizing the full class of PBA of order N  8 was obtained in [ 4 ], in particular, it was found that the cardinality of the PBA class of order N  8 is not less than J8x8  688 128 , while 688 128 PBA were constructed using the original constructive method.

Another major class of perfect algebraic constructions is the class of the bentsequences (the truth tables of bent-functions), which was introduced in [ 5 ] and also found their numerous applications in cryptography and coding theory [ 6 ]. Methods for the synthesis of a full class of bent-sequences of length n  16 (the truth tables of bent-functions of four variables) are described in [ 7 ], while constructive methods for the synthesis of a full class of bent-sequences of length n  64 are proposed in [ 8, 9 ]. Recent researches of the PBA class carried out in [ 7 ] made it possible to establish that the full class of bent-sequences of length n  16 and cardinality Jbent  896 includes the full class of PBA of order N  4 and cardinality J PBA  384 .

However, the characteristics of the interrelation between the classes of bentsequences of length n  16 and PBA of order N  4 remains unspecified. Researches on the interrelation between the class of bent-sequences of length n  64 and PBA of order N  8 are absent in the literature.

The purpose of this paper is to determine the interrelation between the class of bent-sequences of practically significant lengths n  16; 64 and PBA of orders N  4; 8 . 2

Basic definitions

We introduce the basic definitions: Definition 1 [ 10 ]. A perfect binary array is a two-dimensional sequence (matrix) H (N )  hi, j , i, j  0,1,..., N 1, hi, j {1,1} , (1) (2) (3) (4) having an ideal two-dimensional periodic autocorrelation function (2DPACF), whose elements

R(m, )  PACF m,   Ni01 Nj01 hi, j him, j  0, Nfo2r,anfyorothmerm an0d; , where m,  0,1,..., N 1 , and all indices of elements him, j are reduced modulo

Let us give as an example a perfect binary array of order N  4 as well as its twodimensional periodic autocorrelation function

    16 0 0 0 H      , R   00 00 00 00 ,      0 0 0 0

Wf (w)  A(n)F (n) , where the symbol “+” denotes +1, and the symbol “–” denotes –1, respectively. Definition 2 [ 11 ]. The Walsh-Hadamard transform (WHT) of a vector F (n) in matrix form is defined as where F (n) is the binary sequence of length n , A(n) is the Hadamard matrix of order n , which is constructed in accordance with the following recurrence relation A(n)   A(n / 2)

 A(n / 2) AA((nn//22)) , A(1)  []. 3

Interrelation Between the Class of Bent-Sequences of Length n = 16 and the Class of Perfect Binary Arrays of Order N = 4

Let us consider the currently known methods of classification of PBA and bentsequences in order to establish the interrelation between these classes of perfect algebraic constructions. The modern approach to the classification of PBA involves the use of the following proposition: Proposition 1 [ 3 ]. Each PBA of order N generates a E(N ) -class of equivalent PBA matrices by using the cyclic rows and columns shift and inversion, with the cardinality of the equivalent matrices class Definition 3 [ 7 ]. A binary sequence B  [b0 , b1,, bi ,, bn1 ] of length n , where bi 1 are the coefficients, i  0,1,..., n 1 , n  2k , k  2, 4, 6,8,... , is called a bent-sequence, if it has a uniform Walsh-Hadamard spectrum WB ( ). (5) (6) (7)

J E(N )  2N 2 .

Thus, in accordance with Proposition 1, for the order of the PBA N  4 , the cardinality of each equivalent class is J E(8)  2  42  32 , and accordingly, the full set of PBA of cardinality J PBA  384 can be divided into 384 / 32  12 nonequivalent classes. Representatives of these non-equivalent classes are given in [ 3 ].

In [ 7 ] it was shown that the full class of bent-sequences of length n  16 includes the full class of PBA of order N  4 in the case of their representation as vectors by successive concatenation of the rows (columns) of the corresponding PBA.

For example, we concatenate the rows of PBA (3), as a result of which we obtain the following sequence and its Walsh-Hadamard transform coefficients in accordance with (4)

B  [              ]T , 1

WB1 (w)  A(16)B1   [4 4 4  4 4 4 4  4 4 4 4  4  4  4  4 4].

It is easy to see that the sequence (7) really satisfies the condition of Definition 3 and is a bent-sequence of length n  16 .

A modern approach to the classification of bent-sequences is based on the consideration of affine-equivalent classes. This classification is easiest to make on the basis of the representation of bent-sequences in algebraic normal form.

Definition 4 [ 11 ]. The algebraic normal form (ANF) φ(x1, x2 ,..., xk ) of a sequence T is a polynomial of k  log2 n variables with coefficients ai {0,1} , where the AND operation is used as the multiplication, and the XOR operation is used as the addition operation

N 1 φ  x1, x2 ,..., xk    a X s , i0 i i where X is are the terms of the ANF polynomial of degree s  wt  X  ; wt is the Hamming's weight.

The coefficients ai  a0 , a1,..., aN 1 can be found by performing the Reed-Muller transform [ 11 ], i.e. by multiplying the original sequence by the Reed-Muller matrix RM ν

{ai }  T  RM ν , T  {ai } RM ν , where the original sequence T is represented above the alphabet {0,1} using a bijective mapping 1  0, 1  1 , and the Reed-Muller matrix RM ν is determined using the following recurrent rule (8) (9) where  is the Kronecker product.

Definition 5 [ 11 ]. Terms of ANF of the degree s  wt  X   1 are called as affine.

For example, for sequence length n  16 there are the following possible affine terms: 1, x0 , x1, x2 , x3 on the basis of which corresponding affine codewords can be formed.

For example, we can represent as the ANF obtained from the PBA bent-sequence (7)

It is known [ 8 ] that the sum of a bent-sequence with an affine function (which is equivalent to adding one or several affine terms to the ANF coefficients sequence) leads to the formation of other bent-sequences. Thus, the full set of bent-sequences of cardinality J  896 can be classified into 896 / 32  28 affine non-equivalent classes, in each of which it is possible to distinguish a bent-sequence that does not have affine terms.

In this paper, through numerous experiments, the following statement was established: Proposition 2. Let H0 to be PBA of order N  4 , and T0 to be the sequence obtained by concatenating its rows (columns). Then the sequences T0,T1,...,T2k11 obtained by adding to the ANF sequences one or several affine terms construct, by lineby-line (column) filling, a set of matrices H0,H1,...,H2k11 that are also PBA.

Note that the Proposition 2 is valid only for PBA of order N  4 , and fully corresponds to Proposition 1, in terms of structure. However, Proposition 2 makes it easy to establish the interconnection between the generating PBA represented as their ANF (which contain affine terms) and the corresponding generating bent-sequences. We present all 28 generating bent-sequences, among which 12 (in bold font) generates affine non-equivalent classes of PBA of cardinality 32 PBA in each one, corresponding to Proposition 2 b1 = x2 x3 + x1x4; b15 = x3x4 + x1x4 + x1x2; b2 = x2 x3 + x1x4 + x1x2; b16 = x3x4 + x1x4 + x1x3 + x1x2; bb34 == xx22xx33 ++ xx11xx44 ++ xx11xx33;+ x1x2; bb1178 == xx33xx44 ++ xx22xx33 ++ xx11xx32;+ x1x2; bb56  xx22xx44  xx11xx33; x1x2; bb1290 == xx33xx44 ++ xx22xx33 ++ xx11xx44;+ x1x3; bbbbbbb11189712013=xxxxxxx222222xxx3xxx444x4444+xxxxxx112222xxxxxxx4413333x2x;xxxxx111111xxxxxx333434;;;xx1x1x1xx222;;; bbbbbbb22222224256731  xxxxxxx3333333xxxxxxx4444444  xxxxxxx2222222xxxxxxx4444444  xxxxxxx1111222xxxxxxx2344333;;xxxxx11111xxxxx32324;;;;; b14 = x3x4 + x1x3 + x1x2; b28  x3x4  x2x4  x2x3  x1x4  x1x3  x1x2. (12)

4 Interrelation Between the Class of Bent-Sequences of Length n = 64 and the Class of Perfect Binary Arrays of Order N = 8

In the general case, the problem of synthesizing a complete class of PBA of order N  8 is computationally complex and has not been solved yet. Significant progress in the construction of PBA classes was made in [ 4 ], where a method for synthesizing the PBA class based on the classes of thinned matrices was proposed and the constructions for their reproduction and superposition were found.

The results of [ 4 ] are based on the following proposition: Proposition 3 [ 3 ]. The PBA H0 (N ) of the arbitrary order N can always be represented as an interleaving (  ) of its thinned matrices

H0 (N )  hi, j  ai, j  bi, j  ci, j  di, j   A0 (N / 2)  B0 (N / 2)  C0 (N / 2)  D0 (N / 2), where

ai, j  h2i,2 j , bi, j  h2i,2 j1 , ci, j  h2i1,2 j , di, j  h2i1,2 j1 are the corresponding thinned matrices, i, j  0,1,..., N / 2 1 , and the indices hi, j vary within the limits i, j  0,1,..., N 1 .

Each PBA can be represented as (13). In the general case, the set of various structures of thinned matrices obtained by thinning the full class of PBA, we denote as {A i( N / 2)}; {B j ( N / 2)}; {C ( N / 2)}; {D ( N / 2)};   , i  1, 2,...,  A ; j  1, 2,...,  B ;   1, 2,..., C ;   1, 2,...,  D  where the parameters  A , B , C , D are the number of different structures (degrees of freedom) of the corresponding thinned matrices A, B, C, D of order N / 2 .

Different matrix structures from (14) can be obtained by using the cyclic shift operations in rows and columns, inversion, transposition, and mirroring of the set of

In [ 4 ], such a set of thinned matrices was obtained, the structures of which are pregenerating matrices. sented in Table 1.

Thinned matrix

    A                  C                  A0                  A      1             A2              (13) (14) representatives in the PBA class of order N  8 (synthesized in [ 4 ]) that forms the bent-sequences of length n  64 when concatenating their rows (columns).

At the same time, the other 688 128  98 304  589 824 PBA (when concatenating rows or columns) have non-uniform Walsh-Hadamard transform coefficients (absolute values). In order to classify these spectral coefficients, it is most convenient to use the definition of the elementary structure of the Walsh-Hadamard transform coefficients [13].

Definition 6 [13]. The elementary structure of the vector W ( ) of Walsh-Hadamard transform coefficients is the set of absolute values of its spectral components.

It was established experimentally that all remaining 589 824 PBA, on the basis of which it is impossible to form bent-sequences by applying the operation of concatenation of their rows (columns), according to Definition 6, have an elementary structure {0(12), 8(48), 16(4)} .

This notation of the elementary structure should be understood as follows: the number in front of the parentheses characterizes the absolute value of the WalshHadamard transform coefficient, whereas the number in parentheses indicates how many times it occurs in the vector of the Walsh-Hadamard transform coefficients.

Let us consider, for example, one of these PBA, as well as its 2DPACF                         H88          ,                         (16)

Applying the concatenation of the rows (columns) of PBA (15), we obtain a binary sequence and, according to Definition 2, corresponding to it vector of WalshHadamard transform coefficients, which has an elementary structure {0(12), 8(48), 16(4)}

T  {                               

                               }; WT  {                    

         }.

The research performed in this paper shows that establishing the interrelation between the class of PBA of order N  8 and the class of bent-sequences of length n  64 can significantly increase the lower bound of the number of PBA due to their new structures, that exist in the class of bent-sequences.

Note that, in the general case, the problem of synthesizing bent-sequences of length n  64 is a complex computational problem, coupled with the enumeration of a set of J  264  18 446 744 073 709 551616 elements. Nevertheless, the theory of bentsquares that was proposed in [14], with the help of which it was possible to synthesize the full set of bent-sequences of length n  64 which have the cardinality Jbent64  5 425 430 528 .

J sdr bent64  2 326 528

We established that within this set there is a set of PBA of cardinality in which, of course, we found as a subset of J PBA88,bent  98 304 PBA, that was constructed in [ 4 ].

As an example, we present one of the PBA and it’s 2DPACF, that was found in the bent-sequences of the length n  64 class and is not member of set of PBA synthesized in [ 4 ]         64 0 0 0 0 0 0 0          0 0 0 0 0 0 0 0          0 0 0 0 0 0 0 0 H8          , R   00 00 00 00 00 00 00 00 .

         0 0 0 0 0 0 0 0          0 0 0 0 0 0 0 0          0 0 0 0 0 0 0 0 (17)

We concatenate the PBA (17) rows, as a result of which we obtain the following sequence and its Walsh-Hadamard transform coefficients in accordance with (4) B  [                                                              ];

WB  [                               ], which proves that (18) is indeed a bent-sequence.

Note that PBA (17) consists of thinned matrices presented in Table. 2. These structures of thinned matrices differ from the matrices presented in Table 1. This fact shows that there are exist other structures of thinned matrices that differ from those found in [ 4 ].

Thinned matrix

    A                  C             

Thus, the discovering of the interrelation between the class of PBA of order N  8 and bent-sequences of length n  64 allows us to improve the estimation of the lower bound of the cardinality of PBA class of order N  8 . Summarizing, it was established that in [ 4 ], the PBA class that produces the bent-sequences has cardinality J PBA88,bent  98 304 , as well as PBA class that does not produce bent-sequences by concatenating rows (columns) has cardinality J PBA88,nonbent  589 824 . In this paper, it is clarified that the full class of bent-sequences of length n  64 includes the PBA class of cardinality J PBA88,bent  2 326 528 . Thereby, the cardinality of class of all the known PBA is

J PBA88  589 824  2 326 528=2 916 352 , (19) which is larger by a factor of ~ 4.2 compared to the estimation in [ 4 ]. 5

Conclusion

We note the main results obtained in the paper: 1. The lower bound estimation for the cardinality of the class of the PBA of order N  8 is improved. In particular, it has been established that the cardinality of the that is a factor of ~ 4.2 greater than the known estimation. 2. The total cardinality of the PBA class of order N  8 , which are producing the bent-sequences of length n  64 by concatenating the rows (columns), is established and equal to J PBA88,bent  2 326 528 . It is shown that the existence of new structures of thinned matrices, which differ from the previously known ones, are possible. 3. The interrelation between the PBA class of order N  4 and bent-sequences of length n  16 is established. In particular, 12 ANF polynomials of bent-sequences that produce the full PBA class of order N  4 , are presented.

It should be noted that the search for new structures of thinned matrices, as well as the rules for their interleaving for formal enumeration of the PBA full class that generates bent-sequences, is an actual direction for further research. The number of PBA, which generate sequences with other (different from the bent-sequences) elementary structures of the Walsh-Hadamard transform vectors also remains unknown and can be the actual direction for further research. 12. Mazurkov M. I., Chechelnitsky V.Ya. Classes of equivalent and generating perfect binary arrays for CDMA technologies. Proceedings of the universities. Radioelectronics, vol. 46, no. 5, pp. 54–63 (2003) 13. Sokolov A.V., Barabanov N.A. Algorithm for removing the spectral equivalence of component Boolean functions of Nyberg-design S-boxes. Radioelectronics and Communications Systems, vol. 58, no. 5, pp. 220-227. doi:10.3103/s0735272715050040 (2015) 14. Agievich S.V. On the representation of bent functions by bent rectangles. — Probabilistic Methods in Discrete Mathematics: Proceedings of the Fifth International Petrozavodsk Conference (Petrozavodsk, June 1–6, 2000). Utrecht, Boston: VSP, pp. 121—135 (2002)

References

1. Mazurkov M.I. , Chechelnytskyi , V.Y., Murr P . Information security method based on perfect binary arrays . Radioelectronics and Communications Systems , vol. 51 , no. 11 , pp. 612 - 614 . doi: 10 .3103/s0735272708110095 ( 2008 )

2. Baranov P.Y. , Mazurkov M.I. , Chechelnytskyi V.Y. , Yakovenko A.A. Family of twodimensional correcting codes on a basis of perfect binary array . Radioelectronics and Communications Systems , vol. 52 , no. 9 , pp. 501 - 506 . doi: 10 .3103/s0735272709090088 ( 2009 )

3. Mazurkov M.I. Broadband radio communication systems . Science and Technology , p. 340 . ( 2010 )

4. Chechelnytskyi , V. Y. A method for generation of the full class of perfect binary arrays of the order N = 8x8 . Radioelectronics and Communications Systems vol. 48 , no. 11 pp. 48 - 52 . doi: 10 .3103/S0735272705110087 ( 2005 )

5. Rothaus , O.S. On “bent” functions. J. Comb. Theory Ser . A., USA: Academic Press Inc, no. 20 ( 3 ), pp. 300 - 305 . doi: 10 .1016/ 0097 - 3165 ( 76 ) 90024 - 8 ( 1976 )

6. Tokareva N. Bent Functions : Results and Applications to Cryptography. Academic Press, p. 220 . ( 2015 )

7. Mazurkov M.I. , Sokolov A.V. The regular rules of constructing the complete class of bentsequences of length 16 . Proceedings of ONPU, no. 2 ( 41 ), pp. 231 - 237 ( 2013 )

8. Qingshu Meng , Min Yang, Huanguo Zhang, Jingsong Cui . A novel algorithm enumerating bent functions . Discrete Mathematics , vol. 308 , issue 23, pp. 5576 - 5584 . doi: 10 .1016/j.disc. 2007 . 10 .024 ( 2008 )

9. Sokolov , A.V. Synthesis method of a complete class of bent-functions of six variables . Problems of physics, mathematics and technics , no. 4 ( 29 ), pp. 94 - 102 ( 2016 )

10. Jedwab J. , Mithell C . Constructing new perfect binary arrays . Electronics Letters , vol. 24 , no. 11 , pp. 650 - 652 . doi: 10 .1049/el:19880440 ( 1988 )

11. Logachev O.A. , Salnikov A.A. , Yashchenko V.V. Boolean Functions in Coding Theory and Cryptography , Amer Mathematical Society , p. 334 ( 2012 )