Abstract: Abstract A set \(S \subseteq {{\mathbb {F}}_{2}^{n}}\) is called degree-d zero-sum if the sum \({\sum }_{s \in S} f(s)\) vanishes for all n-bit Boolean functions of algebraic degree at most d. Those sets correspond to the supports of the n-bit Boolean functions of degree at most n − d − 1. We prove some results on the existence of degree-d zero-sum sets of full rank, i.e., those that contain n linearly independent elements, and show relations to degree-1 annihilator spaces of Boolean functions and semi-orthogonal matrices. We are particularly interested in the smallest of such sets and prove bounds on the minimum number of elements in a degree-d zero-sum set of rank n. The motivation for studying those objects comes from the fact that degree-d zero-sum sets of full rank can be used to build linear mappings that preserve special kinds of nonlinear invariants, similar to those obtained from orthogonal matrices and exploited by Todo, Leander and Sasaki for breaking the block ciphers Midori, Scream and iScream. PubDate: 2019-11-19

Abstract: Abstract We present a new construction of a family of perfect ternary sequences (PTSs) that is a generalization of one of the known families of PTSs. These PTSs of length N1N2 are derived from shift sequences of odd length N1 corresponding to m-sequences over GF(p) and PTSs of odd length N2. Ipatov PTSs are a special case where N2 = 1. For N2 ≥ 3, we find conditions under which the obtained PTSs are new. We also consider implementation issues of these sequences. PubDate: 2019-11-16

Abstract: Abstract Recently, a class of binary sequences with optimal autocorrelation magnitude has been presented by Su et al. based on Ding-Helleseth-Lam sequences and interleaving technique (Designs, Codes and Cryptography 86, 1329–1338, 2018). The linear complexity of this class of sequences has been proved to be large enough to resist the B-M Algorithm by Fan (Designs, Codes and Cryptography 86, 2441–2450, 2018). In this paper, we study the 2-adic complexities of these sequences with period 4p and show they are no less than 2p, i.e., its 2-adic complexity is large enough to resist the Rational Approximation Algorithm. PubDate: 2019-11-14

Abstract: Abstract Determine the number of the rational zeros of any given linearized polynomial is one of the vital problems in finite field theory, with applications in modern symmetric cryptosystems. But, the known general theory for this task is much far from giving the exact number when applied to a specific linearized polynomial. The first contribution of this paper is a better general method to get a more precise upper bound on the number of rational zeros of any given linearized polynomial over arbitrary finite field. We anticipate this method would be applied as a useful tool in many research branches of finite field and cryptography. Really we apply this result to get tighter estimations of the lower bounds on the second-order nonlinearities of general cubic Boolean functions, which has been an active research problem during the past decade. Furthermore, this paper shows that by studying the distribution of radicals of derivatives of a given Boolean function one can get a better lower bound of the second-order nonlinearity, through an example of the monomial Boolean functions \(g_{\mu }=Tr(\mu x^{2^{2r}+2^{r}+1})\) defined over the finite field \({\mathbb F}_{2^{n}}\). PubDate: 2019-11-13

Abstract: Abstract Complementary sequences with quadrature amplitude modulation (QAM) symbols have important applications in OFDM communication systems. The objective of this paper is to present two constructions of 16-QAM complementary sequence sets of size 4. The first construction generates four complementary sequences of length L = 2m− 1 + 2v, where m and v are two positive integers with 1 ≤ v ≤ m − 1. The second one leads to four complementary sequences of length L = 2m− 1 + 1. It turns out that the peak-to-mean envelope power ratios (PMEPRs) of constructed complementary sequence sets are upper bounded by 4. PubDate: 2019-11-12

Abstract: Abstract Due to the wide applications in communications, data storage and cryptography, linear codes have received much attention in the past decades. As a subclass of linear codes, minimal linear codes can be used to construct secret sharing with nice access structure. The objective of this paper is to construct new classes of minimal binary linear codes with \(w_{\min \limits }/w_{\max \limits }\leq 1/2\) from preferred binary linear codes, where \(w_{\min \limits }\) and \(w_{\max \limits }\) denote the minimum and maximum nonzero Hamming weights in \(\mathcal {C}\) respectively. Firstly, we introduce a concept called preferred binary linear codes and a class of minimal binary linear codes with \(w_{\min \limits }/w_{\max \limits }\leq 1/2\) can be deduced from preferred binary linear codes. As an application of preferred binary linear codes, we get a new class of six-weight minimal binary linear codes with \(w_{\min \limits }/w_{\max \limits }< 1/2\) from a known class of five-weight preferred binary linear codes. Secondly, by employing vectorial Boolean functions, we construct two new classes of preferred binary linear codes and, consequently, these two new classes of preferred binary linear codes can generate two new classes of minimal binary linear codes with \(w_{\min \limits }/w_{\max \limits }\leq 1/2\) and large minimum distance. PubDate: 2019-11-08

