Further properties of several classes of Boolean functions with optimum algebraic immunity

详细信息    查看全文

• 作者：Claude Carlet ; Xiangyong Zeng ; Chunlei Li and Lei Hu
• 关键词：Boolean function ; Algebraic immunity ; Nonlinearity ; Balancedness ; Krawtchouk polynomial
• 刊名：Designs, Codes and Cryptography
• 出版年：2009
• 出版时间：September, 2009
• 年：2009
• 卷：52
• 期：3
• 页码：303-338
• 全文大小：397.2 KB

文摘

Based on a method proposed by the first author, several classes of balanced Boolean functions with optimum algebraic immunity are constructed, and they have nonlinearities significantly larger than the previously best known nonlinearity of functions with optimal algebraic immunity. By choosing suitable parameters, the constructed n-variable functions have nonlinearity 2n-1-((n-1) || (\fracn2-1))+2((n-2) || (\fracn2-2))/(n-2){2^{n-1}-{n-1\choose\frac{n}{2}-1}+2{n-2\choose\frac{n}{2}-2}\Big/(n-2)} for even n 3 8 and 2n-1-((n-1) || (\fracn-12))+D(n){n\geq 8\,{\rm and}\,2^{n-1}-{n-1\choose\frac{n-1}{2}}+\Delta(n)} for odd n, where Δ(n) is a function increasing rapidly with n. The algebraic degrees of some constructed functions are also discussed.