Generate ANF from SBox

There is a simple way based on repeated linear interpolation, known as the Shannon-expansion.

With this you can extract the ANF expression from any black-box map function (for example, an S-Box) using on the order of $2^n$ evaluations for an $n$-bit Boolean function. It's slow but remarkably simple. I will demonstrate using $2$-bit function.

$$f(x_0,x_1)$$

can be expanded in the first bit

$$small{f(x_0,x_1) = f(0,x_1)(1-x_0) ; + ; f(1,x_1){x_0}}$$

and then again in the second bit

$$small{f(x_0,x_1) = f(0,0)(1-x_0)(1-x_1) ; + ; f(0,1)(1-x_0)x_1 ; + ; f(1,0){x_0}(1-x_1) ; + ; f(1,1){x_0}{x_1}}$$

Repeating this with larger functions, the pattern becomes clear. The $k$th term in this expression simply multiplies $small{f(x)}$ with either a $x_i$ or $small(1-x_i)$, depending on the setting of the bit in the input to the map function.

So for a larger Boolean function, the first term would be

$$small{f(0,0,0,0,ldots,0)(1-x_0)(1-x_1)(1-x_2)(1-x_3)ldots(1-x_n)}$$

and the final term would be

$$small{f(1,1,1,1,ldots,1)x_0 x_1 x_2 x_3ldots x_n}$$

The ANF can then be derived from this expression by multiplying out the parenthesis. This is laborious by hand, but a small amount of code in a computer program.

Here is the idea implemented in C++

#include <iostream>
#include <vector>

/* black-box map function to extract ANF */
int map(int x) {
  int sbox[] = {6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11};
  return sbox[x % 16];
}

int num_input_bits = 4; /* number of map input bits to consider */
int num_output_bits = 4; /* number of map output bits to consider */

/* (1-x_0)(1-x1)x_2 = x_2*(1 + x_0 + x_1 + x_0*x_1) */

int main() {
  /* step 1) calculate ANF of the map function */
  int num_input_states = 1 << num_input_bits;
  for (int i = 0; i < num_output_bits; ++i) {
    std::vector<int> anf(num_input_states); /* accumulate ANF here */
    for (int j = 0; j < num_input_states; ++j) {
      int bit = (map(j) >> i) & 1; /* extract map output bit */
      if (bit == 1) {
        for (int k = 0; k < num_input_states; ++k) { /* "broadcast" result to ANF terms */
          if ((j & k) == j) { /* does this bit contribute to this ANF term? */
            anf[k] = (anf[k] + 1) % 2;
          }
        }
      }
    }
    /* step 2) print the ANF expression */
    std::cout << "y_" << i << " = ";
    int term_count = 0;
    for (int j = 0; j < anf.size(); ++j) {
      if (anf[j]) {
        std::cout << (term_count++ != 0 ? " + " : "");
        size_t factor_count = 0;
        for (int k = 0; k < num_input_bits; ++k) {
          if ((j >> k) & 1) {
            std::cout << (factor_count++ != 0 ? "*" : "");
            std::cout << "x_" << k;
          }
        }
        if (factor_count == 0) {
          std::cout << "1"; /* empty product */
        }
      }
    }
    if (term_count == 0) {
      std::cout << "0"; /* empty sum */
    }
    std::cout << std::endl;
  }
  return 0;
}

Which outputs the ANF representation of your S-Box:

y_0 = x_1 + x_0*x_1 + x_0*x_2 + x_1*x_2 + x_0*x_3 + x_0*x_2*x_3 + x_1*x_2*x_3
y_1 = 1 + x_0 + x_2 + x_0*x_2 + x_1*x_2 + x_0*x_3 + x_1*x_3
y_2 = 1 + x_0*x_1 + x_2 + x_0*x_2 + x_0*x_3 + x_0*x_1*x_3 + x_2*x_3 + x_1*x_2*x_3
y_3 = x_0*x_1 + x_3 + x_0*x_3 + x_0*x_1*x_3 + x_0*x_2*x_3

It is possible to use the SageMath, too.

from sage.crypto.sbox import SBox

S = SBox(6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11);

f1 = S.component_function(1)
f2 = S.component_function(2)
f3 = S.component_function(3)
f4 = S.component_function(4)

print ( "y1 = ", f1.algebraic_normal_form())
print ( "y2 = ", f2.algebraic_normal_form())
print ( "y3 = ", f3.algebraic_normal_form())
print ( "y4 = ", f4.algebraic_normal_form())

Providing the output

y1 =  x0*x1 + x0*x2*x3 + x0*x2 + x0*x3 + x1*x2*x3 + x1*x2 + x1
y2 =  x0*x2 + x0*x3 + x0 + x1*x2 + x1*x3 + x2 + 1
y3 =  x0*x1 + x0*x2*x3 + x0 + x1*x2*x3 + x1*x3 + x1 + x2 + 1
y4 =  x0*x1*x3 + x0*x1 + x0*x2 + x0*x3 + x1*x2*x3 + x2*x3 + x2 + 1

The Sbox package of Sage has lots of other tools, too. Some are;

• autocorrelation table
• boomerang connectivity table (BCT)
• Conjunctive Normal Form (CNF)
• fixed points
• has a linear structure
• Linearity
• Non-Linearity
• inverse
• almost perfect nonlinear (APN) function.
• Balanced
• Bent
• Involution
• Permutation
• Max Degree
• Min Degree
• polynomials satisfying the S-box.

This is useful to know in general.

Given the Sbox map, generate the truth tables for the bits of the map. From the truth tables, obtain the algebraic normal form, via the Mobius transform.

So, given an $n-$bit truth table, say $$T=[f(x): x in mathbb{F}_2^n]$$

where $$x=(x_1,ldots,x_n)$$ ranges over the vector space $mathbb{F}_2^n$ in standard order, the function has an anf representation given by $$ f(x)=sum_{y in mathbb{F}_2^n} a_y prod_{1leq ileq n~:~y_i=1} x_i $$ which means the variable $x_i$ is included in the monomial product corresponding to the coefficient $a_y$ if and only if $i$ is in the support of the vector $y.$

So if we had $y=(y_1,y_2,y_3,y_4)=(1,0,1,0),$ for $n=4,$ the coefficient $a_y$ multiplies the monomial $x_1 x_3$.

The transform computes the coefficients $a_y$ by the sum $$ a_y=sum_{xpreccurlyeq y} f(x) ~(mod~2), $$ where $x preccurlyeq y$ means the support of $x$ is a subset of the support of $y.$

The complexity is $N log N$ where $N=2^n,$ so this is a fast transform.