1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.