Home >  Results  >  Cryptographic primitives  > 



Bijective S-boxes of Different Sizes from Quasi-Cyclic Codes


We present algebraic constructions for bijective S-boxes using the binary simplex code presented as a quasi-cyclic code.
We obtain S-boxes of sizes 4, 6, 8, 9, 10, 11, 12, 14, 15, 16 and 18 with good nonlinearity.
Here are the results obtained by Dusan Bikov, Iliya Bouyukliev and Stefka Bouyuklieva in their constructions of S-Boxes from Binary Quasi-Cyclic Codes.


The Considered Constructions

There are different methods to construct quasi-cyclic codes. To connect the codes with S-boxes, we consider the binary simplex codes as quasi-cyclic codes. We use two constructions (marked as M1 and M2) of quasi-cyclic codes [2]. We use M1 and M2 constructed quasi-cyclic codes to obtain S-boxes in two different ways (C1 and C2 constructions). The constructed S-boxes are called here QCS-boxes.

Download M1 matrices - Download

Download M2 matrices - Download

Constructed QCS-boxes

Below are present the constructed QCS-boxes, that have linearity close to the Parseval bound Lin(S) ≥ 2^(n/2), the value of δ is small (δ ≥ 2), the algebraic degree deg(S) is high and the autocorrelation AC(S) is small, and compare them with the best known S-boxes.
The obtained results are presented in tables. The first column shows the used construction (C1 or C2), the used matrix (M1 or M2) and the integers m and r, the next columns contain the values of the computed cryptographic parameters, and the last column gives the number of the constructed QCS-boxes in each of the cases.
For r ≤ 15 we study the S-boxes for all permutations used as it is described in C1 and C2, otherwise we consider only a part of the permutations and therefore the study of the S-boxes constructed from the matrices M1 and M2 using construction methods C1 and C2 is not completed (we put * in the last column of the corresponding row of the table).

Download all constructed QCS-boxes (all results at once) - Download

Table 1. Bijective 4 × 4 QCS-boxes

QCS-boxes Lin nl δ deg(S) AC(S) number #
C1, M1, m = 5, r = 3 ⇓ 8 4 4 3 8 3
C1, M1, m = 3, r = 5 ⇓ 8 4 4 3 8 60
C1, M2, m = 5, r = 3 8 4 4 3 8 3
C1, M2, m = 3, r = 5 8 4 4 3 8 28
C2, M1, m = 5, r = 3 8 4 4 3 8 3
C2, M1, m = 3, r = 5 8 4 4 3 8 60
C2, M2, m = 5, r = 3 8 4 4 3 8 6
C3, M2, m = 3, r = 5 8 4 4 3 8 28


Table 2. Bijective 6 × 6 QCS-boxes

QCS-boxes Lin nl δ deg(S) AC(S) number #
C1, M1, m = 9, r = 7 16 24 4 5 16 7
16 24 4 3 32 7
16 24 4 2 64 7
C1, M2, m = 7, r = 9 16 24 8 4 24 1
C2, M1, m = 9, r = 7 16 24 4 5 16 7
C2, M1, m = 7, r = 9 16 24 4 5 16 18
C2, M2, m = 21, r = 3 16 24 4 5 16 1
C2, M2, m = 9, r = 7 16 24 4 5 16 1
C2, M2, m = 7, r = 9 16 24 4 5 16 1


Table 3. Bijective 8 × 8 QCS-boxes

QCS-boxes Lin nl δ deg(S) AC(S) number #
C1, M1, m = 17, r = 15 32 112 4 7 32 15
C1, M1, m = 15, r = 17 32 112 4 5 48 4*
32 112 4 5 56 4*
C2, M1, m = 85, r = 3 32 112 4 7 32 3
C2, M1, m = 51, r = 5 32 112 4 7 32 5
C2, M1, m = 17, r = 15 32 112 4 7 32 15
C2, M1, m = 15, r = 17 32 112 4 7 32 1*
C2, M2, m = 85, r = 3 32 112 4 7 32 1
C2, M2, m = 51, r = 5 32 112 4 7 32 1
C2, M2, m = 17, r = 15 32 112 4 7 32 1


