Algebraic normal form
Algebraic normal form (ANF) is a canonical polynomial representation of any Boolean function on n variables as a multivariate polynomial over the finite field \mathbb{F}_2 (the field with two elements, where addition is XOR and multiplication is AND), in which each variable appears with degree at most 1 and the polynomial is unique for each function.[1] This form expresses the function f: \mathbb{F}_2^n \to \mathbb{F}_2 as f(x_1, \dots, x_n) = \sum_{u \in \mathbb{F}_2^n} a_u \prod_{i: u_i=1} x_i, where coefficients a_u \in \mathbb{F}_2 are determined by a_u = \bigoplus_{x \preceq u} f(x) via the Möbius inversion over the Boolean lattice, with \preceq denoting componentwise inequality and \bigoplus denoting summation modulo 2.[1] The ANF can be computed from the truth table of the function in O(n 2^n) time using fast Möbius transforms, making it efficient for small n.[1] Introduced by the Soviet mathematician Ivan Zhegalkin in 1927 as a way to represent Boolean operations via ordinary polynomials modulo 2, the ANF—often called the Zhegalkin polynomial in Russian mathematical literature—provides a bridge between Boolean algebra and polynomial algebra over \mathbb{F}_2.[2] A key property is that the algebraic degree of the Boolean function, defined as the maximum number of variables in any monomial with nonzero coefficient a_u \neq 0 (i.e., the maximum Hamming weight of such u), directly influences the function's complexity and cryptographic strength; for instance, the constant zero function has degree -1 by convention.[3] The representation is affine-invariant, meaning it remains structurally similar under affine transformations of the input variables, which aids in classifying functions up to equivalence.[4] In applications, the ANF is fundamental in cryptography for analyzing stream ciphers, block ciphers, and S-boxes, as it facilitates algebraic attacks that exploit low-degree equations to recover keys; higher-degree ANFs enhance resistance to such attacks.[1] It also appears in coding theory, particularly in Reed-Muller codes where codewords correspond to evaluations of low-degree ANF polynomials, and in circuit complexity studies to measure multiplicative complexity via the number of AND gates needed.[4] For example, the ANF of the Boolean function with truth table [0,1,1,0,1,0,1,1] on three variables is x_0 x_1 x_2 + x_0 + x_1 x_2 + x_1 + x_2, illustrating how disjunctive normal forms can be converted to this multilinear polynomial modulo 2.[3]Fundamentals
Definition
The algebraic normal form (ANF) of a Boolean function is a canonical polynomial representation over the finite field GF(2), expressed as a sum of product terms where each variable appears at most once (degree at most 1 per variable) and coefficients are elements of {0,1}, with arithmetic performed modulo 2—addition as exclusive-or (XOR) and multiplication as logical AND.[1][2] This form leverages the structure of Boolean algebra interpreted in GF(2), where the ring of polynomials is quotiented by the ideal generated by x_i^2 + x_i for each variable x_i, enforcing idempotence (x_i^2 = x_i) and ensuring no higher-degree terms arise.[1] Formally, for a Boolean function f: \{0,1\}^n \to \{0,1\}, its ANF is given by f(x_1, \dots, x_n) = \sum_{S \subseteq } a_S \prod_{i \in S} x_i, where = \{1, \dots, n\}, each a_S \in \mathrm{GF}(2), the sum is modulo 2 (i.e., XOR over all terms with a_S = 1), and the product is over distinct variables.[1][2] The coefficients a_S are uniquely determined by the function f, making the ANF a unique representation for any Boolean function.[1] In this modulo 2 semantics, Boolean absorption laws hold in a compatible way, which simplifies polynomial reductions.[1] For example, the function f(x) = x \oplus 1 has ANF x + 1 (modulo 2), where the constant term 1 corresponds to the flipped output at x=0.[2] This contrasts briefly with disjunctive normal form, which uses OR instead of XOR for summation.[1]Basic Properties
The algebraic normal form (ANF) of a Boolean function provides a unique polynomial representation over the field \mathbb{F}_2. Specifically, every Boolean function f: \mathbb{F}_2^n \to \mathbb{F}_2 can be expressed uniquely as f(\mathbf{x}) = \sum_{I \subseteq \{1, \dots, n\}} a_I \prod_{i \in I} x_i, where the coefficients a_I \in \mathbb{F}_2 are determined by the Möbius inversion formula applied to the truth table of f, ensuring a one-to-one correspondence between functions and their ANF polynomials.[5] The degree of a Boolean function f, denoted \deg(f), is defined as the maximum size of the support of any monomial with nonzero coefficient in its ANF, i.e., \deg(f) = \max \{ |I| : a_I = [1](/page/1) \}. This degree captures the nonlinearity of f; for instance, linear functions such as f(x_1, x_2) = x_1 + x_2 have degree 1, while quadratic functions like f(x_1, x_2) = x_1 x_2 + x_1 have degree 2, influencing properties such as resilience to linear approximations in cryptographic contexts.[5] The ANF representation is algebraically closed under the operations of XOR (addition in \mathbb{F}_2) and AND (multiplication in \mathbb{F}_2). The ANF of the XOR of two functions f \oplus g is the component-wise sum of their ANF coefficients modulo 2, while the ANF of f \cdot g is the convolution of their coefficient vectors, preserving the multilinear structure without higher powers. This closure enables polynomial-time computation of the ANF for compositions involving these operations, facilitating efficient analysis in applications like circuit synthesis and cryptographic evaluations.[5] The support of a Boolean function f in its ANF is the set of variables \{ i : \exists I \ni i \text{ with } a_I = 1 \}, representing the variables that appear in at least one nonzero monomial and determining the effective dimensionality of f. Algebraic immunity measures the resistance of f to algebraic attacks and is defined as the smallest degree d such that there exists a nonzero annihilator g of degree at most d satisfying either f \cdot g = 0 or (f + 1) \cdot g = 0 (where all operations are in \mathbb{F}_2). High algebraic immunity, ideally \lceil n/2 \rceil, ensures no low-degree polynomial annihilates f or its complement, enhancing security against attacks that exploit such relations in the ANF.[5][6]Representation
Univariate Case
In the univariate case, where a Boolean function f: \mathbb{F}_2 \to \mathbb{F}_2 depends on a single variable x, the algebraic normal form (ANF) simplifies to an affine polynomial of the form f(x) = a_0 \oplus a_1 x, with coefficients a_0, a_1 \in \mathbb{F}_2.[5] This representation captures all possible univariate Boolean functions, of which there are exactly four, each corresponding to a unique truth table with two entries: f(0) and f(1).[5] Basic univariate functions have straightforward ANFs. The constant function f(x) = 0 is represented by the empty sum (or simply 0).[5] The constant function f(x) = 1 is represented by 1.[5] The identity function f(x) = x is represented by x.[5] The negation function \neg x (or f(x) = 1 \oplus x) is represented by $1 \oplus x.[5] The coefficients in the univariate ANF can be computed using the Möbius inversion formula over \mathbb{F}_2, where the coefficient a_k for the monomial x^k (with k \leq 1) is given by a_k = \bigoplus_{j=0}^k (-1)^{k-j} f(j).[5] Since operations are in \mathbb{F}_2, where -1 = 1, this simplifies to direct mappings: a_0 = f(0) and a_1 = f(0) \oplus f(1).[5] The following table visualizes the mapping from truth tables to ANFs for all four possible univariate Boolean functions:| Truth Table [f(0), f(1)] | ANF Representation | Description | Degree |
|---|---|---|---|
| [0, 0] | $0 | Constant 0 | -1 |
| [1, 1] | $1 | Constant 1 | 0 |
| [0, 1] | x | Identity | 1 |
| [1, 0] | $1 \oplus x | Negation | 1 |
Multivariate Case
In the multivariate case, the algebraic normal form (ANF) of a Boolean function f: \mathbb{F}_2^n \to \mathbb{F}_2 extends the univariate representation by expressing f as a unique polynomial over \mathbb{F}_2 in n variables, where each term is a monomial corresponding to a product of distinct variables. Specifically, f(x_1, \dots, x_n) = \sum_{u \in \mathbb{F}_2^n} a_u \prod_{i=1}^n x_i^{u_i}, with coefficients a_u \in \mathbb{F}_2, and since x_i^2 = x_i in \mathbb{F}_2[x_i]/(x_i^2 - x_i), higher powers reduce, making each monomial a square-free product over a support subset S \subseteq \{1, \dots, n\}, such as x_1 x_2 x_4 for S = \{1,2,4\}. This representation captures interactions among variables through the supports of non-zero monomials, with the algebraic degree defined as the maximum size of such supports.[7][1] The ANF can be derived recursively by fixing one variable and differencing. For a function f(x_1, \dots, x_n), it decomposes as f(x_1, \dots, x_n) = f(0, x_2, \dots, x_n) \oplus x_1 \cdot (f(1, x_2, \dots, x_n) \oplus f(0, x_2, \dots, x_n)), where the first term is the ANF over n-1 variables with x_1 = 0, and the second is x_1 times the ANF of the first-order difference operator \Delta_{x_1} f = f(1, x_2, \dots, x_n) \oplus f(0, x_2, \dots, x_n), which has degree at most one less than that of f. Higher-order terms arise from iterated differencing over subsets, with coefficients a_u = \bigoplus_{v \leq u} f(v), where \leq denotes componentwise inequality in \mathbb{F}_2^n. This recursive structure builds the full multivariate polynomial from lower-dimensional slices.[7][1] For symmetric Boolean functions, which depend only on the Hamming weight of the input, the ANF takes a particularly structured form as a sum of elementary symmetric polynomials. A representative example is the majority function on 3 variables, \mathrm{maj}(x_1, x_2, x_3), which outputs 1 if at least two inputs are 1; its ANF is x_1 x_2 \oplus x_1 x_3 \oplus x_2 x_3. This quadratic form highlights the pairwise interactions without higher-degree terms, and evaluating it confirms the function values: 0 for inputs with fewer than two 1s, and 1 otherwise (noting that the three quadratic terms sum to 1 modulo 2 when all inputs are 1). Such examples illustrate how ANF concisely encodes symmetric dependencies in multivariate settings.[7] The structure of the ANF reveals variable influences and dependencies through the supports of monomials with non-zero coefficients: a variable x_i influences f if it appears in at least one such monomial, while the size and overlap of supports indicate the strength and nature of interactions (e.g., linear terms for individual influences, quadratic for pairwise). Non-zero a_u \neq 0 for | \mathrm{supp}(u) | = k signifies a degree-k dependency among those variables, aiding analysis of function complexity and resilience in applications like cryptography.[7][1]Conversion Methods
From Truth Tables
The truth table of a Boolean function f: \{0,1\}^n \to \{0,1\} consists of $2^n rows, each corresponding to an input vector \mathbf{x} \in \{0,1\}^n (typically ordered lexicographically), with entries giving the output values f(\mathbf{x}). This tabular representation serves as the starting point for deriving the algebraic normal form (ANF), where the goal is to compute the coefficients a_S \in \{0,1\} for each monomial \prod_{i \in S} x_i with S \subseteq .[5] The forward differencing algorithm computes these coefficients via the Möbius inversion formula on the Boolean lattice:a_S = \bigoplus_{T \subseteq S} f(T),
where T is interpreted as the input vector with 1s exactly in the positions indexed by T, and \bigoplus denotes summation modulo 2 (XOR over the relevant entries). This equates to the parity of the number of subsets T \subseteq S where f(T) = 1. The naive implementation iterates over all $2^n subsets S and, for each, XORs the $2^{|S|} values f(T) for T \subseteq S, yielding a time complexity of O(3^n) operations, since the total subset pairs sum to $3^n.[5][8] A more efficient approach is the fast Möbius transform, which computes all coefficients in O(n \cdot 2^n) time through iterative in-place XOR operations across variable dimensions, exploiting the hypercube structure. This method is analogous to the fast Fourier transform and is practical for n up to 20–30 on standard hardware, as the exponential $2^n factor limits scalability for larger n, though the linear n prefactor provides significant speedup over naive methods for moderate sizes. The algorithm proceeds as follows in pseudocode (assuming 0-based indexing and the truth table stored in array
A of size $2^n, with index k representing the binary vector for input k):
After execution,function fast_mobius_transform(A, n): for i in 0 to n-1: // for each [variable](/page/Variable) dimension step = 1 << (i + 1) // 2^{i+1} half = 1 << i // 2^i for j in 0 to (1<<n)-1 step step: for k in 0 to half-1: idx_low = j + k idx_high = j + k + half A[idx_high] = A[idx_low] XOR A[idx_high] return A // Now A[k] = a_S where [binary](/page/Binary)(k) corresponds to Sfunction fast_mobius_transform(A, n): for i in 0 to n-1: // for each [variable](/page/Variable) dimension step = 1 << (i + 1) // 2^{i+1} half = 1 << i // 2^i for j in 0 to (1<<n)-1 step step: for k in 0 to half-1: idx_low = j + k idx_high = j + k + half A[idx_high] = A[idx_low] XOR A[idx_high] return A // Now A[k] = a_S where [binary](/page/Binary)(k) corresponds to S
A[k] holds a_S for the subset S whose characteristic vector is the binary representation of k. This transform is an involution over GF(2), meaning applying it twice recovers the original truth table.[5][8]
To illustrate for n=2, consider the AND function f(x_1, x_2) = x_1 \land x_2, with truth table rows for inputs (x_1, x_2):\begin{array}{c|c} (x_1, x_2) & f \\ \hline (0,0) & 0 \\ (0,1) & 0 \\ (1,0) & 0 \\ (1,1) & 1 \\ \end{array}
or compactly as [[0,0], [0,1]] (grouped by x_1). Initialize
A = [0, 0, 0, 1] (indices 0: (0,0), 1: (0,1), 2: (1,0), 3: (1,1)).
For i=0 (first variable, half=1, step=2):
- j=0: XOR A[9] ^= A → 0 ^= 0 = 0
- j=2: XOR A[10] ^= A[11] → 1 ^= 0 = 1
NowA = [0, 0, 0, 1].
- j=0: XOR A[11] ^= A → 0 ^= 0 = 0; A[10] ^= A[9] → 1 ^= 0 = 1
NowA = [0, 0, 0, 1]. The coefficients are a_\emptyset = 0, a_{\{2\}} = 0, a_{\{1\}} = 0, a_{\{1,2\}} = 1, yielding ANF f(x_1, x_2) = x_1 x_2. This matches the monomial structure where only the full-support term is present.[5]
From Disjunctive Normal Form
To convert a Boolean function given in disjunctive normal form (DNF) to algebraic normal form (ANF), the expression is interpreted over the field GF(2), where logical OR corresponds to addition modulo 2 (XOR) and logical AND corresponds to multiplication. Each term in the DNF, which is a conjunction of literals, is expanded into a polynomial by replacing negated variables \neg x_i with $1 + x_i (since \neg x_i \equiv 1 \oplus x_i in GF(2)) and positive variables x_i remain as is. The product is then distributed to yield a sum of monomials, and the entire DNF is the modulo 2 sum of these expanded terms across all clauses. Like terms are collected, and coefficients that appear an even number of times cancel out (equivalent to 0 modulo 2), resulting in the unique ANF representation.[1][12] This process handles shared factors naturally through the modulo 2 arithmetic, as overlapping monomials from different clauses XOR their coefficients. For instance, consider the parity function on two variables, whose DNF is x_1 \land \neg x_2 \lor \neg x_1 \land x_2. Substituting negations gives (x_1 (1 + x_2)) + ((1 + x_1) x_2) = x_1 + x_1 x_2 + x_2 + x_1 x_2, where the x_1 x_2 terms cancel modulo 2, yielding the ANF x_1 + x_2. This demonstrates how XOR summation in ANF resolves redundancies from shared variables in the DNF.[13][1] The algorithm proceeds as follows: (1) Parse the DNF into its clauses, each a product of literals; (2) for each clause, replace \neg x_i with $1 + x_i and expand the resulting multilinear expression into monomials using distributivity; (3) sum all expanded monomials from all clauses modulo 2, tracking coefficients in a dictionary or array indexed by monomial supports; (4) retain only monomials with odd coefficients (1 modulo 2) in the final ANF. This direct expansion avoids truth table enumeration and leverages the structure of the input DNF.[1] In the worst case, the conversion has exponential time and space complexity in the number of variables, as each clause with k negated literals expands to $2^k monomials, potentially leading to up to $2^n terms before reduction. However, if the DNF is sparse (few clauses) or has low negation density, the process is polynomial in the input size, making it efficient for practical cryptographic functions with structured DNF representations.[1][13]Operations
Algebraic Operations
Algebraic operations on algebraic normal forms (ANFs) of Boolean functions are performed in the ring of functions from \{0,1\}^n to GF(2, where addition corresponds to pointwise XOR and multiplication to pointwise AND. These operations preserve the ANF representation through manipulations of the coefficients and monomials.[12] Addition of two ANFs f(x) = \sum_{S \subseteq } c_S \prod_{i \in S} x_i and g(x) = \sum_{S \subseteq } d_S \prod_{i \in S} x_i is computed by XORing the coefficients for each monomial: the coefficient of \prod_{i \in S} x_i in f + g is c_S + d_S \pmod{2}. This operation is efficient, requiring a single pass over the monomials present in either representation. For instance, if f = x_1 + x_2 and g = x_1, then f + g = x_2.[12] Multiplication of ANFs is more involved, as it requires accounting for the ring structure where x_i^2 = x_i. The product f \cdot g has ANF given by summing over all pairs of monomials: (f \cdot g)(x) = \sum_{S, T \subseteq } c_S d_T \prod_{i \in S \cup T} x_i, with coefficients XORed modulo 2 for each resulting monomial after collecting like terms. The support of the product monomial is the union of the supports of the input monomials, reflecting the idempotence x_i \cdot x_i = x_i. The algebraic degree satisfies \deg(f \cdot g) \leq \deg(f) + \deg(g).[12] As an example, consider the linear ANFs f = x_1 + x_2 and g = x_1. The pairs yield:- x_1 \cdot x_1 = x_1 (union \{1\} \cup \{1\} = \{1\}),
- x_2 \cdot x_1 = x_1 x_2 (union \{2\} \cup \{1\} = \{1,2\}).