Abstract
We consider the function \(x^{-1}\) that inverses a finite field element \(x \in \mathbb {F}_{p^n}\) (p is prime, \(0^{-1} = 0\)) and affine \(\mathbb {F}_{p}\)-subspaces of \(\mathbb {F}_{p^n}\) such that their images are affine subspaces as well. It is proved that the image of an affine subspace L, \(|L |> 2\), is an affine subspace if and only if \(L = s\mathbb {F}_{p^k}\), where \(s\in \mathbb {F}_{p^n}^{*}\) and \(k \mid n\). In other words, it is either a subfield of \(\mathbb {F}_{p^n}\) or a subspace consisting of all elements of a subfield multiplied by \(s\). This generalizes the results that were obtained for linear invariant subspaces in 2006. As a consequence, the function \(x^{-1}\) maps the minimum number of affine subspaces to affine subspaces among all invertible power functions. In addition, we propose a sufficient condition providing that a function \(A(x^{-1}) + b\) has no invariant affine subspaces U of cardinality \(2< |U |< p^n\) for an invertible linear transformation \(A: \mathbb {F}_{p^n} \rightarrow \mathbb {F}_{p^n}\) and \(b \in \mathbb {F}_{p^n}^{*}\). As an example, it is shown that the S-box of the AES satisfies the condition. Also, we demonstrate that some functions of the form \(\alpha x^{-1} + b\) have no invariant affine subspaces except for \(\mathbb {F}_{p^n}\), where \(\alpha , b \in \mathbb {F}_{p^n}^{*}\) and n is arbitrary.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Budaghyan L.: Construction and Analysis of Cryptographic Functions. Springer, Cham (2015).
Burov D.A.: About existence of the special nonlinear invariants for round functions of XSL-ciphers. Diskr. Mat. 33(2), 31–45 (2021). https://doi.org/10.4213/dm1638(in Russian).
Caranti A., Volta F.D., Sala M., Villani F.: Imprimitive permutations groups generated by the round functions of key-alternating block ciphers and truncated differential cryptanalysis. arXiv (2006). https://doi.org/10.48550/ARXIV.MATH/0606022.
Caranti A., Volta F., Sala M.: An application of the O’Nan–Scott theorem to the group generated by the round functions of an AES-like cipher. Des. Codes Cryptogr. 52, 293–301 (2009). https://doi.org/10.1007/s10623-009-9283-1.
Caranti A., Volta F., Sala M.: On some block ciphers and imprimitive groups. Appl. Algebra Eng. Commun. Comput. 20, 339–350 (2009). https://doi.org/10.1007/s00200-009-0100-x.
Carlet C.: Open questions on nonlinearity and on APN functions. In: Koç Ç.K., Mesnager S., Savaş E. (eds.) Arithmetic of Finite Fields. LNCS, vol. 9061, pp. 83–107. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16277-5_5.
Carlet C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021).
Daemen J., Rijmen V.: The Design of Rijndael: AES - The Advanced Encryption Standard, p. 238. Springer, Heidelberg (2002) https://doi.org/10.1007/978-3-662-04722-4.
Dinur I., Shamir A.: Breaking grain-128 with dynamic cube attacks. In: Joux A. (ed.) Fast Software Encryption. LNCS, vol. 6733, pp. 167–187. Springer, Heidelberg (2011).
Dworkin M., Barker E., Nechvatal J., Foti J., Bassham L., Roback E., Dray J.: Advanced Encryption Standard (AES). Federal Inf. Process. Stds. (NIST FIPS). National Institute of Standards and Technology, Gaithersburg (2001). https://doi.org/10.6028/NIST.FIPS.197.
Goldstein D., Guralnick R., Small L., Zelmanov E.: Inversion-invariant additive subgroups of division rings. Pac. J. Math. 227(2), 287–294 (2006). https://doi.org/10.2140/pjm.2006.227.287.
Hua L.-K.: Some Properties of a field. Proc. Natl. Acad. Sci. USA 35(9), 533–537 (1949). https://doi.org/10.1073/pnas.35.9.533.
Idrisova V.A., Tokareva N.N., Gorodilova A.A., Beterov I.I., Bonich T.A., Ishchukova E.A., Kolomeec N.A., Kutsenko A.V., Malygina E.S., Pankratova I.A., Pudovkina M.A., Udovenko A.N.: Mathematical problems and solutions of the ninth International Olympiad in cryptography NSUCRYPTO. Prikl. Diskr. Mat. 62 (2023, in press)
Jacobson N.: Basic Algebra I, 2nd edn Dover Publications, Mineola (2009).
Leander G., Abdelraheem M.A., AlKhzaimi H., Zenner E.: A Cryptanalysis of PRINTCIPHER: The Invariant Subspace Attack. In: Rogaway, P. (ed.) Advances in Cryptology—CRYPTO 2011. LNCS, vol. 6841, pp. 206–221. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_12.
Leander G., Minaud B., Rønjom S.: A Generic Approach to Invariant Subspace Attacks: Cryptanalysis of Robin, iSCREAM and Zorro. In: Oswald E., Fischlin M. (eds.) Advances in cryptology – EUROCRYPT 2015. LNCS, vol. 9056, pp. 254–283. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_11.
Lidl R., Niederreiter H.: Finite Fields, 2nd edn. Encyclopedia of Mathematics and its Applications, vol. 20. Cambridge University Press, Cambridge (1997)
Logachev O.A., Salnikov A.A., Yashchenko V.V.: Boolean Functions in Coding Theory and Cryptography. Translations of Mathematical Monographs, vol. 241. American Mathematical Society, Providence (2012).
Mattarei S.: Inverse-closed additive subgroups of fields. Isr. J. Math. 159, 343–347 (2007). https://doi.org/10.1007/s11856-007-0050-6.
Nyberg K.: Differentially uniform mappings for cryptography. In: Helleseth T. (ed.) Advances in Cryptology — EUROCRYPT’93. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48285-7_6.
Todo Y., Leander G., Sasaki Y.: Nonlinear invariant attack: practical attack on full SCREAM, iSCREAM, and Midori64. J. Cryptol. 32, 1383–1422 (2019). https://doi.org/10.1007/s00145-018-9285-0.
Tokareva N.: Bent Functions: Results and Applications to Cryptography. Academic Press, New York (2015).
Trifonov D.I., Fomin D.B.: Invariant subspaces in SPN block cipher. Prikl. Diskr. Mat. 54, 58–76 (2021) (in Russian).
Acknowledgements
The work is supported by the Mathematical Center in Akademgorodok under the Agreement No. 075–15–2022–282 with the Ministry of Science and Higher Education of the Russian Federation. The authors would like to thank the anonymous reviewers for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by C. Carlet.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Kolomeec, N., Bykov, D. On the image of an affine subspace under the inverse function within a finite field. Des. Codes Cryptogr. 92, 467–476 (2024). https://doi.org/10.1007/s10623-023-01316-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-023-01316-3