Boolean plateaued functions and vectorial functions with plateaued components play a significant role in cryptography, sequences for communications, and the related combinatorics and designs. Our ...knowledge on them is not at a level corresponding to their importance. We introduce new characterizations of plateaued Boolean functions. We give the characterizations of vectorial functions whose components are all plateaued (with possibly different amplitudes), that we simply call plateaued, by means of the value distributions of their derivatives (we characterize similarly those functions whose components are partially bent) and autocorrelation functions, and of the power moments of their Walsh transform. This allows us to derive several characterizations of almost perfect nonlinear (APN) functions in this framework. We prove that all the main results known for quadratic APN functions extend to plateaued functions, allowing the study of their APN-ness to be simplified. We show that if, additionally, the component functions are all unbalanced, this study is still simpler: the APN-ness of such functions depends only on their value distribution. This allows proving, for instance, that any plateaued (n, n)-function, n even, having similar value distribution as the APN power functions, is APN, and has the same extended Walsh spectrum as the APN Gold functions. As by-products, we obtain a few other new results. For instance, any plateaued function in even dimension, which is Carlet-Charpin-Zinoviev (CCZ)-equivalent to a Gold or Kasami APN function, is necessarily extended affine (EA)-equivalent to it.
Determining the weight distribution of all Reed-Muller codes is a huge and exciting problem that has been around since the sixties. Some progress has been made very recently, but we are still far ...from a solution. In this paper, we addressed the subproblem of determining as many codeword weights as possible in Reed-Muller codes of any lengths and any orders, which is decisive for determining their weight spectra (i.e., the lists of all possible weights in these codes). New approaches seem necessary for both the main problem and the subproblem. We first studied the difficulties and the limits of the approach, which consisted of using the usual primary and secondary constructions of Boolean functions for the purpose of determining as many weights as possible in Reed-Muller codes. We then introduced a way, different from the usual constructions, to generate Boolean functions in $ n $ variables having an algebraic degree bounded from above, without any restriction on $ n $, and whose Hamming weights can be determined. This provided weights in Reed-Muller codes of any lengths $ 2^n $ and any orders, allowing us to reach potentially new values in the weight spectra of Reed-Muller codes (as we illustrate with all Reed-Muller codes of lengths up to $ 2^{21} $), with the related codewords being given with their supports and their algebraic normal forms being mathematically derived.
New Characterization and Parametrization of LCD Codes Carlet, Claude; Mesnager, Sihem; Tang, Chunming ...
IEEE transactions on information theory,
2019-Jan., 2019-1-00, 20190101, 2019, Volume:
65, Issue:
1
Journal Article
Peer reviewed
Open access
Linear complementary dual (LCD) cyclic codes were referred historically to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, ...there has been renewed interest in LCD codes. In particular, it has been shown that binary LCD codes play an important role in implementations against side-channel attacks and fault injection attacks. In this paper, we first present a new characterization of binary LCD codes in terms of their orthogonal or symplectic basis. Using such a characterization, we solve a conjecture proposed by Galvez et al. on the minimum distance of binary LCD codes. Next, we consider the action of the orthogonal group on the set of all LCD codes, determine all possible orbits of this action, derive simple closed formulas of the size of the orbits, and present some asymptotic results on the size of the corresponding orbits. Our results show that almost all binary LCD codes are odd-like codes with odd-like duals, and about half of q-ary LCD codes have orthonormal basis, where q is a power of an odd prime.
We survey the properties of two parameters introduced by C. Ding and the author for quantifying the balancedness of vectorial functions and of their derivatives. We give new results on the ...distribution of the values of the first parameter when applied to
F
+
L
, where
F
is a fixed function and
L
ranges over the set of linear functions: we show an upper bound on the nonlinearity of
F
by means of these values, we determine then the mean of these values and we show that their maximum is a nonlinearity parameter as well, we prove that the variance of these values is directly related to the second parameter. We briefly recall the known constructions of bent vectorial functions and introduce two new classes obtained with Gregor Leander. We show that bent functions can be used to build APN functions by concatenating the outputs of a bent (
n
,
n
/2)-function and of some other (
n
,
n
/2)-function. We obtain this way a general infinite class of quadratic APN functions. We show that this class contains the APN trinomials and hexanomials introduced in 2008 by L. Budaghyan and the author, and a class of APN functions introduced, in 2008 also, by Bracken et al.; this gives an explanation of the APNness of these functions and allows generalizing them. We also obtain this way the recently found Edel–Pott cubic function. We exhibit a large number of other sub-classes of APN functions. We eventually design with this same method classes of quadratic and non-quadratic differentially 4-uniform functions.
The correlation immunity of Boolean functions is a property related to cryptography, to error correcting codes, to orthogonal arrays (in combinatorics), and in a slightly looser way to sequences. ...Correlation-immune Boolean functions (in short, CI functions) have the property of keeping the same output distribution when some input variables are fixed. They have been widely used as combiners in stream ciphers to allow resistance to the Siegenthaler correlation attack. Very recently, a new use of CI functions has appeared in the framework of side channel attacks (SCA). To reduce the cost overhead of counter-measures to SCA, CI functions need to have low Hamming weights. This actually poses new challenges since the known constructions which are based on properties of the Walsh-Hadamard transform, do not allow to build unbalanced CI functions. In this paper, we propose constructions of low-weight <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula>th-order CI functions based on the Fourier-Hadamard transform, while the known constructions of resilient functions are based on the Walsh-Hadamard transform. These two transforms are closely related but the resulting constructions are very different. We first prove a simple but powerful result, which makes that one only need to consider the case where <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula> is odd in further research. Then, we investigate how constructing low Hamming weight CI functions through the Fourier-Hadamard transform (which behaves well with respect to the multiplication of Boolean functions). We use the characterization of CI functions by the Fourier-Hadamard transform and introduce a related general construction of CI functions by multiplication. By using the Kronecker product of vectors, we obtain more constructions of low-weight <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula>-CI Boolean functions. Furthermore, we present a method to construct low-weight d-CI Boolean functions by making additional restrictions on the supports built from the Kronecker product.
In the independent works by Kalgin and Idrisova and by Beierle, Leander and Perrin, it was observed that the Gold APN functions over
F
2
5
give rise to a quadratic APN function in dimension 6 having ...maximum possible linearity of
2
5
(that is, minimum possible nonlinearity
2
4
). In this article, we show that the case of
n
≤
5
is quite special in the sense that Gold APN functions in dimension
n
>
5
cannot be extended to quadratic APN functions in dimension
n
+
1
having maximum possible linearity. In the second part of this work, we show that this is also the case for APN functions of the form
x
↦
x
3
+
μ
(
x
)
with
μ
being a quadratic Boolean function.
The weight spectra (i.e. the lists of all possible weights) of the Reed-Muller codes <inline-formula> <tex-math notation="LaTeX">RM(r,m) </tex-math></inline-formula>, of length <inline-formula> ...<tex-math notation="LaTeX">2^{m} </tex-math></inline-formula> and order <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula>, are unknown for <inline-formula> <tex-math notation="LaTeX">r\in \{3, {\dots },m-5\} </tex-math></inline-formula> (and <inline-formula> <tex-math notation="LaTeX">m </tex-math></inline-formula> large enough). Those of <inline-formula> <tex-math notation="LaTeX">RM(m-4,m) </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">RM(m-3,m) </tex-math></inline-formula> have been determined very recently (but not the weight distributions, giving the number of codewords of each weight, which seem out of reach). We determine the weight spectrum of <inline-formula> <tex-math notation="LaTeX">RM(m-5,m) </tex-math></inline-formula> for every <inline-formula> <tex-math notation="LaTeX">m\ge 10 </tex-math></inline-formula>. We proceed by first determining the weights in <inline-formula> <tex-math notation="LaTeX">RM(5,10) </tex-math></inline-formula>. To do this, we construct functions whose weights are in the set <inline-formula> <tex-math notation="LaTeX">\{62, 74, 78, 82, 86, 90\} </tex-math></inline-formula>, and functions whose weights are all the integers between 94 and <inline-formula> <tex-math notation="LaTeX">2^{9}-2=510 </tex-math></inline-formula> that are congruent with 2 modulo 4 (those weights that are divisible by 4 are easier to determine and they are indeed known). This allows us to determine completely the weight spectrum, thanks to the well-known result due to Kasami, Tokura and Azumi, which precisely determines those codeword weights in Reed-Muller codes which lie between the minimum distance <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula> and 2.5 times <inline-formula> <tex-math notation="LaTeX">d </tex-math></inline-formula>, and thanks to the fact the weight spectrum is symmetric with respect to 29. Then we use this particular weight spectrum for determining that of <inline-formula> <tex-math notation="LaTeX">RM(m-5,m) </tex-math></inline-formula>, by an induction on <inline-formula> <tex-math notation="LaTeX">m </tex-math></inline-formula>. We check that a recent conjecture (in which we correct a misprint) on the weight spectrum of <inline-formula> <tex-math notation="LaTeX">RM(m-c,m) </tex-math></inline-formula> is verified for <inline-formula> <tex-math notation="LaTeX">c=5 </tex-math></inline-formula>, and we study the difficulties of trying to extend the results to <inline-formula> <tex-math notation="LaTeX">c\geq 6 </tex-math></inline-formula>.
In this work we give several generalizations of the isotopic shift construction, introduced recently by Budaghyan et al. (IEEE Trans Inform Theory 66:5299–5309, 2020), when the initial function is a ...Gold function. In particular, we derive a general construction of APN functions which covers several unclassified APN functions for
n
=
8
and produces fifteen new APN functions for
n
=
9
.
PDF
