Open Access
Issue
Wuhan Univ. J. Nat. Sci.
Volume 26, Number 6, December 2021
Page(s) 453 - 458
DOI https://doi.org/10.1051/wujns/2021266453
Published online 17 December 2021

© Wuhan University 2021

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

0 Introduction

Boolean functions are important objects in discrete mathematics. They play a role in symmetric cryptography and error-correcting coding theory, and they also have a significant influence on the design and analysis of cryptographic algorithms. The Walsh transform is a vital tool to investigate cryptographic properties of Boolean functions. Some important properties of cryptographic functions, such as resiliency and nonlinearity can be characterized by their Walsh transform[1-3]. An interesting problem is to find Boolean functions with few Walsh transform values and determine their distributions.

Bent functions introduced by Rothaus[4] in 1976 are interesting combinatorial objects with maximum Hamming distance to the set of all affine functions, but they cannot be used in cryptography directly since they exist only in an even number of variables and are not be balanced. Such functions have been extensively studied because of their important applications in coding theory[5,6], cryptography[7], and sequence designs[8]. To get balanced functions with high nonlinearity in odd or even number of variable, Carlet[9] generalized the bent functions to plateaued functions and they take Walsh transform values 0, for a fixed positive integer k. Semi-bent, as a particular case, is an important kind of Boolean functions with three Walsh transform values. In Ref. [10], some classes of Boolean functions with four-valued Walsh spectra are presented by complementing the values of bent functions at two points, one of which is zero and the other is nonzero, and their Walsh spectrum distributions are determined finally. Inspired by this work, recently Jin et al[11] presented three classes of Boolean functions with six-valued Walsh spectra, which were derived from bent functions by complementing their values at the zero and another two nonzero points, and determined their Walsh spectrum distributions with a similar method. In Ref. [12], some classes of Boolean functions with five Walsh transform values were presented by adding the product of two or three linear functions into some known bent functions, and their Walsh spectrum distributions were determined finally. In Ref. [13], Tang et al gave a generic construction of bent functions defined as where n=2m, g(x) is any known bent function over satisfying some conditions, is an arbitrary polynomial in . In particular, the cases of and have been studied by Xu et al[12] and Mesnager[14], respectively. The purpose of this paper is to present the Walsh transform of the Boolean function defined as (1) where f(x) and h(x) are Boolean functions over and . In particular, the case of (2) has been studied by Pang et al[15].

This paper is organized as follows. In Section 1, we give some basic concepts and results. In Section 2, we present the Walsh transform of the Eq. (1). In Section 3, we conclude this paper.

1 Preliminaries

Let denote the n-dimensional vector space over F2, and denote the finite field with 2n elements. For any set E, . By viewing each as a vector where is a basis of over F2, we identify with and then every function is equivalent to a Boolean function. For , the inner product is defined as .

For any positive integer k|n, the trace function from to is the mapping defined as When k=1, is called the absolute trace function.

Some important and useful properties of the trace function are provided in the following:

1) , and .

2) for any .

3) For any , if .

4) When , the trace function satisfies the transitivity property, that is, .

5) For any , , .

Let f be a Boolean function from to F2, and the set of which is denoted by Bn. The Walsh transform of at is defined as

The values , are called the Walsh coefficients of f. The Walsh spectrum of a Boolean function f is the multiset . A Boolean function f is said to be balanced if .

The nega-Hadamard transform of f(x) at is the complex valued function where is the function defined by . A function is negabent if for all .

2 Main Results

Let n be a positive integer and f be a Boolean function from to F2. For any , the Boolean function can be written aswhere for .

The relationship between and , , is given in Theorem 1.

Theorem 1   Let ,Then, the Walsh transform of g(x) at is given by

1) When ,

2) When ,

3) When ,

Proof   For simplicity, denotewhere , , .

The proof proceeds in terms of three cases: , and .

1) If , then one obtainswhere , .

Note thatand .

Then byandwe have

2) The proof of 2) is obvious from 1).

3) If , then one obtainswhere .

Note thatTogether with the factandSimilarly,Then bywe havebywe haveSimilarly, we haveOne immediately gets thatwhen b=0,when b=1,when ,when ,The proof is completed.

In particular, when , the function is exactly the ones studied by Pang et al[15]. Note that our generic construction works for any f(x) and h(x). Therefore, our construction contains the previous ones in Ref. [15] as special cases.

Corollary 1   Let , andThe Walsh transform of g(x) at is given byIn the following, pang proposed three new classes of Boolean functions having the form as Eq. (2) by suitable choices of f(x). The first class is obtained from bent functions, including Dillon bent, kasami bent and Gold-like bent functions, and from the definition of the dual of bent functions, the Walsh transform value distribution of such class is presented. Ref. [15] indicates that the Walsh spectrum distribution of g(x) derived from bent functions is obtained from calculating the dual function of f and the values of , and . Therefore, the Walsh spectrum distribution ofis presented.

