Search

Let $(0, a_1, \ldots, a_{d-1})_n$ denote the function $f_n(x_0, x_1, \ldots, x_{n-1})$ of degree $d$ in $n$ variables generated by the monomial $x_0x_{a_1} \cdots x_{a_{d-1}}$ and having the property that $f_n$ is invariant under cyclic permutations of the variables. Such a function $f_n$ is called monomial rotation symmetric (MRS). Much of this paper extends the work on quadratic MRS functions in a $2020$ paper of the authors to the case of binomial RS functions, that is sums of two quadratic MRS functions. There are also some results for the sum of any number of quadratic MRS functions., Comment: 20 pages + references

We identify the weights $wt(f_n)$ of a family $\{f_n\}$ of rotation symmetric Boolean functions with the cardinalities of the sets of $n$-periodic points of a finite-type shift, recovering the second author's result that said weights satisfy a linear recurrence. Similarly, the weights of idempotent functions $f_n$ defined on finite fields can be recovered as the cardinalities of curves over those fields and hence satisfy a linear recurrence as a consequence of the rationality of curves' zeta functions. Weil's Riemann hypothesis for curves then provides additional information about $wt(f_n)$. We apply our results to the case of quadratic functions and considerably extend the results in an earlier paper of ours., Comment: 23 pages + references

Let $f_n(x_0, x_1, \ldots, x_{n-1})$ denote the algebraic normal form (polynomial form) of a rotation symmetric (RS) Boolean function of degree $d$ in $n \geq d$ variables and let $wt(f_n)$ denote the Hamming weight of this function. Let $(0, a_1, \ldots, a_{d-1})_n$ denote the function $f_n$ of degree $d$ in $n$ variables generated by the monomial $x_0x_{a_1} \cdots x_{a_{d-1}}.$ Such a function $f_n$ is called monomial rotation symmetric (MRS). It was proved in a $2012$ paper that for any MRS $f_n$ with $d=3,$ the sequence of weights $\{w_k = wt(f_k):~k = 3, 4, \ldots\}$ satisfies a homogeneous linear recursion with integer coefficients. This result was gradually generalized in the following years, culminating around $2016$ with the proof that such recursions exist for any rotation symmetric function $f_n.$ Recursions for quadratic RS functions were not explicitly considered, since a $2009$ paper had already shown that the quadratic weights themselves could be given by an explicit formula. However, this formula is not easy to compute for a typical quadratic function. This paper shows that the weight recursions for the quadratic RS functions have an interesting special form which can be exploited to solve various problems about these functions, for example, deciding exactly which quadratic RS functions are balanced., Comment: 27 pages + references; minor typo corrections

Given a Boolean function f, the (Hamming) weight wt(f) and the nonlinearity N(f) are well known to be important in designing functions that are useful in cryptography. The nonlinearity is expensive to compute, in general, so any shortcuts for doing that for particular functions f are significant. The well known majority function has been extensively studied in a cryptographic context for the last dozen years or so, and there is a formula for its nonlinearity. The known proofs for this formula rely on many detailed results for the Krawtchouk polynomials. This paper gives a much simpler proof., Comment: 10 pages, LaTeX; better title and abstract; reference added; revised proofs

Let $f_n(x_1, x_2, \ldots, x_n)$ denote the algebraic normal form (polynomial form) of a rotation symmetric Boolean function of degree $d$ in $n \geq d$ variables and let $wt(f_n)$ denote the Hamming weight of this function. Let $(1, a_2, \ldots, a_d)_n$ denote the function $f_n$ of degree $d$ in $n$ variables generated by the monomial $x_1x_{a_2} \cdots x_{a_d}.$ Such a function $f_n$ is called {\em monomial rotation symmetric} (MRS). It was proved in a $2012$ paper that for any MRS $f_n$ with $d=3,$ the sequence of weights $\{w_k = wt(f_k):~k = 3, 4, \ldots\}$ satisfies a homogeneous linear recursion with integer coefficients. In this paper it is proved that such recursions exist for any rotation symmetric function $f_n;$ such a function is generated by some sum of $t$ monomials of various degrees. The last section of the paper gives a Mathematica program which explicitly computes the homogeneous linear recursion for the weights, given any rotation symmetric $f_n.$ The reader who is only interested in finding some recursions can use the program and not be concerned with the details of the rather complicated proofs in this paper., Comment: 18 pages

Homogeneous rotation symmetric Boolean functions have been extensively studied in recent years because of their applications in cryptography. Little is known about the basic question of when two such functions are affine equivalent. The simplest case of quadratic rotation symmetric functions which are generated by cyclic permutations of the variables in a single monomial was only settled in 2009. This paper studies the much more complicated cubic case for such functions. A new concept of \emph{patterns} is introduced, by means of which the structure of the smallest group G_n, whose action on the set of all such cubic functions in $n$ variables gives the affine equivalence classes for these functions under permutation of the variables, is determined. We conjecture that the equivalence classes are the same if all nonsingular affine transformations, not just permutations, are allowed. This conjecture is verified if n < 22. Our method gives much more information about the equivalence classes; for example, in this paper we give a complete description of the equivalence classes when n is a prime or a power of 3., Comment: This is the author's version of a manuscript which has been accepted by Information Sciences. The ancillary Mathematica file contains a program which computes the equivalence classes described in the paper, given n = number of variables

Under mild conditions on $n,p$, we give a lower bound on the number of $n$-variable balanced symmetric polynomials over finite fields $GF(p)$, where $p$ is a prime number. The existence of nonlinear balanced symmetric polynomials is an immediate corollary of this bound. Furthermore, we conjecture that $X(2^t,2^{t+1}l-1)$ are the only nonlinear balanced elementary symmetric polynomials over GF(2), where $X(d,n)=\sum_{i_1

We study the nonlinearity and the weight of the rotation-symmetric (RotS) functions defined by Pieprzyk and Qu. We give exact results for the nonlinearity and weight of 2-degree RotS functions with the help of the semi-bent functions and we give the generating function for the weight of the 3-degree RotS function. Based on the numerical examples and our observations we state a conjecture on the nonlinearity and weight of the 3-degree RotS functions., Comment: 20 pages; submitted to Discrete Mathematics