# 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$ – Richie Frame 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? – R. Sam 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}$ – Richie Frame Mar 19 '18 at 3:44

## 1 Answer

Table construction would require 148 Exabytes of RAM, so it would be hard to store all at once. This also means that you can't have a predefined S box that you might have developed either to be a random permutation, or used some sort of hill climbing technique to be better than random. You can however have a computed S box function. So it would not be a simple look up table, but rather the 64 bit output would be calculated piecemeal (byte by byte) based upon the 64 bit input. As long as the function was bijective and not surjective, you'd have S box behaviour.

So instead of a large table, you'd have a mathematical function. Without resorting to finite fields, the function could be a simple non cryptographic hash of the 64 bits /8 bytes. One implementation would be a Pearson hash of the 8 bytes, with a unique 256 byte permutation table for each byte position. That means you require 2048 bytes of RAM instead. Less than perfect non linearity could be compensated for with additional rounds, as is done in some current lightweight algoriths.

Note. You'd need a similar function for the permutation layer of your cipher as you wouldn't be able to store that easily either.

• My sample sbox is based on mixed mode modular arithmetic just like IDEA. So, i have a function for computing sbox output instead of look up table. Can you explain how to determine it's non linearity. Size is 64 x 64 bit. – R. Sam Mar 16 '18 at 20:50
• I would imagine using something like a 64-bit block cipher with a fixed key would make a fine 64-bit s-box – Richie Frame Mar 17 '18 at 0:45