In this paper, it is proven that a family of $2k$-variable Boolean functions, including the function recently constructed by Tang et al. [IEEE TIT 59(1): 653--664, 2013], are almost perfect algebraic immune for any integer $k\geq 3$. More exactly, they achieve optimal algebraic immunity and almost perfect immunity to fast algebraic attacks. The functions of such family are balanced and have optimal algebraic degree. A lower bound on their nonlinearity is obtained based on the work of Tang et al., which is better than that of Carlet-Feng function. It is also checked for $3\leq k\leq 9$ that the exact nonlinearity of such functions is very good, which is slightly smaller than that of Carlet-Feng function, and some functions of this family even have a slightly larger nonlinearity than Tang et al.'s function. To sum up, among the known functions with provable good immunity against fast algebraic attacks, the functions of this family make a trade-off between the exact value and the lower bound of nonlinearity.
Category / Keywords: Stream ciphers, Boolean functions Date: received 29 Aug 2012, last revised 14 Jan 2014 Contact author: meicheng liu at gmail com Available format(s): PDF | BibTeX Citation Version: 20140114:081738 (All versions of this report) Short URL: ia.cr/2012/498 Discussion forum: Show discussion | Start new discussion