# Non Linearity of huge Sbox

Sboxes provide confusion in cipher. Non Linearity measures the strength of sbox layer. In order to measure non linearity of sbox, a table is computed to measure distances with its affine functions. If the dimensions of sbox are huge say eg 64 bits input to 64 bit output, how to determine it's non linearity as table construction is not computationally possible?

• If it is made by finite field inversion, like the AES s-box, then yes it is possible, as the nonlinearity follows a simple rule. I think it is $2^{n-1}$ - $2n$ Commented Mar 16, 2018 at 11:22
• The sample sbox is based on mixed mode modular arithmetic like IDEA cipher. Is this rule applicable to mixed mode modular arithmetic based sbox? Commented Mar 16, 2018 at 20:46
• No. And the correct formula for a finite field inversion s-box should be $2^{n-1}$ - $2^{n/2}$ Commented Mar 19, 2018 at 3:44
• @RichieFrame For an n bit sbox which is designed by finite field inversion the nonlinearity always $2^{n-1}-2n$? Commented Nov 24, 2020 at 10:40
• @Radium as long as $n$ is even, I believe the answer is yes, not sure when it is odd, still might be, but see my corrected equation in the comments Commented Nov 24, 2020 at 15:55