A Generalization of the Subfield Construction

Abstract

The subfield construction is one of the most promising methods to construct maximum distance separable (MDS) diffusion layers for block ciphers and cryptographic hash functions. In this paper, we give a generalization of this method and investigate the efficiency of our generalization. As a result, we provide several best MDS diffusions with respect to the number of XORs that the diffusion needs. For instance, we give \begin{itemize} \item an involutory MDS diffusion $\mathbb{F}_{2^8}^{3} \rightarrow \mathbb{F}_{2^8}^{3}$ by 85 d-XORs and \item an involutory MDS diffusion $\mathbb{F}_{2^8}^{4} \rightarrow \mathbb{F}_{2^8}^{4}$ by 122 d-XORs \end{itemize} and hence present new records to the literature. Furthermore, we interpret the coding theoretical background of our generalization.

Keywords

• maximum distance separable (MDS) matrices
• subfield construction
• mds codes

References

1. Barreto PSLM, Nikov V, Nikova S, Rijmen V, Tischhauser E. Whirlwind: a new cryptographic hash function. Designs, Codes and Cryptography 2010; 56 (2–3): 141–162.
2. Beierle C, Kranz T, Leander G. Lightweight multiplication in $\mathrm{GF}(2^n)$ with applications to MDS matrices. In: CRYPTO 2016, Part I; Ed. by Matthew Robshaw and Jonathan Katz, LNCS vol. 9814, Springer, 2016, pp. 625–653.
3. Boyar J, Find MG, Peralta R. Small low-depth, low-size circuits for cryptographic applications. Cryptography and Communications 2019; 11: 109–127.
4. Boyar J, Matthews P, Peralta R. On the shortest linear straight-line program for computing linear forms. In: International Symposium on Mathematical Foundations of Computer Science (MFCS) 2008; LNCS vol. 5162, 2008, pp. 168–179.
5. Boyar J, Matthews P, Peralta R. Logic minimization techniques with applications to cryptology. Journal of Cryptology 2013; 26 (2): 280–312.
6. Boyar J, Peralta R. A new combinational logic minimization technique with applications to cryptology. In: International Symposium on Experimental Algorithms (SEA) 2010; LNCS vol. 6049, 2010, pp. 178–189.
7. Daemen J, Rijmen V. The wide trail design strategy. In: IMA International Conference on Cryptography and Coding (IMACC) 2001; LNCS vol 2260, Springer, 2001, pp. 222-238.
8. Daemen J, Rijmen V. The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography, Springer, 2002.

9. Gupta KC, Pandey SK, Ray IG, Samanta S. Cryptographically significant MDS matrices over finite fields: a brief survey and some generalized results. Advances in Mathematics of Communications 2019; 13 (4): 779-843.
10. G\"uzel GG, Sakall\i\ MT, Akleylek S, Rijmen V, \c{C}engellenmi\c{s} Y. A new matrix form to generate all $3\times 3$ involutory MDS matrices over $\mathbb{F}_{2^m}$. Information Processing Letters 2019; 147: 61-68.
11. Jean J, Peyrin T, Sim SM, Tourteaux J. Optimizing implementations of lightweight building blocks. IACR Transactions on Symmetric Cryptology 2017; 2017 (4): 130-168.
12. Junod P, Vaudenay S. Perfect diffusion primitives for block ciphers." In: Selected Areas in Cryptography (SAC) 2004; LNCS vol. 3357, 2005, pp. 84-99.
13. Khoo K, Peyrin T, Poschmann AY, Yap H. FOAM: searching for hardware-optimal SPN dtructures and components with a fair comparison. In: Conference on Cryptographic Hardware and Embedded Systems (CHES) 2014, pp. 433-450.
14. Kranz T, Leander G, Stoffelen K, Wiemer F. Shorter linear straight-line programs for MDS matrices. IACR Transactions on Symmetric Cryptology 2017; 2017 (4): 188-211.
15. Pehlivanoğlu MK, Sakallı MT, Akleylek S, Duru N, Rijmen V. Generalisation of Hadamard matrix to generate involutory MDS matrices for lightweight cryptography. IET Information Security 2018 12 (4): 348-355.
16. Li S, Sun S, Li C, Wei Z, Hu L. Constructing low-latency involutory MDS matrices with lightweight circuits. IACR Transactions on Symmetric Cryptology 2019; 2019 (1): 84-117.
17. Li Y, Wang M. On the Construction of lightweight circulant involutory MDS matrices. In: Fast Software Encryption Workshop (FSE) 2016; Ed. by Thomas Peyrin, LNCS vol. 9783, Springer, Mar. 2016, pp. 121–139.
18. Lidl R, Niederreiter H. Introduction to Finite Fields and Their Applications. Cambridge, UK: Cambridge University Press, 1994.
19. Liu Y, Rijmen V, Leander G. Nonlinear diffusion layers. Designs, Codes and Cryptography 2018; 86 (11): 2469-2484.
20. Liu M, Sim SM. Lightweight MDS generalized circulant matrices. In: Fast Software Encryption Workshop (FSE) 2016; Ed. by Thomas Peyrin, LNCS vol. 9783, Springer, Mar. 2016, pp. 101–120.
21. Paar C. Optimized arithmetic for Reed-Solomon encoders. In: IEEE International Symposium on Information Theory (ISIT) 1997; IEEE, 1997 pp. 250–250.
22. Roth RM. Introduction to Coding Theory. Cambridge, UK: Cambridge University Press, 2006.
23. Sim SM, Khoo K, Oggier FE, Peyrin T. Lightweight MDS involution matrices. In: Fast Software Encryption Workshop (FSE) 2015; Ed. by Gregor Leander, LNCS vol. 9054, Springer, Mar. 2015, pp. 471–493.
24. Sarkar S, Syed H. Lightweight diffusion layer: importance of Toeplitz matrices. IACR Transactions on Symmetric Cryptology 2016; 2016 (1): 95-113.
25. Sarkar S, Syed H. Analysis of Toeplitz MDS matrices. In: Australasian Conference on Information Security and Privacy (ACISP) 17, Part II; Ed. by Josef Pieprzyk and Suriadi Suriadi, LNCS vol. 10343, Springer, July 2017, pp. 3–18.
26. Visconti A, Schiavo CV, Peralta R. Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2). Information Processing Letters 2018; 137: 1-5.