Table 4. Bijective 10 × 10 QCS-boxes

QCS-boxes Lin nl δ deg(S) AC(S) number #
C1, M1, m = 33, r = 31 64 480 4 9 64 1*
C2, M1, m = 341, r = 3 64 480 4 9 64 3
C2, M1, m = 93, r = 11 64 480 4 9 64 11
C2, M1, m = 33, r = 31 64 480 4 9 64 1*
C2, M2, m = 341, r = 3 64 480 4 9 64 1
C2, M2, m = 93, r = 11 64 480 4 9 64 1


Table 5. Bijective 12 × 12 QCS-boxes

QCS-boxes Lin nl δ deg(S) AC(S) number #
C1, M1, m = 65, r = 63 128 1984 4 11 128 1*
C2, M1, m = 819, r = 5 128 1984 4 11 128 5
C2, M1, m = 585, r = 7 128 1984 4 11 128 7
C2, M1, m = 455, r = 9 128 1984 4 11 128 9
C2, M1, m = 315, r = 13 128 1984 4 11 128 13
C2, M2, m = 1365, r = 3 128 1984 4 11 128 1
C2, M2, m = 819, r = 5 128 1984 4 11 128 1
C2, M2, m = 585, r = 7 128 1984 4 11 128 1
C2, M2, m = 455, r = 9 128 1984 4 11 128 1
C2, M2, m = 315, r = 13 128 1984 4 11 128 1

Table 6. Bijective 14 × 14 QCS-boxes

QCS-boxes Lin nl δ deg(S) AC(S) number #
C1, M1, m = 129, r = 127 256 8064 4 13 256 1*
C2, M1, m = 5461, r = 3 256 8064 4 13 256 3
C2, M2, m = 5461, r = 3 256 8064 4 13 256 1


Table 7. Bijective QCS-boxes for n = 16 and n = 18

QCS-boxes Lin nl δ deg(S) AC(S) number #
C1, M1, n=16, m = 257, r = 255 512 32512 4 15 512 1*
C2, M1, n=16, m = 21845, r = 3 512 32512 4 15 512 3
C2, M1, n=16, m = 13107, r = 5 512 32512 4 15 512 5
C2, M2, n=16, m = 21845, r = 3 512 32512 4 15 512 1
C2, M2, n=16, m = 13107, r = 5 512 32512 4 15 512 1
C1, M1, n=18, m = 513, r = 511 1024 130560 4 17 1024 1*


Table 8. Bijective QCS-boxes for n = 9, n = 11 and n=15

QCS-boxes Lin nl δ deg(S) AC(S) number #
C2, M1, n=9, m = 73, r = 7 44 234 2 8 48 7
C2, M2, n=9, m = 73, r = 7 44 234 2 8 48 1
C2, M1, n=11, m = 89, r = 23 88 980 2 10 88 1*
C2, M1, n=15, m = 4681, r = 7 360 16204 2 14 360 7
C2, M2, n=15, m = 4681, r = 7 360 16204 2 14 360 1


Acknowledgements

We gratefully acknowledge the support of NVIDIA Corporation with the donation of the Titan X Pascal GPU used for this research.


Publications

[1] Bouyukliev, Ilija and Bikov, Dusan and Bouyuklieva, Stefka (2017) S-Boxes from Binary Quasi-Cyclic Codes. Electronic Notes in Discrete Mathematics, Volume 57. pp. 67-72. ISSN 1571-0653
[2] Bikov, Dusan and Bouyukliev, Ilija and Bouyuklieva, Stefka (2019) Bijective S-boxes of different sizes obtained from quasi-cyclic codes. Journal of Algebra Combinatorics Discrete Structures and Applications, 6 (3). pp. 123-134. ISSN 2148-838X