Research on nonlinear invariants of a power function over a binary field

The nonlinear invariant attack is a new and powerful cryptanalytic method for lightweight block ciphers. The core step of such cryptanalytic method is to find the nonlinear invariant(s) of its cascade round. Generally, for an \(\varvec{n}\) $\mathit{n}$ -bit width function, the time complexity \(\varvec{O}(\textbf{2}^{\varvec{3n}})\) $\mathit{O}({\mathbf{2}}^{\mathbf{3}\mathit{n}})$ is needed to find its all nonlinear invariants. In this paper, for the positive integer \(\varvec{m}\) $\mathit{m}$ , we consider the power function \(\varvec{x}^{\varvec{m}}\) ${\mathit{x}}^{\mathit{m}}$ over the finite field \(\varvec{GF}(\varvec{2}^{\varvec{n}})\) $\mathit{GF}({\mathbf{2}}^{\mathit{n}})$ , which is one of the most important cryptographic functions in recent decades. First, the nonlinear invariants of \(\varvec{x}^{\varvec{m}}\) ${\mathit{x}}^{\mathit{m}}$ is studied and we provide two mathematical toolboxes named \(\varvec{\sim }_{\varvec{m}}\) ${\mathbf{\sim }}_{\mathit{m}}$ periodical point and \(\varvec{\sim }_{\varvec{m}}\) ${\mathbf{\sim }}_{\mathit{m}}$ equivalence class. Second, we present an algorithm to get all the nonlinear invariants of \(\varvec{x}^{\varvec{m}}\) ${\mathit{x}}^{\mathit{m}}$ over \(\varvec{GF}(\varvec{2}^{\varvec{n}})\) $\mathit{GF}({\mathbf{2}}^{\mathit{n}})$ at the cost of time complexity \(\varvec{O}(\frac{{\varvec{2}}^{\varvec{n}}\varvec{-1}}{\varvec{\gcd (2}^{\varvec{n}}\varvec{-1,m)}})\) $\mathit{O}(\frac{{\mathbf{2}}^{\mathit{n}}\mathbf{-}\mathbf{1}}{{\mathbf{gcd}\mathbf{(}\mathbf{2}}^{\mathit{n}}\mathbf{-}\mathbf{1}\mathbf{,}\mathit{m}\mathbf{)}})$ . If the growth of n exceeds our tolerance above, another method is provided to get parts of the nonlinear invariants of \(\varvec{x}^{\varvec{m}}\) ${\mathit{x}}^{\mathit{m}}$ . Finally, we consider the nonlinear invariants of \(\varvec{x}^\textbf{3}\) ${\mathit{x}}^{\mathbf{3}}$ over \(\varvec{GF(2}^{\varvec{129}})\) ${\mathit{G}\mathit{F}\mathbf{(}\mathbf{2}}^{\mathbf{129}})$ as an application, which is used in the block cipher MiMC. It seems impractical by existing methods. The results allow us to find several (but not all) nontrivial nonlinear invariants of such a function for the first time.