Wave-shaped round functions and primitive groups

Riccardo Aragona; Marco Calderini; Roberto Civino; Massimiliano Sala; Ilaria Zappatore

doi:10.3934/amc.2019004

Article Contents

2019, Volume 13, Issue 1: 67-88. Doi: 10.3934/amc.2019004

This issue Previous Article Connecting Legendre with Kummer and Edwards Next Article Optimal information ratio of secret sharing schemes on Dutch windmill graphs

Wave-shaped round functions and primitive groups

1.
DISIM, University of L'Aquila, Italy
2.
Department of Informatics, University of Bergen, Norway
3.
Department of Mathematics, University of Trento, Italy
4.
LIRMM of Montpellier, France

* Corresponding author: Roberto Civino
* Corresponding author: Roberto Civino

Received: March 2018

Revised: August 2018

Published: December 2018

R. Aragona is member of INdAM-GNSAGA (Italy). R. Civino thankfully acknowledges support by the Department of Mathematics of the University of Trento. R. Aragona, R.Civino, and M. Sala thankfully acknowledge support by MIUR-Italy via PRIN 2015TW9LSR "Group theory and applications".

Abstract Full Text(HTML) Figure(7) / Table(1) Related Papers Cited by

Abstract

Round functions used as building blocks for iterated block ciphers, both in the case of Substitution-Permutation Networks (SPN) and Feistel Networks (FN), are often obtained as the composition of different layers. The bijectivity of any encryption function is guaranteed by the use of invertible layers or by the Feistel structure. In this work a new family of ciphers, called wave ciphers, is introduced. In wave ciphers, round functions feature wave functions, which are vectorial Boolean functions obtained as the composition of non-invertible layers, where the confusion layer enlarges the message which returns to its original size after the diffusion layer is applied. Efficient decryption is guaranteed by the use of wave functions in FNs. It is shown how to avoid that the group generated by the round functions acts imprimitively, a serious flaw for the cipher. The primitivity is a consequence of a more general result, which reduce the problem of proving that a given FN generates a primitive group to proving that an SPN, directly related to the given FN, generates a primitive group. Finally, a concrete instance of real-world size wave cipher is proposed as an example, and its resistance against differential and linear cryptanalyses is also established.

Keywords:

Mathematics Subject Classification: 20B15, 20B35, 94A60.

Citation:

Full Text(HTML)

Figure 1. Round function of an SPN and of an FN

Download: Full-size image PowerPoint slide

Figure 2. Wave functions

Download: Full-size image PowerPoint slide

Figure 3. A 4x5 APN S-box

Download: Full-size image PowerPoint slide

Figure 4. Feistel structure of wave ciphers

Download: Full-size image PowerPoint slide

Figure 5. Feistel to SPN reduction

Download: Full-size image PowerPoint slide

Figure 6. An example of 40 × 32 proper diffusion layer with parallel kernel, where each "·" represents 0

Download: Full-size image PowerPoint slide

Figure 7. Diffusion properties of the matrix λ of Fig. 6.

Download: Full-size image PowerPoint slide

Table 1. Difference distribution table of the S-box $\gamma_1$ defined in Section 3.1

	0_x	1_x	2_x	3_x	4_x	5_x	6_x	7_x	8_x	9_x	A_x	B_x	C_x	D_x	E_x	F_x	10_x	11_x	12_x	13_x	14_x	15_x	16_x	17_x	18_x	19_x	1A_x	1B_x	1C_x	1D_x	1E_x	1F_x
