Young Researcher and Innovator Conference Grant

IDEM Enough? Evolving Highly Nonlinear Idempotent Boolean Functions

Claude Carlet, University of Bergen, Norway
Marko Ðurasević, University of Zagreb, Croatia
Domagoj Jakobović, University of Zagreb, Croatia
Luca Mariot, University of Twente, Enschede, Netherlands
Stjepan Picek, University of Zagreb, Croatia

Genetic and Evolutionary Computation Conference (GECCO 2026)
San José, Costa Rica
13-17 July 2026

Grantee: Luca Mariot, University of Twente, Enschede, Netherlands
Type of publication: Full paper
Type of presentation: Oral

Start date: 2026-07-13
End date: 2026-07-17
Awarded: 2026-06-08

Abstract

Idempotent Boolean functions form a highly structured subclass of Boolean functions that is closely related to rotation symmetry under a normal-basis representation and to invariance under a fixed linear map in a polynomial basis. These functions are attractive as candidates for cryptographic design, yet their additional algebraic constraints make the search for high nonlinearity substantially more difficult than in the unconstrained case. In this work, we investigate evolutionary methods for constructing highly nonlinear idempotent Boolean functions for dimensions n = 5 up to n = 12 using a polynomial basis representation with canonical primitive polynomials. Our results show that the problem of evolving idempotent functions is difficult due to the disruptive nature of crossover and mutation operators. Next, we show that idempotence can be enforced by encoding the truth table on orbits, yielding a compact genome of size equal to the number of distinct squaring orbits.