On algebraic immunity of trace inverse functions on finite fields of characteristic two

The trace inverse functions Tr(λx ^-1) over the finite field \({F_{{2^n}}}\) are a class of very important Boolean functions and are used in many stream ciphers such as SFINKS, RAKAPOSHI, the simple counter stream cipher (SCSC) presented by Si W and Ding C (2012), etc. In order to evaluate the security of those ciphers in resistance to (fast) algebraic attacks, the authors need to characterize algebraic properties of Tr(λx ^-1). However, currently only some bounds on algebraic immunity of Tr(λx ^-1) are given in the public literature, for example, the NGG upper bound and the Bayev lower bound, etc. This paper gives the exact value of the algebraic immunity of Tr(λx ^-1) over \({F_{{2^n}}}\), that is, \(AI\left( {Tr\left( {\lambda {x^{ - 1}}} \right)} \right) = \left\lceil {2\sqrt n } \right\rceil - 2\), where n ≥ 2, λ ∈ \({F_{{2^n}}}\) and λ ≠ 0, which shows that Dalai’s conjecture on the algebraic immunity of Tr(λx ^-1) is correct. What is more, the authors demonstrate some weak properties of Tr(λx ^-1) against fast algebraic attacks.