Say, I want to generate a lot of $4\times4$ Sboxes with linear (or differential) branch numbre of $3$. One idea is to take all the $302$ affine classes, expand each of those classes and check if any of the Sboxes has the desired branch number.

Is there any better way/known result (such as, this particular class does not contain any Sbox with linear branch number $3$) that can be used to reduce the search space?


1 Answer 1


The differential branch number is the sum of hamming weight between input and output difference distribution table (DDT). it is similar to linear branch number.

One way to construct S-box with branch number 3 is to use concept of differential-equivalence, DDT-equivalence and the $\gamma$-equivalence as shown in paper "Two Notions of Differential Equivalence on Sboxes".

The new paper accepted "Reconstructing an S-box from its Difference Distribution Table " provides algorithm to reconstruct S-box . therefore, you could apply the concept on $\gamma$-equivalence DDT to find S-Box with branch number as you want.

  • $\begingroup$ Nice. So, this method actually [as far as I could see at a quick skim of the paper] finds an S-box with a given Difference Distribution Table, at some computational complexity. How would generating "a lot of S-boxes with given DDT" be done here? It seems you are familiar with this algorithm, are there ways of randomizing the procedure to get many different S-boxes? $\endgroup$
    – kodlu
    May 9, 2019 at 23:40
  • $\begingroup$ Iam familiar with the algorithm in the first paper , second paper is a new paper. in step 2 in the (print sbox)example in "Two Notions of Differential Equivalence on Sboxes" . you have two options (3 and 7) for F[1] producing two different boxes for the same DDT. Figure 2 shows the path of two sboxes. $\endgroup$
    – hardyrama
    May 10, 2019 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.