0_x	16	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $
1_x	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2
2_x	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $
3_x	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2
4_x	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $
5_x	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2
6_x	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2
7_x	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $
8_x	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	2
9_x	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2
A_x	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $
B_x	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	2	$\cdot $	2	$\cdot $
C_x	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $
D_x	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $
E_x	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	2	$\cdot $	2	$\cdot $	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2
F_x	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	2	2	2	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	2	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $	$\cdot $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. Adams, The CAST-128 encryption algorithm, 1997, Available from: http://buildbot.tools.ietf.org/html/rfc2144.
[2]	R. J. Anderson, E. Biham and L. R. Knudsen, SERPENT: A new block cipher proposal, Fast Software Encryption, Lecture Notes in Comput. Sci., 1372 (1998), 222-238.
[3]	K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima and T. Tokita, Camellia: A 128-bit block cipher suitable for multiple platforms-design and analysis, Selected Areas in Cryptography, Lecture Notes in Comput. Sci., 2012 (2000), 39-56. doi: 10.1007/3-540-44983-3_4.
[4]	R. Aragona, M. Calderini, A. Tortora and M. Tota, Primitivity of PRESENT and other lightweight ciphers, J. Algebra Appl., 17 (2018), 1850115 (16 pages). doi: 10.1142/S0219498818501153.
[5]	R. Aragona, A. Caranti, F. Dalla Volta and M. Sala, On the group generated by the round functions of translation based ciphers over arbitrary fields, Finite Fields Appl., 25 (2014), 293-305. doi: 10.1016/j.ffa.2013.10.005.
[6]	R. Aragona, A. Caranti and M. Sala, The group generated by the round functions of a GOSTlike cipher, Ann. Mat. Pura Appl., 196 (2017), 1-17. doi: 10.1007/s10231-016-0559-6.
[7]	A. Bannier, N. Bodin and E. Filiol, Partition-Based Trapdoor Ciphers, IACR Cryptology ePrint Archive, 2016, Available from: http://eprint.iacr.org/2016/493.
[8]	E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptology, 4 (1991), 3-72. doi: 10.1007/BF00630563.
[9]	A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin and C. Vikkelsoe, PRESENT: An ultra-lightweight block cipher, CHES '07, Lecture Notes in Comput. Sci., 4727 (2007), 450-466.
[10]	K. A. Browning, J. F. Dillon, M. T. McQuistan and A. J. Wolfe, An APN permutation in dimension six, Finite Fields: theory and applications, 518 (2010), 33-42. doi: 10.1090/conm/518/10194.
[11]	M. Calderini, A note on some algebraic trapdoors for block ciphers, Adv. Math. Commun., 12 (2018), 515-524. doi: 10.3934/amc.2018030.
[12]	M. Calderini and M. Sala, Elementary abelian regular subgroups as hidden sums for cryptographic trapdoors, preprint, arXiv: 1702.00581.
[13]	M. Calderini, I. Villa and M. Sala, A note on APN permutations in even dimension, Finite Fields Appl., 46 (2017), 1-16. doi: 10.1016/j.ffa.2017.02.001.
[14]	P. J. Cameron, Permutation Groups, London Mathematical Society Student Texts, 45, Cambridge University Press, Cambridge, 1999. doi: 10.1017/CBO9780511623677.
[15]	A. Canteaut, S. Duval and L. Perrin, A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2^4k+2, IEEE Trans. Inform. Theory, 63 (2017), 7575-7591. doi: 10.1109/TIT.2017.2676807.
[16]	A. Canteaut and M. Naya-Plasencia, Structural weaknesses of permutations with low differential uniformity and generalized crooked functions, Finite Fields: Theory and Applications Selected Papers from the 9th International Conference Finite Fields and Applications, Contemporary Mathematics, 518 (2010), 55-71. doi: 10.1090/conm/518/10196.
[17]	A. Caranti, F. Dalla Volta and M. Sala, An application of the O'Nan-Scott theorem to the group generated by the round functions of an AES-like cipher, Des. Codes Cryptogr., 52 (2009), 293-301. doi: 10.1007/s10623-009-9283-1.
[18]	A. Caranti, F. Dalla Volta and M. Sala, On some block ciphers and imprimitive groups, Appl. Algebra Engrg. Comm. Comput., 20 (2009), 339-350. doi: 10.1007/s00200-009-0100-x.
[19]	D. Coppersmith and E. Grossman, Generators for certain alternating groups with applications to cryptography, SIAM J. Appl. Math., 29 (1975), 624-627. doi: 10.1137/0129051.
[20]	J. Daemen and V. Rijmen, The design of Rijndael: AES - the Advanced Encryption Standard, Information Security and Cryptography, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-04722-4.
[21]	V. Dolmatov, GOST 28147-89: encryption, decryption, and message authentication code (MAC) algorithms, technical report, 2010. Available at http://tools.ietf.org/html/rfc5830.
[22]	Federal information processing standards publication, Data Encryption Standard and Others, National Bureau of Standards, US Department of Commerce, 1977.
[23]	E. Goursat, Sur les substitutions orthogonales et les divisions régulières de l'espace, Ann. Sci. École Norm. Sup., 6 (1889), 9-102. doi: 10.24033/asens.317.
[24]	X.-D. Hou, Affinity of permutations of $\mathbb{F}_{2}^{n}$, Discrete Appl. Math., 154 (2006), 313-325. doi: 10.1016/j.dam.2005.03.022.
[25]	Jr. B. S. Kaliski, R. L. Rivest and A. T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES), J. Cryptology, 1 (1988), 3-36. doi: 10.1007/BF00206323.
[26]	M. Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in cryptology - EUROCRYPT '93, Lecture Notes in Comput. Sci., 765 (1994), 386-397.
[27]	K. Nyberg, Differentially uniform mappings for cryptography, Advances in cryptology - EUROCRYPT '93, Lecture Notes in Comput. Sci., 765 (1994), 55-64. doi: 10.1007/3-540-48285-7_6.
[28]	K. G. Paterson, Imprimitive permutation groups and trapdoors in iterated block ciphers, Fast Software Encryption, Lecture Notes in Comput. Sci., 1636 (1999), 201-214.
[29]	J. Petrillo, Goursat's other theorem, The College Mathematics Journal, 40 (2009), 119-124.
[30]	G. Piret, T. Roche and C. Carlet, PICARO-a block cipher allowing efficient higher-order sidechannel resistance, Applied Cryptography and Network Security-ACNS2012, Lecture Notes in Comput. Sci., 7341 (2012), 311-328.
[31]	C. E. Shannon, Communication theory of secrecy systems, Bell System Tech., 28 (1949), 656-715. doi: 10.1002/j.1538-7305.1949.tb00928.x.
[32]	R. Sparr and R. Wernsdorf, Group theoretic properties of Rijndael-like ciphers, Discrete Appl. Math., 156 (2008), 3139-3149. doi: 10.1016/j.dam.2007.12.011.
[33]	R. Wernsdorf, The round functions of RIJNDAEL generate the alternating group, Fast Software Encryption, Lecture Notes in Comput. Sci., 2365 (2002), 143-148.
[34]	R. Wernsdorf, The one-round functions of the DES generate the alternating group, Advances in Cryptology-EUROCRYPT '92, Lecture Notes in Comput. Sci., 658 (1993), 99-112. doi: 10.1007/3-540-47555-9_9.
[35]	R. Wernsdorf, The round functions of SERPENT generate the alternating group, 2000. Available from: http://csrc.nist.gov/archive/aes/round2/comments/20000512-rwernsdorf.pdf.