Abstract: The algebraic immunity is a criteria on evaluating the property of the Boolean function recently. This paper studies the relation of the nonlinearity and algebraic immunity of the functions having odd weight and gives the lower bound of the nonlinearity when the algebraic is given, further shows that this bound is tight. The weight distribution has a range when the algebraic immunity is given, i.e. d, and shows that the range is also tight, that is for any integer in that range, there exists a Boolean function that its weight is t and the algebraic immunity is greater than d.

Key words: Boolean function, algebraic immunity, nonlinearity

摘要： _{代数免疫度是近几年提出的一个衡量布尔函数密码学性质的标准。该文研究重量为奇数的布尔函数的代数免疫度和非线性度之间的关系，得到了代数免疫度固定时非线性度的下界，而且证明这个下界是紧的。代数免疫度大于d时，函数的重量有一个范围，证明了这个范围是紧的，即对任何这个范围内的整数t，都存在一个布尔函数其重量为t，代数免疫度大于d。}

关键词: 布尔函数, 代数免疫度, 非线性度

CLC Number: 

• TP309