Cryptographic properties of cyclic binary matrices

Akbar Mahmoodi Rishakani; Seyed Mojtaba Dehnavi; Mohmmadreza Mirzaee Shamsabad; Nasour Bagheri

doi:10.3934/amc.2020068

Article Contents

2021, Volume 15, Issue 2: 311-327. Doi: 10.3934/amc.2020068

This issue Previous Article An explicit representation and enumeration for negacyclic codes of length

$ 2^kn $

over

$ \mathbb{Z}_4+u\mathbb{Z}_4 $

Next Article A note on generalization of bent boolean functions

Cryptographic properties of cyclic binary matrices

1.
Department of Sciences, Shahid Rajaee Teacher Training University, Tehran, Iran
2.
Department of Mathematicsl and Computer Sciences, Kharazmi University, Tehran, Iran
3.
Department of Mathematics and Computer Sciences, Shahid Beheshti University, Tehran, Iran
4.
Electrical Engineering Department, Shahid Rajaee Teacher Training University, Tehran, Iran

^* Corresponding author: Nasour Bagheri
^* Corresponding author: Nasour Bagheri

Received: September 2019

Revised: December 2019

Early access: January 2020

Published: May 2021

The fourth author is supported by Shahid Rajaee Teacher Training University

Abstract / Introduction Full Text(HTML) Figure(4) / Table(4) Related Papers Cited by

Abstract

Many modern symmetric ciphers apply MDS or almost MDS matrices as diffusion layers. The performance of a diffusion layer depends on its diffusion property measured by branch number and implementation cost which is usually measured by the number of XORs required. As the implementation cost of MDS matrices of large dimensions is high, some symmetric ciphers use binary matrices as diffusion layers to trade-off efficiency versus diffusion property. In the current paper, we investigate cyclic binary matrices (CBMs for short), mathematically. Based upon this theorical study, we provide efficient matrices with provable lower bound on branch number and minimal number of fixed-points. We consider the product of sparse CBMs to construct efficiently implementable matrices with the desired cryptographic properties.

Keywords:

Mathematics Subject Classification: Primary: 14G50; Secondary: 11T71, 14G50.

Citation:

Full Text(HTML)

Figure 1. The corresponding diffusion layer of ASCON

Download: Full-size image PowerPoint slide

Figure 2. An ASCON-like diffusion layer

Download: Full-size image PowerPoint slide

Figure 3. Parallel use of diffusion layers

Download: Full-size image PowerPoint slide

Figure 4. Our proposed integrated diffusion layer

Download: Full-size image PowerPoint slide

Table 1. Diffusion layers of HIGHT and ASCON

n	Source	The mapping	Number of fixed-points
8	HIGHT	circ(1, 6, 7)	8
8	HIGHT	circ(2, 4, 5)	2
64	ASCON	$ f_1 $=circ(0, 19, 28)	2
64	ASCON	$ f_2 $=circ(0, 39, 61)	4
64	ASCON	$ f_3 $=circ(0, 1, 6)	2
64	ASCON	$ f_4 $=circ(0, 10, 17)	2
64	ASCON	$ f_5 $=circ(0, 7, 41)	4

| Show Table

DownLoad: CSV

Table 2. Number of $ 16 \times 16 $ CBMs with fixed branch number

	$ b_f=4 $	$ b_f=6 $	$ b_f=8 $
$ w_f=3 $	105	-	-
$ w_f=5 $	145	1220	-
$ w_f=7 $	301	3332	1372
$ w_f=9 $	495	4644	1296
$ w_f=11 $	297	2134	572
$ w_f=13 $	169	286	-
$ w_f=15 $	15	-	-

| Show Table

DownLoad: CSV

Table 3. $ n \times n $ CBMs with maximal branch number and efficient implementation

n	mapping	$ \# $XORs	$ \# $fixed-points
16	$ circ(0,1,2)(0,2,9) $	49	4
16	$ circ(0,14,15)(0,7,14) $	49	4
16	$ circ(0,1,2)(0,7,14) $	49	16
16	$ circ(0,14,15)(0,2,9) $	49	16
16	$ circ(0,3,6)(0,5,10) $	51	16
16	$ circ(0,3,6)(0,6,11) $	51	4
32	$ circ(0,3,6)(0,4,8)(0,5,10) $	146	64
32	$ circ(0,3,6)(0,4,8)(0,22,27) $	146	4
32	$ circ(0,26,29)(0,24,28)(0,22,27) $	146	64
32	$ circ(0,4,8)(0,5,10)(0,13,26) $	148	4
32	$ circ(0,4,8)(0,22,27)(0,6,19) $	148	4
32	$ circ(0,1,2)(0,7,14)(0,12,24) $	150	64
32	$ circ(0,30,31)(0,18,25)(0,8,20) $	150	64
32	$ circ(0,1,2)(0,9,18)(0,12,24) $	150	4
32	$ circ(0,30,31)(0,14,23)(0,8,20) $	150	4
32	$ circ(0,3,6)(0,4,8)(0,11,22) $	150	4
32	$ circ(0,7,14)(0,12,24)(0,15,30) $	151	4
32	$ circ(0,9,18)(0,12,24)(0,15,30) $	151	64
32	$ circ(0,4,8 )(0,11,22)(0,13,26) $	152	64

