How to find the nonlinear invariants is the core step for the nonlinear invariant attack. In this paper, to reduce the costs in finding nonlinear invariants for linear transformation, an improved algorithm is proposed to obtain nonlinear invariants with low algebraic degree not more than \(\varvec{k}\) , whose time complexity is \(\varvec{O}\varvec{(}\left[ \sum \limits _{\varvec{i=1}}^{\varvec{k}}{\varvec{C}}_{\varvec{n}}^{\varvec{i}}\right] ^{\varvec{3}}\varvec{)}\) for an \(\varvec{n}\) -dimension linear transformations on binary field. Besides, for the \(\varvec{m}\times \varvec{n}\) -dimension linear transformation on binary field which applies an \(\varvec{n}\) -dimension linear transformation on binary field \(\varvec{m}\) times in parallel, this paper make further improvement of getting its all invariants with algebraic degree not more than \(\varvec{k}\varvec{(}\varvec{k}\varvec{<}\varvec{m}\varvec{)}\) , whose time complexity is \(\varvec{O}\varvec{(}\varvec{k}\left[ \sum \limits _{\varvec{i=1}}^{\varvec{k}}{\varvec{C}_{\varvec{n(k-1)}}^{\varvec{i}}}\right] ^{\varvec{3}}\varvec{+}\varvec{n}^{\varvec{3k}}\varvec{)}\) . In particular, we take the lightweight block cipher Scream as example to demonstrate the efficiency of our methods, which indicates that the methods in this paper have significant advantages than before.
