Constructing Higher Nonlinear Odd-Variable RSBFs With Optimal AI and Almost Optimal FAI

Yindong Chen, Limin Lin, Lumin Liao, Jie Ruan, Fei Guo, Weihong CaiIEEE Access 2019 · OpenReview

Abstract

Rotation symmetric Boolean functions (RSBFs) are nowadays studied a lot because of its easy operations and good performance in cryptosystem. This paper constructs a new class of odd-variable RSBFs with optimal algebraic immunity (AI). The nonlinearity of the new function, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{n-1}-\binom {n-1}{k}+2^{k-4}(k-3)(k-2)$ </tex-math></inline-formula> , is the highest among all existing RSBFs with optimal AI and known nonlinearity, and its algebraic degree is also almost highest. Besides, the class of functions have almost optimal fast algebraic immunity (FAI) at least for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n &lt; 17$ </tex-math></inline-formula> , which is actually the highest possible value for the designated number of variables.
BibTeX
@inproceedings{chen2019constructing,
  author = {Yindong Chen and Limin Lin and Lumin Liao and Jie Ruan and Fei Guo and Weihong Cai},
  title = {{Constructing Higher Nonlinear Odd-Variable RSBFs With Optimal AI and Almost Optimal FAI}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=in1U_LWZ0XA},
}

Loading related content...

Figure