Relying on a 4-bit S-box instead of an 8-bit one

Question

I've discovered that generating good S-boxes with only modular addition, bitwise XOR, bitwise AND, bitwise OR, bitwise NOT, rotations, and, shifts is difficult. I figure that using them to make a good 4-bit S-box will be easier. But, does using a 4-bit S-box instead of an 8-bit one degrade security by a large margin?

Answer 1

While an ideal 4x4 s-box will have less ideal properties compared to an ideal 8x8 s-box, you can make up the difference with more applications of the smaller s-box.

As an example, the worst differential in the AES s-box is 4/256, or 1/64. If your s-box only has 16 entries, you clearly cannot obtain an entry nearly so low as 1/64 - the lowest possible entry is only 1/16 in the smaller s-box (neglecting the need for uniformity). But if you apply your smaller s-box repeatedly, you can see that the overall probability can be made to be equivalent.

Note that the design of 4x4 s-boxes is basically a solved problem - there are multiple papers out there that have already searched through all possible 4-bit mapping and found the s-boxes with optimal properties that can be implemented in a minimum number of instructions from among all 4x4 s-boxes.