Abstract: Abstract A quaternary sequence is said to be optimal if its odd-periodic autocorrelation magnitude equal to 2 for even length, and 1 for odd length. In this paper, we propose three constructions of optimal quaternary sequences: the first construction applies the inverse Gray mapping to four component binary sequences, which could be chosen from GMW sequence pair, twin-prime sequence pair, Legendre sequence pair, and ideal sequences; the second one generates optimal sequences from quaternary sequences with optimal even-periodic autocorrelation magnitude; the third one gives new optimal quaternary sequences by applying the sign alternation transform and Gray mapping to GMW sequence pair and twin-prime sequence pair. In particular, some proposed sequences have new parameters. PubDate: 2019-11-08

Abstract: Abstract Constacyclic codes are a subclass of linear codes and have been well studied. Constacyclic BCH codes are a family of constacyclic codes and contain BCH codes as a subclass. Compared with the in-depth study of BCH codes, there are relatively little study on constacyclic BCH codes. The objective of this paper is to determine the dimension and minimum distance of a class of q-ary constacyclic BCH codes of length \(\frac {q^{m}-1}{q-1}\) with designed distances \(\delta _{i}=q^{m-1}-\frac {q^{\lfloor \frac {m-3}2 \rfloor +i }-1}{q-1}\) for \(1\leq i\leq \min \limits \{\lceil \frac {m+1}2 \rceil -\lfloor \frac {m}{q+1} \rfloor , \lceil \frac {m-1}2 \rceil \}\) . As will be seen, some of these codes are optimal. PubDate: 2019-11-06

Abstract: Abstract In the last few decades we’ve seen several results connecting the image sets of some special functions to differences sets and partial difference sets. Examples here include planar functions (skew-Hadamard difference sets), and (more classically) monomials (cyclotomic DS). It can be observed that there is a commonality (in the main) among the behaviour of these functions, in that there tends to be a certain regularity in the number of times each image occurs. In this paper, we instigate a new approach to constructing sets with regularity of differences based on the above observation. Specifically, we show how functions over finite fields exhibiting a regularity of images can yield image sets that exhibit some sort of difference regularity. PubDate: 2019-11-01

