# 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$ Mar 16 '18 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? Mar 16 '18 at 20:46
• No. And the correct formula for a finite field inversion s-box should be $2^{n-1}$ - $2^{n/2}$ Mar 19 '18 at 3:44
• @RichieFrame For an n bit sbox which is designed by finite field inversion the nonlinearity always $2^{n-1}-2n$? Nov 24 '20 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 Nov 24 '20 at 15:55