arXiv:2604.17342v1 [cs.NE] 19 Apr 2026
Monotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity Claude Carlet1,2 , Marko Čupić3 , Marko Ðurasevic3 , Domagoj Jakobovic3 , Luca Mariot4 , and Stjepan Picek3,5 1 University of Paris 8, 2 rue de la liberté, 93526 Saint-Denis Cedex, France 2 University of Bergen, Bergen, Norway [email protected] 3 Faculty of Electrical Engineering and Computing, University of Zagreb, Unska 3,
Zagreb, Croatia , [email protected], [email protected], [email protected] 4 Semantics, Cybersecurity and Services Group, University of Twente, Drienerlolaan 5,
7522 NB Enschede, The Netherlands , [email protected] 5 Digital Security Group, Radboud University, Postbus 9010, 6500 GL Nijmegen, The
Netherlands , [email protected]
April 21, 2026 Abstract Monotone Boolean functions are a structurally important class of Boolean functions, but their restricted form imposes strong limitations on achievable nonlinearity. In this paper, we investigate whether evolutionary computation can evolve monotone Boolean functions with high nonlinearity, both in the balanced and imbalanced settings. We consider three solution encodings: the standard truth table representation, a balanced truth table encoding that preserves Hamming weight, and a symbolic tree-based genetic programming representation. To guide the search toward monotone increasing functions, we introduce a non-monotonicity penalty and combine it with fitness functions targeting balancedness and nonlinearity. Experimental results are reported for dimensions from n = 5 to n = 14. The results show that evolutionary search can discover monotone Boolean functions with nonlinearities clearly exceeding those of majority functions, and in several cases approaching the best currently known values for monotone functions. At the same time, the experiments reveal substantial differences between encodings: the balanced truth table encoding performs poorly for larger dimensions, while the standard truth table and genetic programming encodings remain competitive, with genetic programming becoming especially relevant in the largest tested dimensions.
1
Keywords Boolean functions, Monotone Functions, Nonlinearity
1
Introduction
Boolean functions are mathematical objects used in diverse applications, and as such, we require Boolean functions with diverse properties and structures. One especially interesting subclass is that of monotone Boolean functions. These functions satisfy a simple and natural order constraint: switching an input bit from 0 to 1 can never force the output to decrease. Monotone Boolean functions are useful whenever adding more “positive evidence” should never make the output flip the wrong way. Monotone functions arise naturally in threshold phenomena [12], decision processes [19], system biology [20], and combinatorial models [14], and include important families such as monomials, threshold functions, and majority functions. At the same time, this structural restriction significantly limits their spectral behavior: known theoretical bounds show that monotone Boolean functions must remain much closer to affine functions than unrestricted Boolean functions, and even standard representatives such as majority functions fall well below the best-known nonlinearities in the unrestricted setting [2]. This tension between structural simplicity and spectral complexity makes monotone Boolean functions a compelling object of study. While the nonlinearity of several explicit monotone families is known, and upper bounds for the class have been established, much less is known about how close one can get to these limits in practice, especially when searching beyond classical constructions. At the same time, evolutionary and metaheuristic methods have proved highly successful in the design of Boolean functions with desirable properties, including balanced, bent, and highly nonlinear functions [7]. However, to the best of our knowledge, these methods have not yet been systematically explored for the evolution of monotone Boolean functions. In this paper, we investigate whether evolutionary computation can effectively discover monotone Boolean functions with high nonlinearity. We consider both balanced and imbalanced settings, examine several solution encodings, and design fitness functions that combine monotonicity enforcement with spectral optimization. By doing so, we aim to better understand the search landscape of monotone Boolean functions and to assess how close evolutionary approaches can come to the best-known bounds and benchmark constructions such as threshold and majority functions. Our main contributions are: 1. This is the first systematic study considering the design of monotone Boolean functions with high nonlinearity with evolutionary algorithms. 2. We consider the evolutionary design of both balanced and imbalanced monotone functions, comparing three encodings and several fitness variants. The results show that the nonlinearity of evolved monotone functions outperforms that of majority functions. 3. We identify and discuss which encodings remain effective as the number of input variables increases.
2
2
Background
We denote by F2 the finite field with two elements 0, 1, equipped with XOR (sum) and logical AND (multiplication), respectively. The n-dimensional vector space over F2 is denoted by Fn2 , consisting of all 2n binary vectors of length n. Given a, b ∈ Fn2 , their L inner product equals a · b = ni=1 ai bi in Fn2 . A Boolean function of n variables is a mapping f : Fn2 → F2 . Finally, we equip Fn2 with the usual coordinate-wise partial order: u⪯v
⇐⇒
ui ≤ vi for every i ∈ {1, . . . , n}.
2.1
Representations and Properties of Boolean Functions
2.1.1
Truth Table Representation.
(1)
A Boolean function f : Fn2 → F2 can be uniquely represented by using its truth table. The truth table (TT) of a Boolean function f is the list of pairs (x, f (x)) of input vectors x ∈ Fn2 and function outputs f (x) ∈ F2 . Once a total order has been fixed on the input vectors of Fn2 (most commonly, the lexicographic order), the truth table can be represented by the simple output vector of the function, of length 2n . 2.1.2
Walsh-Hadamard Transform.
The Walsh-Hadamard transform W f : Fn2 → Z is another unique representation of a Boolean function f . The Walsh-Hadamard transform measures the correlation between f and the linear functions a · x, for all a ∈ Fn2 : W f (a) = ∑ (−1) f (x)⊕a·x ,
(2)
x∈Fn2
with the sum calculated in Z. The Walsh-Hadamard transform is an involution up to a normalization by a constant. As such, one can retrieve the truth table representation of f from the spectrum of its Walsh-Hadamard coefficients W f (a). The Walsh-Hadamard transform allows easy characterization of several cryptographic properties, particularly balancedness and nonlinearity. 2.1.3
Balancedness
A Boolean function is balanced if it has the same number of zeros and ones in its truth table. Alternatively, it is balanced if W f (0) = 0 [2]. 2.1.4
Nonlinearity
The minimum Hamming distance between a Boolean function f and all affine functions is the nonlinearity of f , which is calculated from the Walsh-Hadamard spectrum as follows [2]: 1 (3) nl f = 2n−1 − maxn |W f (a)| . 2 a∈F2
3
Every n-variable Boolean function f satisfies the covering radius bound: n
nl f ≤ 2n−1 − 2 2 −1 .
(4)
Eq. (4) cannot be tight when n is odd (since W f (a) ∈ Z for all a ∈ Fn2 ), which means that a nonlinearity of 2n−1 − 2n/2−1 can be reached for even n only. Boolean functions in an even number of variables that achieve a nonlinearity of 2n−1 − 2n/2−1 are called bent Boolean functions. The maximal possible nonlinearity for Boolean functions in odd dimensions lies n−1 n between [2]: 2n−1 − 2 2 and 2⌊2n−2 − 2 2 −2 ⌋, where the first value is also called the quadratic bound. The highest nonlinearity for odd-sized Boolean functions is strictly larger than the quadratic bound for n > 7 [2].
2.2
Monotone Boolean functions
The function f is called monotone increasing if [2]: u ⪯ v =⇒ f (u) ≤ f (v).
(5)
Equivalently, changing any input bit from 0 to 1 cannot change the output from 1 to 0. 2.2.1
Nonlinearity of Monotone Boolean Functions.
A first general result is that for every odd n ≥ 5 and every monotone Boolean function f in n variables [5], nl f ≤ 2n−1 − 2(n−1)/2 . (6) For even dimensions, it is shown that for every even n ≥ 10 and every monotone Boolean function f [5], nl f ≤ 2n−1 − 2n/2 . (7) Thus, monotone Boolean functions are always significantly closer to affine functions than bent functions are. An even stronger bound, valid for every n, is obtained in terms of an auxiliary quantity M [1]: 1√ nl f ≤ 2n−1 − M, (8) 2 where ( min(A, B,C), if n is even, M= min(B,C), if n is odd, with
!2 j n/2 n/2 + (2n/2 − 2)2 , A = 2n + 2 ∑ 2n/2 − 2 ∑ j i i=0 1≤ j<n/4 B = minn 2n+k + 1≤k≤ 2 n+k even
n−k 2
∑ j=⌊ n+k 4 ⌋+1
n−k 2
j
4
n+k 2 2 n+k 2 −2 ∑ 2i , i=0
n+k − j 2
and
2.2.2
2 2 n−1 , if n is even, n/2 C= 2 2 n−1 , if n is odd. (n−1)/2 Threshold and Majority Functions
A central family of monotone Boolean functions is given by threshold functions [6]. For positive integers d ≤ n + 1, define ( 0, if wH (x) < d, Td,n (x) = x ∈ Fn2 . 1, if wH (x) ≥ d, Thus, Td,n outputs 1 exactly when the Hamming weight of the input is at least d. These functions are symmetric and monotone increasing. A special case of a threshold function is the majority function: ( 0, if wH (x) ≤ ⌊n/2⌋, MAJn (x) = 1, otherwise. 2.2.3
Exact Nonlinearity of Threshold Functions
The nonlinearity of threshold functions is known exactly [6]. For every n > 0 and 1 ≤ d ≤ n, n+1 n−1 , 2n−1 − (n−1)/2 , if d = 2 n n n+1 if d > , nl f (Td,n ) = ∑ k , 2 k=d d−1 n n+1 if d < . ∑ k , 2 k=0 Thus, the nonlinearity profile of threshold functions is symmetric with respect to the transformation d 7→ n − d + 1. For odd n, the majority function is the unique central threshold function, and its nonlinearity is n−1 n−1 nl f = 2 − . (n − 1)/2 For even n, the majority function is MAJn = Tn/2+1,n , and its nonlinearity equals n
n nl f = ∑ . k k=n/2+1 By symmetry, this is also equal to the nonlinearity of the adjacent threshold function Tn/2,n . We provide information about maximal known nonlinearity for balanced, imbalanced, and majority functions, as well as the upper bound for general Boolean functions 5
Table 1: Max possible and known nonlinearities. dimension
5
6
7
8
9
10
11
12
13
14
nl f (balanced)
12
26
56
116
240
492
992
2010
4036
8120
nl f (imbalanced)
12
28
56
120
242
496
996
2016
4040
8128
nl f (majority)
10
22
44
93
186
386
772
1586
3172
6476
nl f (bound)
12
28
58
120
244
496
1000
2016
4050
8128
nl f (bound monotone)
12
27
55.5
114.4
237.1
478.5
977.6
1975.1
3975.2
8013.1
and monotone functions in Table 1. Note that the bound for monotone functions results in non-integer values, while the nonlinearity values must be integers [1]. More information about Boolean functions can be found in, e.g., [15, 2].
3
Related Work
Metaheuristics are widely used in the design of Boolean functions. Common application settings include cryptography [2], combinatorics [24], and coding theory [13, 15]. For a recent overview of metaheuristic approaches for the design of Boolean functions, we refer readers to [7]. To our knowledge, no prior work has considered the evolution of monotone Boolean functions. However, many works consider evolving maximally nonlinear (bent) or balanced and highly nonlinear Boolean functions. We recall some of those works below. In 1998, Millan et al. used heuristics to design cryptographically strong balanced Boolean functions [18]. In 2003, Fuller et al. used evolutionary algorithms to evolve bent Boolean functions to 2003 [8]. In 2005, Yang et al. used evolutionary algorithms and the trace representation of Boolean functions to evolve bent Boolean functions [26]. Picek and Jakobovic used genetic programming to evolve secondary algebraic constructions that are then used to construct bent Boolean functions [21]. Hrbacek and Dvorak used Cartesian Genetic Programming to evolve bent Boolean functions [9]. Picek et al. considered the evolution of bent quaternary functions, i.e., a generalization of maximally nonlinear functions with a four-valued range [22]. Mariot et al. used evolutionary strategies to evolve a secondary construction based on cellular automata for quadratic bent functions [17]. Husa and Dobai used linear genetic programming to evolve bent Boolean functions [10]. Carlet et al. used several evolutionary algorithms and showed it is possible to evolve (anti)-self-dual bent functions for Boolean functions [3]. Yan et al. developed an improved genetic algorithm to construct weightwise (almost) perfectly balanced Boolean functions [25]. Carlet et al. provided a systematic evaluation of evolving highly nonlinear Boolean functions in odd dimensions [4].
6
4
Methodology
4.1
Solution Encodings
We consider three encodings. Truth table encoding (TT) explores the full space and is maximally expressive, but unconstrained. Balanced truth table encoding (TTw) enforces balancedness directly, but may make monotonicity much harder to satisfy simultaneously. Finally, symbolic encoding used by genetic programming (GP) may better capture structural regularities of monotone functions through symbolic compositions. 4.1.1
Truth table Encoding (TT).
The most common way to represent a Boolean function is via its truth table (TT) [7], which is encoded as a bitstring. For a Boolean function with n inputs, the truth table is a bitstring of length 2n . The search algorithm explores the full space of n-variable n Boolean functions, which has the size 22 . In this encoding, we use the simple bit mutation and the shuffle mutation. For crossover, we employ one-point and uniform crossover operators. Each time the evolutionary algorithm invokes a crossover or mutation operation, one of the previously described operators is randomly selected. 4.1.2
Balanced Truth Table Encoding (TTw).
The balanced encoding also uses a truth table to represent a Boolean function. However, the number of ones in the truth table is kept at the desired value (2n /2) at all times, so that the corresponding function is always balanced. This encoding is implemented with customized genetic operators that preserve this property, which includes initialization, mutation, and crossover. The crossover and mutation operators used in this work are based on [16], so that all genetic operators preserve the number of ones throughout the evolution. For the crossover, we use the balanced weighted crossover operator, and the mutation uses a two-bit inversion (which flips two random bits) and a mixing mutation, which shuffles the genes between two randomly chosen positions in the bitstring. 4.1.3
Symbolic Encoding (GP).
This encoding uses tree-based genetic programming (GP) to represent a Boolean function in its symbolic form. A candidate solution is represented with a tree whose leaves correspond to the input variables x1 , . . . , xn ∈ F2 . The internal nodes are Boolean operators that combine the inputs received from their children and forward their output to the respective parent nodes. We use the following function set: OR, XOR, AND, IF, and the NOT function that takes a single argument. The function IF takes three arguments and returns the second one if the first one evaluates to true, and the third one otherwise. This function set is common in previous applications and is based on our tuning results. The output of the root node is the output value of the Boolean function. The truth table of the function f : Fn2 → F2 is determined by evaluating the tree over all possible 2n assignments of the inputs at the leaves. 7
For the symbolic encoding, the genetic operators used in our experiments are simple tree crossover, uniform crossover, size fair, one-point, and context preserving crossover [23] (selected at random), and subtree mutation. Multiple genetic operators were used based on previous results indicating better convergence when using a diverse set of operators.
4.2
Fitness Functions
4.2.1
Non-monotone Penalty
In all experimental configurations, we use the non-monotone penalty to drive the search towards monotone increasing Boolean functions. One way to enforce this property is to penalize the function for every case where the monotone requirement (see Eq. (5)) is violated. This is calculated with the following: • iterate over every input u for which f (u) = 1; • for each such input u, iterate over every v obtained by taking each input bit equal to 0 and changing it to 1; • increase penalty value penalty by 1 for every case in which f (v) = 0. If the penalty is zero, meaning the function is monotone, then we add the desired property to optimize in the fitness function. 4.2.2
Fitness for Balanced Functions
In the first scenario, we search for balanced, highly nonlinear monotone functions. All fitness functions include a non-monotone penalty term, penalty, that counts the occurrences that do not satisfy the monotone property. This term is added with a negative sign to act as a penalty in maximization. The delta function δ penalty,0 assumes the value one when penalty = 0 and is zero otherwise. Furthermore, to obtain only balanced monotone functions, we include the balancedness penalty BAL, which is defined as the difference up to the balancedness (i.e., the number of bits to be changed to make the function balanced). This difference is also subtracted to facilitate maximization. The delta function δBAL,0 assumes the value one when BAL = 0 and is zero otherwise. Only if the function is monotone and balanced, i.e., if both BAL and penalty equal zero, the nonlinearity value (nl f ) is added, and the fitness is maximized. However, rather than considering only the extreme values of the Walsh–Hadamard spectrum, we also observe the number of times the maximum absolute value occurs in the spectrum, denoted by #max_vals. Since higher nonlinearity corresponds to a lower maximal absolute value, we aim for as few occurrences of the maximal value as possible to reach the next nonlinearity value; therefore, we include the inverse percentage of these values as a non-integer part added to the nonlinearity value. Finally, the composite fitness function is defined as: 2n − #max_vals f itnessBAL = −penalty − BAL + δ penalty,0 · δBAL,0 · nl f + . (9) 2n 8
4.2.3
Fitness for Imbalanced Functions
For the imbalanced monotone functions scenario, we can simply omit the balancedness penalty, thus arriving at the following fitness function: 2n − #max_vals . (10) f itnessIMB = −penalty + δ penalty,0 · nl f + 2n However, when calculating the non-monotone penalty, it can be observed that Boolean functions with a lower Hamming weight will, on average, receive a lower penalty: since we count only cases where f (u) changes from 1 to 0, functions having fewer ones in the truth table will have a lower maximum possible penalty. This is evident from Figure 1a, where we sample random Boolean functions (of 6 variables) with different weights and record the obtained penalties; it is obvious that this penalty will favor functions with a lower Hamming weight. To achieve a more uniform penalty pressure over all weight values, we experiment with two additional variants; penalty2 takes the original count penalty and divides it with the number of total possible occurences of non-monotone violations, which is equal to the number of all truth table entries u where f (u) = 1 and all possible bit changes from 0 to 1 in input u. Finally, penalty3 is divided by the square of the maximum possible penalty, since it was observed that penalty2 introduces an inverted weight bias (Figure 1). Therefore, the experiments for imbalanced monotone functions include three fitness functions, denoted f it1 , f it2 , and f it3 , which simply correspond to the penalty variant used in Eq. (10). Note that different penalty measures incur different scales, but this is irrelevant in cases where selection is not proportional. The three penalty variants are motivated by the dependence of monotonicity violations on the Hamming weight of the candidate function. The raw penalty in fit1 counts all local violations directly and therefore favors functions with fewer ones in their truth table, since such functions have fewer opportunities to violate monotonicity. To reduce this bias, fit2 normalizes the count by the maximum possible number of violations for the given support size. As shown in Figure 1b, this correction is too strong and introduces the opposite bias, favoring functions with larger Hamming weight. We then introduce fit3, which uses a milder normalization by the square of the maximum possible penalty. This yields a more uniform penalty landscape across Hamming weights and acts as a compromise between the two extremes.
4.3
Algorithms and Parameters
We use the same evolutionary algorithm for all encodings: a steady-state selection with a 3-tournament elimination operator. In each iteration, three individuals from the population are chosen at random, and the worst one in terms of fitness value is eliminated. The two remaining individuals are used with the crossover operator to generate a child individual, which then undergoes mutation with individual mutation probability pmut = 0.5. The mutated child replaces the eliminated individual in the population. All algorithms use the same stopping criterion of 106 evaluations, and all experiments are executed in 30 runs. The implementation was made using the ECF
9
(a) Penalty for f itness1 : count non-monotone (b) Penalty for f itness2 : normalized by maxioccurences mum penalty
(c) Penalty for f itness3 : normalized by square of max. penalty
Figure 1: Non-monotone penalty variants. framework1 [11] and the code is available upon request.
5
Experimental Results
In the experiments, we carry out experiments in two scenarios: optimization of balanced functions, with a single fitness function, and imbalanced Boolean functions with three fitness variants. Experiments are made using three encodings (TT, TTw, and GP) and problem sizes from 5 to 14 variables. As a concise overview, Table 2 shows only the best obtained nonlinearity values for every combination of size, encoding, and fitness function. The dash as the table entry denotes a configuration in which not a single monotone function was found in 30 runs. From the values in the table, we can see that the evolutionary approach is effective at discovering monotone functions with nonlinearity substantially above the majority baseline. Indeed, for every tested size, we find monotone functions with higher nonlinearity than that of majority functions. This comparison is important because the majority functions are the most classical monotone benchmark, yet they substantially 1 http://ecf.zemris.fer.hr/
10
Table 2: Best obtained results (nonlinearity) for all considered sizes.
5
6
7
8
9
13
14
bal: TT
10 22 46 94 192 388 786 1583 2835
-
bal: TTw
10 22 44 70
6
bal: GP
10 22 44 84 176 336 704 1281 2721 5441
34
10
22
11
18
12
14
12
imb: TT, fit1 11 23 47 96 195 396 797 1612 3173
-
imb: TT, fit2 11 23 47 96 195 396 800 1596 1156
498
imb: TT, fit3 11 23 47 97 195 397 799 1610 2462
-
imb: GP, fit1 11 23 46 97 196 396 802 1581 3072 6651 imb: GP, fit2 11 23 46 95 196 398 796 1619 3401 6750 imb: GP, fit3 11 23 46 96 198 395 767 1642 3293 6659
underestimate the nonlinear behavior achievable within the monotone class. In this sense, evolutionary search does not merely rediscover known constructions, but explores regions of the monotone-function space that are not captured by standard thresholdbased examples. Naturally, the obtained values still remain below the known upper bound for monotone functions (except for n = 5), but the extent to which explicit monotone constructions can approach that bound remains open. At the same time, the remaining gap to the best known upper bound for monotone functions should be interpreted with caution: it may reflect limitations of the search process, but it may also indicate that the current upper bound is not tight for explicit constructions in the tested dimensions. For sizes n = 5, 6, all approaches work equally well, showcasing that the problem is still easy. The results for individual problem sizes are presented in Figures 2 to 7. The results for the balanced scenario show that the balanced encoding (TTw) with enforced weight performs worse than TT for n ≤ 7, and worse overall for all larger n. This can also be observed in Table 2, since even the best TTw results are much smaller than the ones from other encodings. For that reason, we omit the TTw values in figures depicting balanced results for a larger number of variables. The balanced scenario is visibly harder than the imbalanced one, which is natural because the search must simultaneously satisfy two strong constraints: monotonicity and exact balance. This helps explain both the rapid deterioration of the TTw encoding and the fact that, in larger dimensions, even the unrestricted TT representation struggles to locate feasible balanced monotone solutions. As for the symbolic encoding (GP) compared to TT, we can see that it is generally worse than TT, but it starts to perform competitively for sizes 13 and 14. Indeed, already for n = 13, the balanced TT cannot find a balanced monotone function in most of the runs (which end with a negative fitness value); only in a single run (out of 30), the best nonlinearity value of 2835 is found with TT, most likely by pure chance. For this reason,
11
+ ●
+
● ●
80
95 ●
+
60
40
● ● ●
+
fitness value
fitness value
●
+
+
● ●
●
●
+
+
90
● ●
●
+ ●
85
20
TT
TTw
GP
●
TT_fit1
TT_fit2
n = 8, balanced
TT_fit3
GP_fit1
GP_fit2
GP_fit3
+
+
+
GP_fit1
GP_fit2
GP_fit3 ●
n = 8, imbalanced
Figure 2: Results for n = 8
200
+
200
● ●
●
●
195
+ 100
fitness value
fitness value
150
+
+
+
190
185
180
50 ● ● ●
+ ●
TT
TTw
175 GP
TT_fit1
TT_fit2
n = 9, balanced
TT_fit3
n = 9, imbalanced ●
Figure 3: Results for n = 9 ●
the plot for the balanced case in 13 variables is not shown (since the majority of TT results are negative). Furthermore, in n = 14 variables, the TT encoding does not succeed in finding a single monotone Boolean function, whether balanced or not; therefore, the plot for this case (Figure 7) shows only GP results. This difference between TT and GP suggests that representation bias becomes increasingly important as the dimension grows: while TT is highly expressive, GP appears better able to exploit structural regularities of monotone functions once the feasible region becomes too sparse to be reached reliably by direct truth table search. Throughout the experiments, fitness functions fit2 and fit3 offer a slight advantage over fit1 in the imbalanced setting; however, this effect is visible mainly for the TT encoding and mostly for sizes below n = 13. This suggests that correcting the Hamming weight bias in the penalty is useful when the search is performed directly in truth table space, where local changes strongly affect support size. In contrast, for GP, the structural bias induced by the representation appears to dominate the influence of the penalty normalization, so the three fitness variants behave much more similarly.
12
380
400
+ ● ● ● ●
● ●
390
340
●
●
320 300
fitness value
fitness value
360
+
+ ● ●
●
+
380
+
+ +
370
●
360
280
+
260
●
TT
350
GP
TT_fit1
TT_fit2
TT_fit3
GP_fit1
GP_fit2
GP_fit3
●
n = 10, balanced
n = 10, imbalanced
Figure 4: Results for n = 10 ●
800
+ 750
+
●
700
fitness value
fitness value
780
650
+
+ ●
●
+
760
+
+
740
600 720
+
550
700 TT
GP
TT_fit1
TT_fit2
n = 11, balanced
TT_fit3
GP_fit1
GP_fit2
GP_fit3 ●
n = 11, imbalanced
Figure 5: Results for n = 11 ●
1600
1650
+
+
+
●
fitness value
1550
1400
fitness value
●
●
1600
1500
+
1500
1300
●
●
+
+
+
GP_fit1
GP_fit2
GP_fit3
1450
1200 ●
1100
+ TT
1400 1350
GP
TT_fit1
TT_fit2
n = 12, balanced
TT_fit3
n = 12, imbalanced
Figure 6: Results for n = 12
13
3500
7000
● ●
+
3000
+
+
● ●
+
● ●
●
6500
● ●
fitness value
2000
●
●
fitness value
●
2500
6000
+
1500
+
+
5500
+
● ●
1000
+ ●
500
5000 TT_fit1
TT_fit2
TT_fit3
GP_fit1
GP_fit2
GP_fit3
GP_fit1
● ●
n = ●13, imbalanced
GP_fit2
GP_fit3
n = 14, imbalanced
Figure 7: Results for n = 13 and n = 14, imbalanced functions
6
Conclusions and Future Work
In this work, we studied the problem of evolving monotone Boolean functions with high nonlinearity. Unlike the classical setting of unrestricted Boolean-function design, monotone Boolean functions are subject to strong structural constraints, which significantly limit the achievable nonlinearity. This makes them an interesting and challenging target for evolutionary search. To address this problem, we considered three solution encodings: the standard truth table encoding, a balanced truth table encoding with dedicated variation operators, and a symbolic genetic programming representation. We also proposed fitness functions that combine nonlinearity optimization with explicit pressure toward monotonicity, and, in the balanced scenario, with an additional balancedness constraint. For imbalanced monotone functions, we investigated three variants of the monotonicity penalty in order to reduce the bias induced by Hamming weight. The experimental study for dimensions n = 5, . . . , 14 shows that evolutionary algorithms can successfully discover monotone Boolean functions with high nonlinearity in both the balanced and imbalanced settings. In particular, the evolved functions consistently outperform majority functions in terms of nonlinearity, confirming that majority functions are not representative of the best nonlinear behavior achievable inside the monotone class. Overall, the results demonstrate that evolutionary search is a viable method for exploring the space of monotone Boolean functions with high nonlinearity. More specifically, TT tends to provide the strongest results in small and medium dimensions, whereas GP becomes more robust in the largest tested sizes, especially when TT fails to find feasible monotone solutions. This further indicates that the choice of representation and fitness design has a decisive impact on performance. As future work, it would be natural to extend the search to larger dimensions, investigate additional representations and variation operators tailored to monotonicity, and analyze the structure of the best evolved functions in order to derive constructive principles for monotone Boolean functions with improved cryptographic properties.
14
References [1] C. Carlet. On the nonlinearity of monotone boolean functions. Cryptography and Communications, 10(6):1051–1061, Oct. 2017. [2] C. Carlet. Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge, 2021. [3] C. Carlet, M. Durasevic, D. Jakobovic, L. Mariot, and S. Picek. Look into the Mirror: Evolving Self-dual Bent Boolean Functions, page 161–175. Springer Nature Switzerland, 2024. [4] C. Carlet, M. Durasevic, D. Jakobovic, S. Picek, and L. Mariot. A systematic study on the design of odd-sized highly nonlinear boolean functions via evolutionary algorithms. Genetic Programming and Evolvable Machines, 27(1), Dec. 2025. [5] C. Carlet, D. Joyner, P. Stănică, and D. Tang. Cryptographic properties of monotone Boolean functions. Journal of Mathematical Cryptology, 10(1):1–14, 2016. [6] C. Carlet and P. Méaux. A complete study of two classes of boolean functions: Direct sums of monomials and threshold functions. IEEE Transactions on Information Theory, 68(5):3404–3425, 2022. [7] M. Djurasevic, D. Jakobovic, L. Mariot, and S. Picek. A survey of metaheuristic algorithms for the design of cryptographic Boolean functions. Cryptography and Communications, 15(6):1171–1197, July 2023. [8] J. Fuller, E. Dawson, and W. Millan. Evolutionary generation of bent functions for cryptography. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2003, Canberra, Australia, December 8-12, 2003, pages 1655–1661. IEEE, 2003. [9] R. Hrbacek and V. Dvorak. Bent function synthesis by means of cartesian genetic programming. In T. Bartz-Beielstein, J. Branke, B. Filipič, and J. Smith, editors, Parallel Problem Solving from Nature – PPSN XIII, pages 414–423, Cham, 2014. Springer International Publishing. [10] J. Husa and R. Dobai. Designing bent Boolean functions with parallelized linear genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17, page 1825–1832, New York, NY, USA, 2017. Association for Computing Machinery. [11] D. Jakobovic, M. Ðurasević, S. Picek, and B. Gašperov. Ecf: A c++ framework for evolutionary computation. SoftwareX, 27:101640, 2024. [12] G. Kalai. Threshold phenomena and influences. Computational Complexity and Statistical Physics, pages 25–60, 2006. Lecture notes / survey. [13] A. Kerdock. A class of low-rate nonlinear binary codes. Information and Control, 20(2):182 – 187, 1972. 15
[14] A. D. Korshunov. Monotone boolean functions. Russian Mathematical Surveys, 58(5):929–1001, 2003. [15] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. Elsevier, Amsterdam, North Holland, 1977. ISBN: 978-0-444-85193-2. [16] L. Manzoni, L. Mariot, and E. Tuba. Balanced crossover operators in genetic algorithms. Swarm Evol. Comput., 54:100646, 2020. [17] L. Mariot, M. Saletta, A. Leporati, and L. Manzoni. Heuristic search of (semi-)bent functions based on cellular automata. Nat. Comput., 21(3):377–391, 2022. [18] W. Millan, A. Clark, and E. Dawson. Heuristic design of cryptographically strong balanced Boolean functions. In K. Nyberg, editor, Advances in Cryptology — EUROCRYPT’98, pages 489–499, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. [19] R. O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. [20] L. Paulevé and S. Sené. Boolean networks and their dynamics: the impact of updates. International Journal of Molecular Sciences, 23(15):8671, 2022. [21] S. Picek and D. Jakobovic. Evolving algebraic constructions for designing bent Boolean functions. In Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO ’16, page 781–788, New York, NY, USA, 2016. Association for Computing Machinery. [22] S. Picek, K. Knezevic, L. Mariot, D. Jakobovic, and A. Leporati. Evolving bent quaternary functions. In 2018 IEEE Congress on Evolutionary Computation, CEC 2018, Rio de Janeiro, Brazil, July 8-13, 2018, pages 1–8. IEEE, 2018. [23] R. Poli, W. B. Langdon, and N. F. McPhee. A Field Guide to Genetic Programming. lulu.com, 2008. [24] O. Rothaus. On “bent” functions. Journal of Combinatorial Theory, Series A, 20(3):300 – 305, 1976. [25] L. Yan, J. Cui, J. Liu, G. Xu, L. Han, A. Jolfaei, and X. Zheng. Iga: An improved genetic algorithm to construct weightwise (almost) perfectly balanced boolean functions with high weightwise nonlinearity. In Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, ASIA CCS ’23, page 638–648, New York, NY, USA, 2023. Association for Computing Machinery. [26] M. Yang, Q. Meng, and H. Zhang. Evolutionary design of trace form bent functions. Cryptology ePrint Archive, Paper 2005/322, 2005. https://eprint.iacr.org/ 2005/322.
16