# Degree of a big S-box

Assume we have a big S-box (i.e. $15*15$). We have truth table of it. (so $2^{15}$ output). How can we find its degree without using Algebraic Normal Form of its Boolean functions. Or with ANF, can you help me to write the algorithm of implementing.

## 1 Answer

Take the field with $2^{15}$ elements, identify its elements with 15-bit 0/1-strings (in any linear way -- the polynomials will be dependent on the choice, but not the resulting maximal Hamming weight) and find the polynomial $p(X)$ of degree $2^{15}-1$ with $p(x) = S[x]$ for all $2^{15}$ values $x$ via Lagrange or Newton interpolation. If $p(X) = \sum_{i=0}^{2^{15}-1} p_i X^i$ then the degree you are looking for is the maximum of all Hamming weights (= number of zeros in binary representation) of exponents $i$ where $p_i\ne 0$.

So if for example $p(X) = p_7 X^7 + p_{257} X^{257}$ with $p_7\ne 0$, $p_{257}\ne 0$ then the degree is $3$, as maximum of Hamming weight(7) = Hamming weight($2^2+2^1+2^0$) = 3 and Hamming weight(257) = Hamming weight($2^8+2^0$) = 2.