1
$\begingroup$

I am trying to figure out whether the following simple s-box configuration I created is more linear than non-linear or vice versa more non-linear than linear?

The parameters for this 16*4 table of 64 values, is it takes any arbitrary 6-bit binary string, and uses the left-most column for the outer-bits (first and last) and top-row for the inner 4-bits as lookup values, to output a 4 bit final value.

Example: a binary value of 101010, starts with 1 and ends with 0 so the third row would be used for part of the coordinate lookup value, and the inner bits of 0101 correspond to the sixth column and point to the coordinate 1111. So an binary value of 101010 would transform to 1111.

This s-box was created using a deterministic process involving XOR and one of the conditions it meets for non-linearity is that each output has 4 pre-images, but I am otherwise not sure if it is totally linear or to what degree, if any, it has non-linearity and other desired s-box properties such as discussed here: Desirable S-box properties

Sidenote: It also has a balanced hamming distance of all values, not sure if that is applicable either helping or hurting it one way or another.

Is the following s-box more linear or more non-linear?

P.S. There have been other questions about s-box linearity but those used AES-'s s-box How are the AES S-Boxes calculated? or the one from DES S-box basic question.

$\endgroup$
6
  • 2
    $\begingroup$ Steve, it looks like this to me $\endgroup$
    – Paul Uszak
    Jul 1, 2019 at 22:51
  • $\begingroup$ Thanks @PaulUszak, do you know how to format it to resize it? In the meantime, I'll add it as a photo. $\endgroup$ Jul 2, 2019 at 6:03
  • 1
    $\begingroup$ please define the parameters. is it a 6-bit to 4-bit mapping? like DES sboxes? $\endgroup$
    – kodlu
    Jul 2, 2019 at 6:22
  • $\begingroup$ Yes, pardon added that now. $\endgroup$ Jul 2, 2019 at 6:26
  • 1
    $\begingroup$ Sorry, but I don't. I also don't have your patience to type all of that in so I'd just screen grab it as an image :-( The other thing to note re. AES, is that this one isn't invertable, whereas AES' is. $\endgroup$
    – Paul Uszak
    Jul 2, 2019 at 9:38

2 Answers 2

5
$\begingroup$

Yes, your table is perfectly linear: The output is the sum of the inner four bits plus left outer bit*0101 plus right outer bit*1010.

$\endgroup$
0
$\begingroup$

In general for any Sbox map $$S:\{0,1\}^n\rightarrow\{0,1\}^m$$ the map is linear or affine if and only if some Walsh-Hadamard transform coefficient of the function $$b \cdot S(X)$$ with $n$ bit input $X$ takes on the value $\pm 2^{n},$ for some $b \neq0,$ $b\in \{0,1\}^m.$

See here for an explanation of Walsh-Hadamard transforms.

$\endgroup$

Your Answer

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

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