I am looking for a 4-bit S-box which has only 4s in its difference distribution table (except the top left corner) but I was not able to find one in the literature.

Has such an S-box been already published? If not, is it theoretically possible to reach this property? If so, how to proceed?


Yes. All $4\times4$ bit S-boxes have been classified. It is possible to reach a maximum differential of 4 as well as optimum nonlinearity.

SERPENT used optimal $4\times 4$ S-boxes with respect to differential cryptanalysis. So does PRESENT, to the best of my knowledge.

Some links

SAGE is a good way to learn about and experiment with S-boxes.

Edit: None of the optimal Sboxes' representatives from Saarinen have the property of all 4's you want. I have no time, but I believe it can be proved using Theorem 1

Theorem 1

in Blondeau-Nyberg which originally appeared in Eurocrypt 94 Chabaud-Vaudenay that such a DDT pattern would yield weak S-boxes against linear cryptanalysis. Here $n=m=4,$ $cor_x(a\cdot x \oplus b\cdot F(x))$ is the correlation bias of the corresponding linear characteristic, and $P[\delta \stackrel{F}{\rightarrow} \Delta]$ is the diferential probability.

  • $\begingroup$ Although the maximum value in the DDTs of SERPENT and PRESENT is 4, some entries are also equal to 2: I'm looking for an S-box whose DDT contains 4s only. $\endgroup$ – Raoul722 Feb 6 at 21:14
  • $\begingroup$ I don't know if there is an equivalence class that contains such an example. So you want 4's and 0's. $\endgroup$ – kodlu Feb 6 at 23:27
  • $\begingroup$ why don't you go to the table at the end of the Saarinen paper and check the DDT of the 16 equiv class representatives using Sage? $\endgroup$ – kodlu Feb 6 at 23:30

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.