Boolean Functions and Algebraic Normal Form (ANF)

Updated 19 Sep 2026

• •

  What it is

  • •

    ANF expresses a Boolean function as XORs of products of input bits. It makes exact identities, algebraic degree, annihilators, and linear approximations visible.

• •

  When to apply

  • •

    A filter or combiner is written with XOR, AND, and NOT, and you need to compare its outputs to algebraic or linear expressions.

• •

  Symbols and assumptions

  • •

    Inputs $x_i\in\{0,1\}$. In the Boolean ring, $x_i^2=x_i$, $1+1=0$. ANF is $f(x)=\bigoplus_{S}a_S\prod_{i\in S}x_i$ with bit coefficients $a_S$.

• •

  Math — step by step

  • •
    1. Replace XOR by addition, AND by multiplication, and NOT x by 1+x. OR requires $x+y+xy$ unless its two terms cannot both be 1.
  • •
    2. Expand products, remove pairs of identical monomials, and replace powers of a variable by that variable. The largest remaining monomial size is the algebraic degree.
  • •
    3. For a small input count, enumerate every input and evaluate the function. A six-input filter has only $2^6=64$ rows: exhaustive checking can prove an identity for all possible local input tuples.
  • •
    4. A linear approximation $\ell(x)$ is a different object from an identity. Define Walsh sum $W=\sum_x(-1)^{f(x)\oplus\ell(x)}$. Agreement count is $(2^n+W)/2$; a nonzero W means bias under uniform inputs.
• •

  Worked example

  • •

    The two-input OR function is $x+y+xy$. For (0,0), (0,1), (1,0), (1,1) it gives 0,1,1,$1+1+1=1$, as required. Plain x+y would fail on (1,1).

  • •

    For f=xy and linear approximation $\ell=0$, only input (1,1) disagrees. Thus 3/4 agree and $W=3-1=2$. The function is nonlinear even though a linear approximation predicts it with bias.

• •

  Checks and pitfalls

  • •

    LFSR Destroyer’s pasted function F has degree 5, but the actual emitted bit is z=1 XOR F. Complementing the output flips every Walsh correlation sign and changes which side of an annihilator identity applies.

  • •

    Exhaustive local truth tables prove identities and uniform-input agreement counts. They do not establish independence of temporally overlapping LFSR samples.

• •

  Related

  • •

    Finite Fields (Galois Fields: GF(p) and GF(2^n))

  • •

    Annihilator Attack on Filtered LFSRs (Quadratic Linearization)

  • •

    Correlation Attack on Filtered LFSRs (Belief Propagation)

• •

  Python

  • •

    from itertools import product
    
    def truth_table(f, n):
        return {x: f(*x) for x in product((0, 1), repeat=n)}
    
    OR = truth_table(lambda x, y: x ^ y ^ (x & y), 2)
    assert list(OR.values()) == [0, 1, 1, 1]
    

◌ Explore connections in Graph view