| Show Table

DownLoad: CSV

Table 4. $ 2^m \times 2^m $, $ m \geq 6 $ CBMs with provable branch numbers and determined number of fixed-points

$ f $	$ b_{f} $	$ \# $XORs	$ \# $fixed-points
$ circ(0,1,2)(0,2,9) $	8	$ 49 \times 2^{m-4} $	4
$ circ(0,14,15)(0,7,14) $	$ \geq8 $	$ 49 \times 2^{m-4} $	4
$ circ(0,3,6)(0,4,8)(0,22,27) $	$ \geq12 $	$ 146 \times 2^{m-5} $	4
$ circ(0,4,8)(0,5,10)(0,13,26) $	$ \geq12 $	$ 148 \times 2^{m-5} $	4
$ circ(0,1,2)(0,9,18)(0,12,24) $	$ \geq12 $	$ 150 \times 2^{m-5} $	4

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Specification of the 3GPP confidentiality and integrity algorithms 128-EEA3 and 128-EIA3. document 2: ZUC specification, Online available at https://www.gsma.com/aboutus/wp-content/uploads/2014/12/eea3eia3zucv16.pdf.
[2]	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, in Selected Areas in Cryptography (Waterloo, ON, 2000), 39-56, Lecture Notes in Comput. Sci., 2012, Springer, Berlin, 2001. doi: 10.1007/3-540-44983-3_4.
[3]	B. Aslan and M. T. Sakalli, Algebraic construction of cryptographically good binary linear transformations, Security and Communication Networks, 7 (2014), 53-63. doi: 10.1002/sec.556.
[4]	S. Banik, A. Bogdanov, T. Isobe, K. Shibutani, H. Hiwatari, T. Akishita and F. Regazzoni, Midori: A block cipher for low energy (extended version), Advances in Cryptology-ASIACRYPT 2015. Part Ⅱ, 9453 (2015), 411-436. doi: 10.1007/978-3-662-48800-3_17.
[5]	C. Beierle, T. Kranz and G. Leander, Lightweight multiplication in gf(2^n) with applications to MDS matrices, in Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, 9814 (2016), 625-653. doi: 10.1007/978-3-662-53018-4_23.
[6]	B. Bilgin, A. Bogdanov, M. Knezevic, F. Mendel and Q. Wang, FIDES: Lightweight authenticated cipher with side-channel resistance for constrained hardware, Cryptographic Hardware and Embedded Systems - CHES 2013, 8086 (2013), 142-158. doi: 10.1007/978-3-642-40349-1_9.
[7]	J. Daemen and V. Rijmen, Rijndael for AES, in AES Candidate Conference, 2000,343-348. doi: 10.1007/0-387-23483-7_358.
[8]	C. Dobraunig, M. Eichlseder, F. Mendel and M. Schl ffer, Ascon v1.2, Online available at http://competitions.cr.yp.to/round3/asconv12.pdf.
[9]	P. Ekdahl and T. Johansson, A new version of the stream cipher SNOW, in Selected Areas in Cryptography, 9th Annual International Workshop, SAC 2002, St. John's, Newfoundland, Canada, August 15-16, 2002. Revised Papers (eds. K. Nyberg and H. M. Heys), vol. 2595 of Lecture Notes in Computer Science, Springer, 2003, 47-61. doi: 10.1007/3-540-36492-7_5.
[10]	D. Feng, X. Feng, W. Zhang, X. Fan and C. Wu, Loiss: A byte-oriented stream cipher, in Coding and Cryptology - Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings, 6639 (2011), 109-125. doi: 10.1007/978-3-642-20901-7_7.
[11]	M. Grassl, Code Tables: Bounds on the parameters of various types of codes, Online available at http://www.codetables.de/main.html, last access Jan. 2020.
[12]	J. Guo, J. Jean, I. Nikolic, K. Qiao, Y. Sasaki and S. M. Sim, Invariant subspace attack against midori64 and the resistance criteria for s-box designs, IACR Trans. Symmetric Cryptol., 2016 (2016), 33-56.
[13]	Z. Guo, R. Liu, S. Gao, W. Wu and D. Lin, Direct construction of optimal rotational-xor diffusion primitives, IACR Trans. Symmetric Cryptol., 2017 (2017), 169-187.
[14]	Z. Guo, W. Wu and S. Gao, Constructing lightweight optimal diffusion primitives with feistel structure, in Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers (eds. O. Dunkelman and L. Keliher), vol. 9566 of Lecture Notes in Computer Science, Springer, 2016,352-372. doi: 10.1007/978-3-319-31301-6_21.
[15]	D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B. Koo, C. Lee, D. Chang, J. Lee, K. Jeong, H. Kim, J. Kim and S. Chee, HIGHT: A new block cipher suitable for low-resource device, in Cryptographic Hardware and Embedded Systems - CHES 2006, 8th International Workshop, Yokohama, Japan, October 10-13, 2006, Proceedings, 2006, 46-59. doi: 10.1007/11894063_4.
[16]	W. Ji and L. Hu, New description of SMS4 by an embedding overgf(2⁸), in Progress in Cryptology - INDOCRYPT 2007, 8th International Conference on Cryptology in India, Chennai, India, December 9-13, 2007, Proceedings (eds. K. Srinathan, C. P. Rangan and M. Yung), vol. 4859 of Lecture Notes in Computer Science, Springer, 2007,238-251.
[17]	M. Kanda, S. Moriai, K. Aoki, H. Ueda, Y. Takashima, K. Ohta and T. Matsumoto, E2 - a new 128-bit block cipher, E83-A, (2000), 48-59.
[18]	B. Koo, H. S. Jang and J. H. Song, On constructing of a 32 $\times$32 binary matrix as a diffusion layer for a 256-bit block cipher, in Information Security and Cryptology - ICISC 2006, 9th International Conference, Busan, Korea, November 30 - December 1, 2006, Proceedings (eds. M. S. Rhee and B. Lee), vol. 4296 of Lecture Notes in Computer Science, Springer, 2006, 51-64. doi: 10.1007/11927587_7.
[19]	D. Kwon, J. Kim, S. Park, S. H. Sung, Y. Sohn, J. H. Song, Y. Yeom, E. Yoon, S. Lee, J. Lee, S. Chee, D. Han and J. Hong, New block cipher: ARIA, in Information Security and Cryptology - ICISC 2003, 6th International Conference, Seoul, Korea, November 27-28, 2003, Revised Papers (eds. J. I. Lim and D. H. Lee), vol. 2971 of Lecture Notes in Computer Science, Springer, 2003,432-445. doi: 10.1007/978-3-540-24691-6_32.
[20]	G. Leander, B. Minaud and S. Rønjom, A generic approach to invariant subspace attacks: Cryptanalysis of robin, iscream and zorro, in Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, 2015,254-283. doi: 10.1007/978-3-662-46800-5_11.
[21]	S. Ling and C. Xing, Coding Theory: A First Course, Cambridge University Press, 2004, https://books.google.com/books?id=N1jiL8V3ISwC. doi: 10.1017/CBO9780511755279.
[22]	A. M. Rishakani, S. M. Dehnavi, M. R. M. Shamsabad, H. Maimani and E. Pasha, New concepts in design of lightweight mds diffusion layers, 2014 11th International ISC Conference on Information Security and Cryptology, 2014. doi: 10.1109/ISCISC.2014.6994017.
[23]	M. Sajadieh, M. Dakhilalian and H. Mala, Perfect involutory diffusion layers based on invertibility of some linear functions, IET Information Security, 5 (2011), 228-236. doi: 10.1049/iet-ifs.2010.0289.
[24]	M. Sajadieh, M. Dakhilalian, H. Mala and P. Sepehrdad, Efficient recursive diffusion layers for block ciphers and hash functions, J. Cryptology, 28 (2015), 240-256. doi: 10.1007/s00145-013-9163-8.
[25]	M. T. Sakalli and B. Aslan, On the algebraic construction of cryptographically good 32${\times}$32 binary linear transformations, J. Computational Applied Mathematics, 259 (2014), 485-494. doi: 10.1016/j.cam.2013.05.008.
[26]	R. Schürer and W. C. Schmid, MinT: A Database for Optimal Net Parameters, In: Niederreiter H., Talay D. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2004. Springer, Berlin, Heidelberg.
[27]	B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall and N. Ferguson, Twofish: A 128-bit block cipher.,