Lightweight Multiplication in \(GF(2^n)\) with Applications to MDS Matrices

详细信息    查看全文

• 关键词：Finite fields ; Multiplication ; XOR ; count ; Lightweight cryptography ; MDS matrices ; Block cipher
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9814
• 期：1
• 页码：625-653
• 全文大小：508 KB
• 参考文献：1.Albrecht, M.R., Driessen, B., Kavun, E.B., Leander, G., Paar, C., Yalçın, T.: Block ciphers – focus on the linear layer (feat. PRIDE ). In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 57–76. Springer, Heidelberg (2014)CrossRef
  2.Augot, D., Finiasz, M.: Direct construction of recursive MDS diffusion layers using shortened BCH codes. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 3–17. Springer, Heidelberg (2015)
  3.Barreto, P., Nikov, V., Nikova, S., Rijmen, V., Tischhauser, E.: Whirlwind: a new cryptographic hash function. Des. Codes Crypt. 56(2–3), 141–162 (2010)MathSciNet CrossRef MATH
  4.Bertoni, G., Daemen, J., Peeters, M., Assche, G.: The Keccak reference. Submission to NIST (Round 3) (2011)
  5.Biham, E., Anderson, R., Knudsen, L.R.: Serpent: a new block cipher proposal. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, p. 222. Springer, Heidelberg (1998)CrossRef
  6.Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991)
  7.Daemen, J.: Cipher and hash function design strategies based on linear and differential cryptanalysis. Ph.D. thesis, Doctoral Dissertation, KU Leuven, March 1995
  8.Daemen, J., Knudsen, L.R., Rijmen, V.: The block cipher SQUARE. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997)CrossRef
  9.Daemen, J., Rijmen, V.: AES Proposal: Rijndael (1998). http://​csrc.​nist.​gov/​archive/​aes/​rijndael/​Rijndael-ammended.​pdf
  10.Daemen, J., Rijmen, V.: Correlation analysis in \(GF(2^n)\) . In: Advanced Linear Cryptanalysis of Block and Stream Ciphers. Cryptology and Information Security, pp. 115–131 (2011)
  11.Dummit, D.S., Foote, R.M.: Abstract Algebra. Wiley, Hoboken (2004)MATH
  12.Grosso, V., Leurent, G., Standaert, F.-X., Varici, K.: LS-designs: bitslice encryption for efficient masked software implementations. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 18–37. Springer, Heidelberg (2015)
  13.Guo, J., Peyrin, T., Poschmann, A.: The PHOTON family of lightweight hash functions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 222–239. Springer, Heidelberg (2011)CrossRef
  14.Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED block cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326–341. Springer, Heidelberg (2011)CrossRef
  15.Gupta, K.C., Ray, I.G.: Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications. Crypt. Commun. 7(2), 257–287 (2015)MathSciNet CrossRef MATH
  16.Jean, J., Peyrin, T., Sim, S.M.: Minimal implementations of linear and non-linear lightweight building blocks. Personal communication (2015)
  17.Khoo, K., Peyrin, T., Poschmann, A.Y., Yap, H.: FOAM: searching for hardware-optimal SPN structures and components with a fair comparison. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 433–450. Springer, Heidelberg (2014)
  18.Knapp, A.W.: Basic Algebra. Birkhäuser, Boston (2006)CrossRef MATH
  19.Li, Y., Wang, M.: On the construction of lightweight circulant involutory MDS matrices. In: Fast Software Encryption (FSE), LNCS. Springer, Heidelberg (2016, to appear)
  20.Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge (1994)CrossRef MATH
  21.Liu, M., Sim, S.M.: Lightweight MDS generalized circulant matrices. In: Fast Software Encryption (FSE). LNCS. Springer, Heidelberg (2016, to appear)
  22.MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland Publishing Company, Amsterdam (1977)MATH
  23.Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
  24.Sajadieh, M., Dakhilalian, M., Mala, H., Sepehrdad, P.: Recursive diffusion layers for block ciphers and hash functions. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 385–401. Springer, Heidelberg (2012)CrossRef
  25.Sarkar, S., Sim, S.M.: A deeper understanding of the XOR count distribution in the context of lightweight cryptography. In: Pointcheval, D., et al. (eds.) AFRICACRYPT 2016. LNCS, vol. 9646, pp. 167–182. Springer, Heidelberg (2016). doi:10.​1007/​978-3-319-31517-1_​9 CrossRef
  26.Silvester, J.R.: Determinants of block matrices. Math. Gaz. 84(501), 460–467 (2000)CrossRef
  27.Sim, S.M., Khoo, K., Oggier, F., Peyrin, T.: Lightweight MDS involution matrices. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 471–493. Springer, Heidelberg (2015)CrossRef
  28.Swan, R.G.: Factorization of polynomials over finite fields. Pacific J. Math. 12(3), 1099–1106 (1962)MathSciNet CrossRef MATH
  29.Wardlaw, W.P.: Matrix representation of finite fields. Math. Mag. 67(4), 289–293 (1994)MathSciNet CrossRef MATH
  30.Wu, S., Wang, M., Wu, W.: Recursive diffusion layers for (lightweight) block ciphers and hash functions. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol. 7707, pp. 355–371. Springer, Heidelberg (2013)CrossRef
  31.Xu, H., Zheng, Y., Lai, X.: Construction of perfect diffusion layers from linear feedback shift registers. IET Inf. Secur. 9(2), 127–135 (2015)CrossRef
  
• 作者单位：Christof Beierle (15)
  Thorsten Kranz (15)
  Gregor Leander (15)
  
  15. Horst Görtz Institute for IT Security, Ruhr-Universität Bochum, Bochum, Germany
  
• 丛书名：Advances in Cryptology – CRYPTO 2016
• ISBN：978-3-662-53018-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9814

文摘

In this paper we consider the fundamental question of optimizing finite field multiplications with one fixed element. Surprisingly, this question did not receive much attention previously. We investigate which field representation, that is which choice of basis, allows for an optimal implementation. Here, the efficiency of the multiplication is measured in terms of the number of XOR operations needed to implement the multiplication. While our results are potentially of larger interest, we focus on a particular application in the second part of our paper. Here we construct new MDS matrices which outperform or are on par with all previous results when focusing on a round-based hardware implementation.