**On Algebraic Immunity of $\Tr(x^{-1})$ over $\mathbb{F}_{2^n}**

*Xiutao Feng*

**Abstract: **The trace inverse function $\Tr(x^{-1})$ over the finite field $\mathbb{F}_{2^n}$ is a class of very important Boolean functions in stream ciphers, which possesses many good properties,
including high algebraic degree, high nonlinearity, ideal autocorrelation, etc. In this work we discuss properties of $\Tr(x^{-1})$ in resistance to (fast) algebraic attacks.
As a result, we prove that the algebraic immunity of $\Tr(x^{-1})$ arrives the upper bound
given by Y. Nawaz et al when $n\ge4$, that is, $\AI(\Tr(x^{-1}))=\ceil{2\sqrt{n}}-2$, which shows that D.K. Dalai' conjecture on the algebraic immunity
of $\Tr(x^{-1})$ is correct for almost all positive integers $n$. What is more, we further demonstrate some weak properties of $\Tr(x^{-1})$ in resistance to fast algebraic attacks.

**Category / Keywords: **trace inverse function, algebraic immunity, fast algebraic attacks

**Date: **received 11 Sep 2013, last revised 11 Sep 2013

**Contact author: **fengxt at amss ac cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20130914:030230 (All versions of this report)

**Short URL: **ia.cr/2013/585

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]