On q -ary bent and plateaued functions
- PDF / 343,250 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 223 Views
On q-ary bent and plateaued functions Vladimir N. Potapov1 Received: 16 November 2019 / Revised: 27 March 2020 / Accepted: 11 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We obtain the following results. For any prime p the minimal Hamming distance between distinct regular p-ary bent functions of 2n variables is equal to p n . The number of p-ary regular bent functions at the distance p n from the quadratic bent function Q n = x1 x2 + · · · + x2n−1 x2n is equal to p n ( p n−1 + 1) · · · ( p + 1)( p − 1) for p > 2. The Hamming distance s+n−2 between distinct binary s-plateaued functions of n variables is not less than 2 2 and the Hamming distance between distinct ternary s-plateaued functions of n variables is not less s+n−1 than 3 2 . These bounds are tight. For p = 3 we prove an upper bound on nonlinearity of ternary functions in terms of their correlation immunity. Moreover, functions reaching this bound are plateaued. For p = 2 analogous result are well known but for large p it seems impossible. Constructions and some properties of p-ary plateaued functions are discussed. Keywords Plateaued function · Bent function · Correlation immune function · Hamming distance · Nonlinearity Mathematics Subject Classification 94A60 · 94C10 · 06E30
1 Introduction Boolean bent and plateaued functions play a significant role in information theory and combinatorics. These functions are intensively studied at present as they have numerous applications in cryptography, coding theory, and other areas. Bent functions are known as Boolean functions with maximal nonlinearity. q-Ary generalizations of bent functions are also interesting mathematical object (see [21]). Boolean plateaued functions generalize functions with maximal nonlinearity. Moreover, some Boolean plateaued functions achieve tradeoff between properties of nonlinearity and correlation immunity. Recently Mesnager at al. [11] redefined
Communicated by Y. Zhou. The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (Project No. 0314-2019-0017).
B 1
Vladimir N. Potapov [email protected] Sobolev Institute of Mathematics, Novosibirsk, Russia
123
V. N. Potapov
plateaued functions over any finite field Fq where q is a prime power, and established their properties. In this paper (Sect. 6) we generalize some methods in order to construct binary plateaued functions for q-ary plateaued functions. The Hamming distance d( f , g) between two discrete functions f and g is the number of arguments where these functions differ. In other words, the Hamming distance between two functions f and g is the cardinality of the support {x ∈ Dom( f ) | f (x) = g(x)} of their difference. The problem of finding the minimal Hamming distance between two functions of the same type is known as the problem of the minimum-support bitrade (see [6]). A series of results on calculation of the minimal Hamming distance between Boolean bent and correlation immune functions can be found in [4] and [13].
Data Loading...
