Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications. (English) Zbl 1365.94432
Summary: MDS matrices incorporate diffusion layers in block ciphers and hash functions. MDS matrices are in general not sparse and have a large description and thus induce costly implementations both in hardware and software. It is also nontrivial to find MDS matrices which could be used in lightweight cryptography. In the AES MixColumn operation, a circulant MDS matrix is used which is efficient as its elements are of low hamming weights, but no general constructions and study of MDS matrices from \(d\times d\) circulant matrices for arbitrary \(d\) is available in the literature. In a SAC 2004 paper, P. Junod and S. Vaudenay [Lect. Notes Comput. Sci. 3357, 84–99 (2005; Zbl 1117.94010)] constructed a new class of efficient matrices whose submatrices were circulant matrices and they coined the term circulating-like matrices for these new class of matrices. We call these matrices as Type-I circulant-like matrices. In this paper we introduce a new type of circulant-like matrices which are involutory by construction and we call them Type-II circulant-like matrices.
We study the MDS properties of \(d\times d\) circulant, Type-I and Type-II circulant-like matrices and construct new and efficient MDS matrices which are suitable for lightweight cryptography for \(d\) up to 8. We also consider orthogonal and involutory properties of such matrices and study the construction of efficient MDS matrices whose inverses are also efficient. We explore some interesting and useful properties of circulant, Type-I and Type-II circulant-like matrices which are prevalent in many parts of mathematics and computer science.
We study the MDS properties of \(d\times d\) circulant, Type-I and Type-II circulant-like matrices and construct new and efficient MDS matrices which are suitable for lightweight cryptography for \(d\) up to 8. We also consider orthogonal and involutory properties of such matrices and study the construction of efficient MDS matrices whose inverses are also efficient. We explore some interesting and useful properties of circulant, Type-I and Type-II circulant-like matrices which are prevalent in many parts of mathematics and computer science.
Keywords:
diffusion; invmixcolumn operation; involutory matrix; maximum distance separable (MDS) matrix; mixcolumn operation; orthogonal matrixCitations:
Zbl 1117.94010References:
| [1] | Augot, D., Finiasz, M.: Direct construction of recursive MDS diffusion layers using shortened BCH codes. In: FSE (2014) · Zbl 1382.94054 |
| [2] | Barreto, P., Rijmen, V.: The Khazad legacy-level block cipher. Submission to the NESSIE Project. Available at http://cryptonessie.org (2000) |
| [3] | Barreto, P.S., Rijmen, V.: The Anubis block cipher. NESSIE Algorithm Submission. Available at http://cryptonessie.org (2000) |
| [4] | Barreto, P.S.L.M., Rijmen, V.: Whirlpool In: Encyclopedia of Cryptography and Security. 2nd edn, pp. 1384-1385 (2011) |
| [5] | Bosma, W., Cannon, J., Playoust, C.: The magma algebra system I: The User Language. J. Symbolic Comput. 24 (3-4), 235-265 (1997). Computational algebra and number theory (London, 1993) · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125 |
| [6] | Choy, J., Yap, H., Khoo, K., Guo, J., Peyrin, T., Poschmann, A., Tan, C.H.: SPN-Hash: Improving the provable resistance against differential collision attacks. In: AFRICACRYPT 2012 (2012) · Zbl 1304.94041 |
| [7] | Daemen, J., Knudsen, L.R., Rijmen, V.: The block cipher SQUARE. In: 4th Fast Software Encryption Workshop. LNCS 1267, pp. 149-165. Springer (1997) · Zbl 1385.94025 |
| [8] | Daemen, J., Rijmen, V.: The Design of Rijndael:AES - The Advanced Encryption Standard. Springer (2002) · Zbl 1065.94005 |
| [9] | Filho, G.D., Barreto, P., Rijmen, V.: The maelstrom-0 hash function. In: Proceedings of the 6th Brazilian Symposium on Information and Computer Systems Security (2006) |
| [10] | Gauravaram, P., Knudsen, L.R., Matusiewicz, K., Mendel, F., Rechberger, C., Schlaffer, M., Thomsen, S.: Gr ϕstl a SHA-3 Candidate. Submission to NIST (2008). Available at http://www.groestl.info |
| [11] | Hirschfeld, J.W.P.: The main conjecture for MDS codes, cryptography and coding. In:Proceeding of the 5th IMA Conference, pp. 44-52. Cirencester (1995) · Zbl 1383.94056 |
| [12] | Guo, J., Peyrin, T., Poschmann, A.: The PHOTON family of lightweight hash functions. In: CRYPTO 2011, pp. 222-239. Springer (2011) · Zbl 1287.94069 |
| [13] | Gupta, K.C., Ray, I.G.: On constructions of involutory MDS matrices. In: AFRICACRYPT 2013, pp. 43-60. Springer (2013) · Zbl 1312.94038 |
| [14] | Gupta, K.C., Ray, I.G.: On constructions of MDS matrices from companion matrices for lightweight cryptography. In: CD-ARES 2013 Workshops: MoCrySEn, pp. 29-43. Springer (2013) |
| [15] | Gupta, K.C., Ray, I.G.: On constructions of circulant MDS matrices for lightweight cryptography. In: ISPEC 2014, pp. 564-576. Springer (2014) |
| [16] | Nakahara J. Jr, Abrahao, E.: A new involutory mds matrix for the AES. Int. J. Netw. Secur. 9 (2), 109-116 (2009) |
| [17] | Junod, P., Vaudenay, S.: Perfect diffusion primitives for block ciphers building efficient MDS matrices. Selected Areas in Cryptography 2004. Lecture Notes in Computer Science. Springer, Waterloo, Canada. Revisited papers, · Zbl 1117.94010 |
| [18] | Junod, P., Vaudenay, S.: FOX: a new family of block ciphers. Selected Areas in Cryptography, SAC. pp. 114-119. Springer, LNCS (2004) · Zbl 1117.94322 · doi:10.1007/978-3-540-30564-4_8 |
| [19] | Junod, P., Macchetti, M.: Revisiting the IDEA philosophy In: 16th International Workshop (FSE), Fast Software Encryption. Lecture Notes in Computer Science, 5665, pp. 277-295. Springer (2009) · Zbl 1291.94109 |
| [20] | Lacan, J., Fimes, J.: Systematic MDS erasure codes based on vandermonde matrices. IEEE Trans. Commun. Lett. 8 (9), 570572 (2004). CrossRef |
| [21] | Lo, J.W., Hwang, M.S., Liu, C.H.: An efficient key assignment scheme for access control in a large leaf class hierarchy. In: Journal of Information Sciences: An International Journal Archive, vol. 181, no. 4, pp. 917-925. Elsevier, New York (2011) · Zbl 1208.94048 |
| [22] | MacWilliams, F.J., Sloane, N.J.A: The Theory of Error Correcting Codes. North Holland (1986) · Zbl 0369.94008 |
| [23] | Rao, A.R., Bhimasankaram, P.: Linear Algebra, 2nd edn. Hindustan Book Agency · Zbl 0982.15001 |
| [24] | Rijmen, V., Daemen, J., Preneel, B., Bosselaers, A., Win, E.D.: The cipher SHARK. In: 3rd Fast Software Encryption Workshop, LNCS 1039. pp. 99-112. Springer (1996) · Zbl 1373.94929 |
| [25] | Sajadieh, M., Dakhilalian, M., Mala, H., Omoomi, B.: On construction of involutory MDS matrices from Vandermonde matrices in GF(2q). In: Design, Codes Cryptography (2012) · Zbl 1255.94083 |
| [26] | Sajadieh, M., Dakhilalian, M., Mala, H., Sepehrdad, P.: Recursive diffusion layers for block ciphers and hash functions. In: FSE 2012, pp. 385-401. Springer (2012) · Zbl 1312.94088 |
| [27] | Schneier, B., Kelsey, J., Whiting, D., Wagner, D., Hall, C., Ferguson, N.: Twofish: A 128-bit block cipher. In: The First AES Candidate Conference. National Institute for Standards and Technology (1998) |
| [28] | Schneier, B., Kelsey, J., Whiting, D., Wagner, D., Hall, C., Ferguson, N.: The Twofish Encryption Algorithm. Wiley (1999) · Zbl 0929.94018 |
| [29] | Schnorr, C., Vaudenay, S.: Black box cryptanalysis of hash networks based on multipermutations. In: De Santis, A. (ed.) Proceedings of LNCS Advances in Cryptology - EUROCRYPT 94, vol. 950, pp. 47-57. Springer (1995) · Zbl 0909.94013 |
| [30] | Shannon, C.E: Communication theory of secrecy systems. Bell Syst. Technical J. 28, 656-715 (1949) · Zbl 1200.94005 · doi:10.1002/j.1538-7305.1949.tb00928.x |
| [31] | Shiraj, T., Shibutani, K.: On the diffusion matrix employed in the Whirlpool hashing function. Available at http://www.cosic.esat.kuleuven.be/nessie/reports/.../whirlpool-20030311.pdf. |
| [32] | Sony Corporation: The 128-bit block cipher CLEFIA algorithm specification (2007). Available at http://www.sony.co.jp/Products/cryptography/clefia/download/data/clefia-spec-1.0.pdf. |
| [33] | S. Vaudenay: On the need for multipermutations: Cryptanalysis of MD4 and SAFER. In: Preneel, B. (ed.) Proceedings of LNCS Fast Software Encryption, vol. 1008, pp. 286-297. Springer (1995) · Zbl 0939.94542 |
| [34] | Watanabe, D., Furuya, S., Yoshida, H., Takaragi, K., Preneel, B.: A new keystream generator MUGI. In: FSE 2002. pp. 179-194. Springer, Berlin/Heidelberg (2002) · Zbl 1045.94534 |
| [35] | Wu, S., Wang, M., Wu, W.: Recursive diffusion layers for (Lightweight) block ciphers and hash functions. In: SAC 2012, LNCS 7707, pp. 355-371. Springer, Berlin Heidelberg (2013) · Zbl 1327.94079 |
| [36] | Youssef, A.M., Tavares, S.E., Heys, H.M.: A new class of substitution permutation networks. In: Workshop on Selected Areas in Cryptography, SAC ’96. Workshop Record (1996) · Zbl 1200.94005 |
| [37] | Youssef, A.M., Mister, S., Tavares, S.E.: On the design of linear transformations for substitution permutation encryption networks. In: Workshop On Selected Areas in Cryptography, SAC 97. pp. 40-48 (1997) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
