Paper 2013/585

On Algebraic Immunity of Trace Inverse Functions over Finite Fields with Characteristic Two

Xiutao Feng and Guang Gong

Abstract

The trace inverse function $\Tr(\lambda x^{-1})$ over the finite field $\mathbb{F}_{2^n}$ is a class of very important Boolean functions and has be used in many stream ciphers, for example, SFINKS, RAKAPOSHI, the simple counter stream cipher presented by W. Si and C.S. Ding, etc. In order to evaluate the security of those algorithms in assistance to (fast) algebraic attacks, it is essential to algebraic properties of $\Tr(\lambda x^{-1})$. However, currently only some bounds on algebraic immunity of $\Tr(\lambda x^{-1})$ are given in public literature. In this work we give the exact value of $\Tr(\lambda x^{-1})$ over finite fields $\mathbb{F}_{2^n}$, that is, $\AI(\Tr(\lambda x^{-1}))=\floor{\sqrt{n}}+\ceil{\frac{n}{\floor{\sqrt{n}}}}-2=\ceil{2\sqrt{n}}-2$, where $n\ge2$, $\lambda\in \mathbb{F}_{2^n}$ and $\lambda\ne0$, which is just the upper bound given by Y. Nawaz et al. And at the same time our result shows that D.K. Dalai' conjecture on the algebraic immunity of $\Tr(\lambda x^{-1})$ is correct. What is more, we further demonstrate some weak properties of $\Tr(\lambda x^{-1})$ in resistance to fast algebraic attacks.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
boolean functionsalgebraic immunity
Contact author(s)
fengxt @ amss ac cn
History
2014-10-10: revised
2013-09-14: received
See all versions
Short URL
https://ia.cr/2013/585
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/585,
      author = {Xiutao Feng and Guang Gong},
      title = {On Algebraic Immunity of Trace Inverse Functions over Finite Fields with Characteristic Two},
      howpublished = {Cryptology ePrint Archive, Paper 2013/585},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/585}},
      url = {https://eprint.iacr.org/2013/585}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.