Abstract: Abstract A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a Boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (J. ACM 22(2), 195–201, 1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. (Theor. Comput. Sci. 235(1), 43–57, 2000) and by Boyar and Peralta (Theor. Comput. Sci. 396(1–3), 223–246, 2008). We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions \({{\Sigma }^{n}_{k}}\) and counting functions \({E^{n}_{k}}\) with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric \({{\Sigma }^{8}_{4}}\) and the counting \({E^{8}_{4}}\) functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132. PubDate: 2019-11-01

Abstract: Abstract In this paper, we study some properties of a certain kind of permutation σ over \(\mathbb {F}_{2}^{n}\), where n is a positive integer. The desired properties for σ are: (1) the algebraic degree of each component function is n − 1; (2) the permutation is unicyclic; (3) the number of terms of the algebraic normal form of each component is at least 2n− 1. We call permutations that satisfy these three properties simultaneously unicyclic strong permutations. We prove that our permutations σ always have high algebraic degree and that the average number of terms of each component function tends to 2n− 1. We also give a condition on the cycle structure of σ. We observe empirically that for n even, our construction does not provide unicylic permutations. For n odd, n ≤ 11, we conduct an exhaustive search of all σ given our construction for specific examples of unicylic strong permutations. We also present some empirical results on the difference tables and linear approximation tables of σ. PubDate: 2019-11-01

Abstract: Abstract Functions f from \({\mathbb {F}_{p}^{n}}\), n = 2m, to \(\mathbb {Z}_{{p}^{k}}\) for which the character sum \(\mathcal {H}^{k}_{f}(p^{t},u)=\sum\limits _{x\in {\mathbb {F}_{p}^{n}}}\zeta _{p^{k}}^{p^{t}f(x)}\zeta _{p}^{u\cdot x}\) (where \(\zeta _{q} = e^{2\pi i/q}\) is a q-th root of unity), has absolute value \(p^{m}\) for all \(u\in {\mathbb {F}_{p}^{n}}\) and \(0\le t\le k-1\), induce relative difference sets in \({\mathbb {F}_{p}^{n}}\times \mathbb {Z}_{{p}^{k}}\) hence are called bent. Functions only necessarily satisfying \( \mathcal {H}^{k}_{f}(1,u) = p^{m}\) are called generalized bent. We show that with spreads we not only can construct a variety of bent and generalized bent functions, but also can design functions from \({\mathbb {F}_{p}^{n}}\) to \(\mathbb {Z}_{{p}^{m}}\) satisfying \( \mathcal {H}_{f}^{m}(p^{t},u) = p^{m}\) if and only if \(t\in T\) for any \(T\subset \{0,1\ldots ,m-1\}\). A generalized bent function can also be seen as a Boolean (p-ary) bent function together with a partition of \({\mathbb {F}_{p}^{n}}\) with certain properties. We show that the functions from the completed Maiorana-McFarland class are bent functions, which allow the largest possible partitions. PubDate: 2019-11-01

Abstract: Abstract Whether there exist Almost Perfect Non-linear permutations (APN) operating on an even number of bits is the so-called Big APN Problem. It has been solved in the 6-bit case by Dillon et al. in 2009 but, since then, the general case has remained an open problem. In 2016, Perrin et al. discovered the butterfly structure which contains Dillon et al.’s permutation over \(\mathbb {F}_{2^{6}}\). Later, Canteaut et al. generalised this structure and proved that no other butterflies with exponent 3 can be APN. Recently, Yongqiang et al. further generalized the structure with Gold exponent and obtained more differentially 4-uniform permutations with optimal nonlinearity. However, the existence of more APN permutations in their generalization was left as an open problem. In this paper, we adapt the proof technique of Canteaut et al. to handle all Gold exponents and prove that a generalised butterfly with Gold exponents over \(\mathbb {F}_{2^{n}}\) can never be APN when n > 3. More precisely, we prove that such a generalised butterfly being APN implies that the branch size is strictly smaller than 5. Hence, the only APN butterflies operate on 3-bit branches, i.e. on 6 bits in total. PubDate: 2019-11-01

Abstract: Abstract We investigate a construction in which a vectorial Boolean function G is obtained from a given function F over \(\mathbb {F}_{2^{n}}\) by changing the values of F at two points of the underlying field. In particular, we examine the possibility of obtaining one APN function from another in this way. We characterize the APN-ness of G in terms of the derivatives and in terms of the Walsh coefficients of F. We establish that changing two points of a function F over \(\mathbb {F}_{2^{n}}\) which is plateaued (and, in particular, AB) or of algebraic degree deg(F) < n − 1 can never give a plateaued (and AB, in particular) function for any n ≥ 5. We also examine a particular case in which we swap the values of F at two points of \(\mathbb {F}_{2^{n}}\). This is motivated by the fact that such a construction allows us to obtain one permutation from another. We obtain a necessary and sufficient condition for the APN-ness of G which we then use to show that swapping two points of any power function over a field \(\mathbb {F}_{2^{n}}\) with n ≥ 5 can never produce an APN function. We also list some experimental results indicating that the same is true for the switching classes from Edel and Pott (Adv. Math. Commun. 3(1):59–81, 2009), and conjecture that the Hamming distance between two APN functions cannot be equal to two for n ≥ 5. PubDate: 2019-11-01

Abstract: Abstract Recently, Tu, Zeng, Li, and Helleseth considered trinomials of the form \(f(X)=X+aX^{q(q-1)+ 1}+bX^{2(q-1)+ 1}\in \mathbb {F}_{q^{2}}[X]\), where q is even and \(a,b\in \mathbb {F}_{q^{2}}^{*}\). They found sufficient conditions on a, b for f to be a permutation polynomial (PP) of \(\mathbb {F}_{q^{2}}\) and they conjectured that the sufficient conditions are also necessary. The conjecture has been confirmed by Bartoli using the Hasse-Weil bound. In this paper, we give an alternative solution to the question. We also use the Hasse-Weil bound, but in a different way. Moreover, the necessity and sufficiency of the conditions are proved by the same approach. PubDate: 2019-11-01

Abstract: Abstract We show the existence of many infinite classes of permutations over finite fields and bent functions by extending the notion of linear translators, introduced by Kyureghyan (J. Combin. Theory Ser. A 118(3), 1052–1061, 2011). We call these translators Frobenius translators since the derivatives of \(f:{\mathbb F}_{p^{n}} \rightarrow {\mathbb F}_{p^{k}}\), where n = rk, are of the form \(f(x+u\gamma )-f(x)=u^{p^{i}}b\), for a fixed \(b \in {\mathbb F}_{p^{k}}\) and all \(u \in {\mathbb F}_{p^{k}}\), rather than considering the standard case corresponding to i = 0. It turns out that Frobenius translators correspond to standard linear translators of an exponentiated version of f, namely to \(f^{p^{k-i}}\) with respect to \(b^{p^{k-i}}\). Nevertheless, this concept turns out to be useful for providing further explicit specification of a rather rare family {f} of quadratic polynomials (especially sparse ones) admitting linear translators. In this direction, we solve a few open problems in the recent article (Cepak et al., Finite Fields Appl. 45, 19–42, 2017) concerning the existence and an exact specification of f admitting classical linear translators. In addition, an open problem introduced in Hodžić et al. (2018), of finding a triple of bent functions f1,f2,f3 such that their sum f4 is bent and that the sum of their duals satisfies \(f_{1}^{*}+f_{2}^{*}+f_{3}^{*}+f_{4}^{*}=1\), is also resolved. We also specify two huge families of permutations over \({\mathbb F}_{p^{n}}\) related to the condition that \(G(y)=-L(y)+(y+\delta )^{s}-(y+\delta )^{p^{k}s}\) permutes the set \({\mathcal S}=\{\beta \in {\mathbb F}_{p^{n}}: T{r_{k}^{n}}(\beta )=0\}\), where n = 2k and p > 2. Finally, we give some generalizations of constructions of bent functions in Mesnager et al. (2017) and describe some new bent families using the permutations found in Cepak et al. (Finite Fields Appl. 45, 19–42, 2017). PubDate: 2019-11-01

Abstract: Abstract In this paper we investigate generalized Boolean functions whose spectrum is flat with respect to a set of Walsh-Hadamard transforms defined using various complex primitive roots of 1. We also study some differential properties of the generalized Boolean functions in even dimension defined in terms of these different characters. We show that those functions have similar properties to the vectorial bent functions. We next clarify the case of gbent functions in odd dimension. As a by-product of our proofs, more generally, we also provide several results about plateaued functions. Furthermore, we find characterizations of plateaued functions with respect to different characters in terms of second derivatives and fourth moments. PubDate: 2019-11-01

Abstract: Abstract Bent functions are a kind of Boolean functions which have the maximum Hamming distance to linear and affine functions, they have some interesting applications in combinatorics, coding theory, cryptography and sequences. However, generally speaking, how to find new bent functions is a hard work and is a hot research project during the past decades. A subclass of bent functions that has received attention since Dillon’s seminal thesis (1974) is the subclass of those Boolean functions that are equal to their dual (or Fourier transform in Dillon’s terminology): the so-called self dual bent functions. In this paper, we propose a construction of involutions from linear translators, and provide two methods for constructing new involutions by utilizing some given involutions. With the involutions presented in this paper, several new classes of self-dual bent functions are produced. PubDate: 2019-11-01

Abstract: Abstract In this paper, we study two special subsets of a finite field of odd characteristics associated with non-weakly regular bent functions. We show that those subsets associated to non-weakly regular even bent functions in the GMMF class (see Çesmelioğlu et al. Finite Fields Appl. 24, 105–117 2013) are never partial difference sets (PDSs), and are PDSs if and only if they are trivial subsets. Moreover, we analyze the two known sporadic examples of non-weakly regular ternary bent functions given in Helleseth and Kholosha (IEEE Trans. Inf. Theory 52(5), 2018–2032 2006, Cryptogr. Commun. 3(4), 281–291 2011). We observe that corresponding subsets are non-trivial partial difference sets. We show that they are the union of some cyclotomic cosets and so correspond to 2-class fusion schemes of a cyclotomic scheme. We also present a further construction giving non-trivial PDSs from certain p-ary functions which are not bent functions. PubDate: 2019-09-14