2
$\begingroup$

In paper https://eprint.iacr.org/2011/218.pdf, the author has examined 16! different 4 bit SBoxes and at the end of investigation, introduced an optimal class which named "Golden SBoxes". How can I extract one SBoxes from this class?

I mean by knowing the canonical representation of Golden SBoxes as "035869C7DAE41FB2","03586CB79EADF214","03586AF4ED9217CB" and "03586CB7A49EF12D"(table 4 of paper),

how can I extract the golden sboxes such as Serpent S-Box S3, Hummingbird-1 SBoxes S1, S2, and S3 and Hummingbird-2 SBoxes S0 and S1?

$\endgroup$
2
$\begingroup$

in extension to koldu answer , $M_0$ and $M_1$ are 4 bit binary matrices, the number of invertible binary matrices is 20160 (approximately $2^{14}$) using this formula:

$$\sharp S_n=\prod_{k=1}^n(2^n-2^{k-1})$$ where $n$ is 4 bit in this case.

there are two binary matrices and two affine constants (size of $2^4$) , the computation complexity is quite high using brute force , therefore , there are some tricks such as An Improved Affine Equivalence Algorithm for Random Permutations to reduce complexity.

$\endgroup$
2
$\begingroup$

This illustrates the idea with no efficiencies considered. Take the canonical Sbox, and let $$X:=[X[1],\ldots,X[16]]$$ be the vectors in $\{0,1\}^4$ in the order given by the canonical Sbox map.

Looping through all invertible $4\times4$ matrices $M_0,M_i$ and all constant vectors $c_0,c_i$ compute the list of column matrices $$ F(M_0,M_i,c_0,c_i):=M_0 \cdot [M_i\cdot(X[1]\oplus c_i),M_i\cdot(X[2]\oplus c_i), \ldots M_i\cdot(X[16]\oplus c_i)]\oplus [c_0,\ldots,c_0], $$ and you will find the target Sboxes for some $F$ computed during this process.

See extract from the paper quoted in the question below:

here

$\endgroup$
  • $\begingroup$ paper link is not available.I can not extract paper from the given link. $\endgroup$ – Arsalan Vahi Apr 13 at 8:22
  • $\begingroup$ its the paper from the question $\endgroup$ – kodlu Apr 13 at 9:44

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.