Structural cryptanalysis and storage efficiency of Kronecker-product diffusion layers for lightweight block ciphers
DOI:
https://doi.org/10.56764/hpu2.jos.2026.5.02.65-83Abstract
Matrix-based linear transformations are fundamental to the diffusion properties of modern block ciphers. This paper investigates the algebraic structure and security of the Dual-Matrix Affine Modular construction \(C\equiv K_LMK_R+K_S\pmod p.\) Although it is structurally isomorphic to a constrained affine map on \(\mathbb{Z}_p^{n^2}\) via the Kronecker product \(K_R^T\otimes K_L\), this construction offers a significant efficiency advantage: it reduces the storage complexity from \(\mathcal{O}(n^4)\) (for a generic linear layer) to \(\mathcal{O}(n^2)\). We formally derive the effective key space and present a rigorous structural chosen-plaintext attack. We prove that by exploiting the tensor decomposition property, an equivalent key tuple can be recovered in \(\mathcal{O}(n^4)\) field operations, significantly bypassing the \(\mathcal{O}(n^6)\) complexity of generic affine cryptanalysis. Our results demonstrate that while insecure as a standalone primitive, this structure offers a favorable trade-off between large-state diffusion and implementation cost, making it a compelling candidate for the mixing layer in lightweight Substitution-Permutation Networks (SPNs).
References
[1] L. S. Hill, “Cryptography in an algebraic alphabet,” The American Mathematical Monthly, vol. 36, no. 6, pp. 306–312, 1929, doi: 10.2307/2298294.
[2] National Institute of Standards and Technology, “Advanced Encryption Standard (AES),” FIPS 197, May 2023, doi: 10.6028/NIST.FIPS.197-upd1.
[3] J. Daemen and V. Rijmen, The Design of Rijndael: AES—The Advanced Encryption Standard, Berlin, Germany: Springer, 2002, doi: 10.1007/978-3-662-04722-4.
[4] C. E. Shannon, “A mathematical Theory of Communication,” Bell System Technical Journal, vol. 27, pp. 379–423 and 623–656, 1948, doi: 10.1002/j.1538-7305.1948.tb01338.x.
[5] C. E. Shannon, “Communication Theory of Secrecy Systems,” Bell System Technical Journal, vol. 28, no. 4, pp. 656–715, Oct. 1949, doi: 10.1002/j.1538-7305.1949.tb00928.x.
[6] D. R. Stinson and M. B. Paterson, Cryptography: Theory and Practice, 4th ed. Boca Raton, FL, USA: CRC Press, 2018, doi: 10.1201/9781315282497.
[7] J. Katz and Y. Lindell, Introduction to Modern Cryptography, 3rd ed. Boca Raton, FL, USA: Chapman and Hall/CRC, 2020, doi: 10.1201/9781351133036.
[8] B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed., New York, NY, USA: Wiley, 1996.
[9] W. Stallings, Cryptography and Network Security: Principles and Practice, 7th ed., Boston, MA, USA: Pearson, 2017.
[10] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 2013, doi: 10.1017/CBO9781139020411.
[11] R. Lidl and H. Niederreiter, “Finite Fields,” Cambridge, U.K.: Cambridge Univ. Press, Oct.1996, doi: 10.1017/CBO9780511525926.
[12] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, vol. 4, no. 1, pp. 3–72, Jan. 1991, doi: 10.1007/BF00630563.
[13] M. Matsui, “Linear cryptanalysis method for DES cipher,” in Advances in Cryptology—EUROCRYPT ’93, Lecture Notes in Computer Science, vol. 765, T. Helleseth, Ed. Berlin, Germany: Springer-Verlag, 1994, pp. 386–397, doi: 10.1007/3-540-48285-7_33.
[14] W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654, Nov. 1976, doi: 10.1109/TIT.1976.1055638.
[15] M. Dworkin, “Recommendation for block cipher modes of operation: Methods and techniques,” NIST Special Publication 800-38A, Dec. 2001, doi: 10.6028/NIST.SP.800-38A.
[16] M. Dworkin, “Recommendation for block cipher modes of operation: The CMAC Mode for Authentication,” NIST Special Publication 800-38B, Jan. 2005, doi: 10.6028/NIST.SP.800-38B-2005.
[17] E. Barker and J. Kelsey, “Recommendation for random number generation using deterministic random bit generators,” NIST Special Publication 800-90A Rev. 1, Jun. 2015, doi: 10.6028/NIST.SP.800-90Ar1.
[18] National Institute of Standards and Technology, “Digital Signature Standard (DSS),” FIPS 186-5, Feb. 2023, doi: 10.6028/NIST.FIPS.186-5.
[19] R. Bassous, A. Mansour, R. Assous, H. Fu, Y. Zhu, and G. Corser, “Ambiguous multi-symmetric scheme and applications,” Journal of Information Security, vol. 8, no. 4, pp. 383–401, Oct. 2017, doi: 10.4236/jis.2017.84024.
[20] H. Huang, W. Kong, and T. Xu, “Asymmetric cryptography based on the tropical Jones matrix,” Symmetry, vol. 16, no. 4, Art. no. 456, Apr. 2024, doi: 10.3390/sym16040456.
[21] H. Huang, L. Deng, C. Li, and C. Pan, “Cryptanalysis of an encryption scheme using matrices over finite fields,” Chinese Journal of Electronics, vol. 27, no. 2, pp. 293–296, Mar. 2018, doi: 10.1049/cje.2017.07.007.
[22] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, Boca Raton, FL, USA: CRC Press, Dec. 2018, doi: 10.1201/9781439821916.
[23] H. Anton and C. Rorres, Elementary Linear Algebra: Applications Version, 11th ed., New York, NY, USA: Wiley, 2013.
[24] D. J. Bernstein, J. Buchmann, and E. Dahmen (Eds.), Post-Quantum Cryptography. Berlin, Germany: Springer, 2009, doi: 10.1007/978-3-540-88702-7.
[25] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis. Cambridge, U.K.: Cambridge Univ. Press, 1991, doi: 10.1017/CBO9780511840371.
[26] A. Sinkov, Elementary Cryptanalysis: A Mathematical Approach, Washington, DC, USA: Mathematical Association of America, 2009, doi: 10.5948/UPO9780883859377.
Downloads
Published
How to Cite
Volume and Issue
Section
Copyright and License
Copyright (c) 2026 Thi-Tuyet Phan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
