Affine equivalence for quadratic rotation symmetric Boolean functions

DOI10.1007/S10623-020-00748-5MaRDI QIDQ780372zbMATH OpenOpenAlexFDO

Authors Thomas W. Cusick, Alexandru Chirvasitu

Publication date 15 July 2020

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.08448

zbMATH Keywords

Boolean functionHamming weightrecursionrotation symmetric

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Cryptography (94A60) Boolean functions (94D10)

Abstract: 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 $ngeqd$ 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_0{x}_{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.

Review text

A function \(f\) from \(\mathbb{F}_2^n\) to \(\mathbb{F}_2\) is called rotation symmetric (RS) if \(f(x_0,x_1,\ldots,x_{n-1}) = f(x_1,\ldots,x_{n-1},x_0)\) for all \((x_0,x_1,\ldots,x_{n-1})\in\mathbb{F}_2^n\). An RS function \(f\) is called monomial rotation symmetric (MRS) if \(f\) is generated by a monomial (the algebraic normal form of \(f\) consists of the shifts of one monomial). The authors investigate a recursion formula for the weights of quadratic RS functions. As application, the authors show statements on balancedness of quadratic RS functions, the number of affine equivalence classes of quadratic MRS functions is given.

Recommendations

• The weight recursions for the 2-rotation symmetric quartic Boolean functions
• On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2
• Weights for short quartic Boolean functions
• A recursive formula for weights of Boolean rotation symmetric functions
• Theory of 2-rotation symmetric cubic Boolean functions

Cites work

• A new characterization of semi-bent and bent functions on finite fields
• A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions
• Affine equivalence of cubic homogeneous rotation symmetric functions
• Constructions of Quadratic and Cubic Rotation Symmetric Bent Functions
• Cryptographic Boolean functions and applications
• scientific article; zbMATH DE number 3957242 (Why is no real title available?)
• scientific article; zbMATH DE number 1973372 (Why is no real title available?)
• scientific article; zbMATH DE number 5785317 (Why is no real title available?)
• Idempotent and \(p\)-potent quadratic functions: distribution of nonlinearity and co-dimension
• Linearized polynomials over finite fields revisited
• On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2
• Permutation equivalence of cubic rotation symmetric Boolean functions
• Weight recursions for any rotation symmetric Boolean functions

Cited in

(16)

• Affine equivalence of quartic monomial rotation symmetric Boolean functions in prime power dimension
• On the matrix of rotation symmetric Boolean functions
• Equivalence of 2-rotation symmetric quartic Boolean functions
• Using inclusion/exclusion to find bent and balanced monomial rotation symmetric functions
• Weights for short quartic Boolean functions
• Symbolic dynamics and rotation symmetric Boolean functions
• Circulant matrices and affine equivalence of monomial rotation symmetric Boolean functions
• Affine equivalence of monomial rotation symmetric Boolean functions: a Pólya's theorem approach
• The weight recursions for the 2-rotation symmetric quartic Boolean functions
• Quadratic rotation symmetric Boolean functions
• Using easy coefficients conjecture for rotation symmetric Boolean functions
• Quadratic truncated rotation symmetric Boolean functions
• Recursions for quadratic rotation symmetric functions weights
• Extended quadratic truncated rotation symmetric Boolean functions
• On the conjecture about the nonexistence of homogeneous rotation symmetric bent functions
• Permutation equivalence of k-rotation symmetric monomial Boolean functions

This page was built for publication: Affine equivalence for quadratic rotation symmetric Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q780372)