The second class is derived from Gold functions and their Walsh spectrum distribution is obtained by making use of the Walsh transform property of Gold functions and the known conclusions of Weil sums in characteristic 2. The Walsh spectrum distribution of g(x) which is obtained by Gold functions is discussed in the following three cases.

Case 1  n/d is even and for any integer t. It is known that in this case is bent. Then the Walsh spectrum distribution ofis given in Ref. [15].

Case 2  n/d is even and for some integer t. In this case the Walsh spectrum distribution ofdepends on whether is solvable.

Case 3  n/d is odd. In this case we only need to consider , then the Walsh spectrum distribution ofis presented in Ref. [15].

The last class comes from the product of linearized polynomials which have three or four Walsh transform values. With the help of k-tuple balance property, the Walsh spectrum distribution of such functions are determined. Ref. [15] present the Walsh transform of together with the Walsh transform of Eq. (2), the Walsh spectrum distribution ofis given.

In another particular case, when f(x)=0 and , the function is studied by Wu et al[16]. They give the necessary and sufficient conditions for g(x) to be negabent.

Corollary 2   Let , where . Then g(x) is negabent on if and only if one of the following conditions is satisfied:

1) and .

2) and .

In Ref. [16], first they presented the necessary and sufficient conditions for the functionsto be negabent, where n=2k, , , when it is the one discussed in Ref. [16]. Further, by using some permutation trinomials over , they presented some classes of negabent functions of the formwhere 0<k<n.

3 Conclusion

In this paper, we proposed the Walsh transform of a class of Boolean functions by using the properties of the Walsh transform and the trace function. Then, we hope that we can deduce the Walsh spectrum distributions of g(x) defined as Eq. (1) by suitable choices of f(x) and h(x). Further, several new classes of Boolean functions with few Walsh transform values are obtained.

References

  1. Carlet C, Mesnager S. Four decades of research on bent functions [J]. Designs, Codes and Cryptography, 2016, 78(1): 5-50. [Google Scholar]
  2. Mesnager S. On Semi-Bent Functions and Related Plateaued Functions over the Galois Field [M]. Berlin: Springer-Verlag, 2014. [Google Scholar]
  3. Tu Z B, Zheng D B, Zeng X Y, et al. Boolean functions with two distinct Walsh coefficients [J]. Applicable Algebra in Engineering Communication and Computing, 2011, 22(5-6): 359-366. [Google Scholar]
  4. Rothaus O S. On “bent” functions [J]. Journal of Combinatorial Theory, 1976, 20(3): 300-305. [Google Scholar]
  5. Frances M, Litman A. On covering problems of codes [J]. Theory of Computing Systems, 1997, 30(2): 113-119. [CrossRef] [MathSciNet] [Google Scholar]
  6. Calderbank R, Kantor W M. The geometry of two-weight codes [J]. Bulletin of the London Mathematical Society, 1986, 18(2): 97-122. [Google Scholar]
  7. Carlet C. Boolean functions for cryptography and error-correcting codes [J]. Encyclopedia of Mathematics and Its Applications, 2016, 78(1): 5-50. [Google Scholar]
  8. Olsen J, Scholtz R, Welch L. Bent-function sequences [J]. IEEE Transactions on Information Theory, 1982, 28(6): 858-864. [CrossRef] [MathSciNet] [Google Scholar]
  9. Carlet C. Boolean and vectorial plateaued functions and APN functions [J]. IEEE Transactions on Information Theory, 2015, 61(11): 6272-6289. [CrossRef] [MathSciNet] [Google Scholar]
  10. Sun Z Q, Hu L. Boolean functions with four-valued Walsh spectra [J]. Journal of Systems Science and Complexity, 2015, 28(3): 743-754. [CrossRef] [MathSciNet] [Google Scholar]
  11. Jin W G, Du X N, Sun Y Z, et al. Boolean functions with six-valued Walsh spectra and their application [J]. Cryptography and Communications, 2021, 13(5): 393-405. [Google Scholar]
  12. Xu G K, Cao X W, Xu S D. Several new classes of Boolean functions with few Walsh transform values [J]. Applicable Algebra in Engineering Communication and Computing, 2017, 28(2): 155-176. [Google Scholar]
  13. Tang C M, Zhou Z C, Qi Y F, et al. Generic construction of bent functions and bent idempotents with any possible algebraic degrees [J]. IEEE Transactions on Information Theory, 2017, 63(10): 6149-6157. [CrossRef] [MathSciNet] [Google Scholar]
  14. Mesnager S. Several new infinite families of bent functions and their duals [J]. IEEE Transactions on Information Theory, 2014, 60(7): 4397-4407. [CrossRef] [MathSciNet] [Google Scholar]
  15. Pang T T, Li N, Zhang L, et al. Several new classes of (balanced) Boolean functions with few Walsh transform values [J]. Advances in Mathematics of Communications, 2021, 15(4): 757-775. [Google Scholar]
  16. Wu G F, Li N, Zhang Y Q, et al. Several classes of negabent functions over finite fields [J]. Science China. Information Sciences, 2018, 61(3): 1-3. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.