Nonlinearity of Boolean functions: an algorithmic approach based on multivariate polynomials

2014/04/10 by E. Bellini, Bellini, E., I. Simonetti +3
Computer Science · #Coding theory and cryptography #Digital Filter Design and Implementation #FOS: Computer and information sciences #Information Theory (cs.IT) #Numerical Methods and Algorithms

paper · pdf · doi:10.48550/arxiv.1404.2741

openalex publication_date 2014/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We compute the nonlinearity of Boolean functions with Groebner basis techniques, providing two algorithms: one over the binary field and the other over the rationals. We also estimate their complexity. Then we show how to improve our rational algorithm, arriving at a worst-case complexity of O(n2ⁿ) operations over the integers, that is, sums and doublings. This way, with a different approach, we reach the same complexity of established algorithms, such as those based on the fast Walsh transform.

Related

• An algorithmic approach using multivariate polynomials for the nonlinearity of Boolean functions
• Yet another algorithm to compute the nonlinearity of a Boolean function
• Nonlinearity Computation for Sparse Boolean Functions
• Use of Simple Arithmetic Operations to Construct Efficiently Implementable Boolean functions Possessing High Nonlinearity and Good Resistance to Algebraic Attacks
• Fast Gröbner Basis Computation for Boolean Polynomials