Recently, Tu and Deng proposed a combinatorial conjecture about binary strings, and, on the assumption that the conjecture is correct, they obtained two classes of Boolean functions which are both algebraic immunity optimal, the first of which are also bent functions. The second class gives balanced functions, which have optimal algebraic degree and the best nonlinearity known up to now. In this paper, by using three different approaches, we prove the conjecture for many cases. We also propose some problems about the weight equations which are related to this conjecture. Because of the scattered distribution, we predict that an exact count is difficult to obtain, in general.
1 October 2012 in Journal of Mathematical Cryptology
: This paper studies degree 3 Boolean functions in n variables which are rotation symmetric, that is, invariant under any cyclic shift of the indices of the variables. These rotation symmetric functions have been extensively studied in the last dozen years or so because of their importance in cryptography. Let denote the (Hamming) weight of the Boolean function f . We extend and simplify results of Bileschi, Cusick and Padgett, who gave an algorithm for finding a recursion for the sequence , where is the cubic rotation symmetric function generated by the monomial We show that the weights for the function (note this is just the sum of the first terms in the definition of ) satisfy the same recursion as the weights for . We prove the recursion for the weights of by a method based on the work by Bileschi–Cusick–Padgett, but we are able to avoid a lot of the complications in their proofs. In particular, we do not need the technical notion of “ g terms” or the elaborate proof of similarity of certain matrices.
30 December 2011 in Cryptography and Communications
We give some results towards the conjecture that are the only nonlinear balanced elementary symmetric polynomials over GF(2), where t and are any positive integers and X ( d, n ) = Σ 1≤ i1 < i2 <⋯<
i
d ≤ nxi1xi2 ⋯ x
i
d .
31 May 2012 in Finite Fields and Their Applications