Let fn(x1, x2,⋯, xn) denote the algebraic normal form (polynomial form) of a rotation symmetric Boolean function of degree d in n ≥ d variables and let wt(fn) denote the Hamming weight of this function. Let (1, α2,⋯, αd)ndenote the function fnof degree d in n variables generated by the monomial x1xα2⋯xαd. Such a function fnis called monomial rotation symmetric (MRS). It was proved in a 2012 paper that for any MRS fnwith d = 3, the sequence of weights {wk= wt(fk) : k = 3, 4,⋯} satisfies a homogeneous linear recursion with integer coefficients. In this paper, it is proved that such recursions exist for any rotation symmetric function fn; such a function is generated by some sum of t monomials of various degrees. A Mathematica program is available on arxiv.org which explicitly computes the homogeneous linear recursion for the weights, given any rotation symmetric fn. 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.

The authors describe a method for producing Boolean functions of degree d ≥ 3 in n = 2 dk − 1 ( k = 1, 2, …) variables, such that the functions are plateaued and balanced, have high nonlinearity and have no linear structures. The nonlinearity is 2 n −1 − 2 ( n −1)/2 , which is the same as the largest possible nonlinearity for a quadratic function in n (odd) variables (the so‐called ‘quadratic bound’). Their theorem uses some new ideas to generalise a theorem, which gave the case d = 3, in a 2009 paper by Fengrong Zhang et al . They discuss the cryptographic properties and applications for the functions.

It is known that the set of rotation symmetric Boolean functions has many functions with various useful properties for cryptography. This study shows how to construct some families of rotation symmetric functions which are balanced or plateaued. The authors also consider vectorial Boolean functions [that is, maps from GF (2) n to GF (2) m ] which are k ‐rotation symmetric and they give two infinite families of such functions which are permutations with the maximum possible algebraic degree. The families of functions that they give provide a source, which can be searched for functions with other useful cryptographic properties.

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 prove that X(2t, 2t+1lscr-1) are balanced and conjecture that these are the only balanced symmetric polynomials over GF(2), where X(d, n) = Sigma1lesi1<i2<hellip

Periodic binary sequences with the "trinomial property" are considered. A conjecture of Golomb and Gong (see ibid., vol..45, p.1276-9, May 1999) concerning these sequences is disproved.

This paper shows that there is a connection between the crosscorrelation functions of certain binary m-sequences and the value sets of the polynomials x k (1 + x) 2 m - 1 for k in pm 1, pm 2, 4, where x is in the finite field GF(2 2m ). In particular, the size of such value sets is determined by using finite field theory and known results about crosscorrelation functions.

In 1972 Niho gave various conjectures about the crosscorrelation between a binary maximum-length linear shift register sequence and a decimation of that sequence by an integer d. We prove that the crosscorrelation function for two new values of d takes on precisely three values and thereby confirm two of Niho's conjectures.

In 1986, L. Blum, R.I. Blum, and M. Shub introduced the x/sup 2/ mod N generator of pseudorandom bit strings and showed, given certain plausible but unproved hypotheses, that it has the desirable cryptographic property of unpredictability. They also studied the period length of the sequences produced by this generator and proposed a way to guarantee that these sequences will have maximum possible period. In this correspondence we prove that it is very likely that for many values of N the sequences produced by the x/sup 2/ mod N generator are usually not balanced (that is, having equal frequency of 0's and 1's). We further prove that the proposed method for guaranteeing long periods is also very likely to guarantee relatively large imbalances between the frequencies of 0's and 1's. However, we also prove that the average imbalance for these sequences is no worse than what would be expected in a truly random bit string of the same length. Thus our results provide further support for the use of the x/sup 2/ mod N generator in cryptographic applications.>