递归构造多个具有最优代数免疫度的平衡布尔函数

代数免疫度是针对代数攻击而提出来的一个新的密码学概念.要能够有效地抵抗代数攻击,密码系统中使用的布尔函数必须具有平衡性、较高的代数次数、较高的非线性度和较高的代数免疫度等.为了提高布尔函数的密码学性能,通过布尔函数仿射等价的方法,找出了所有具有最优代数免疫度的三变元布尔函数.由这些具有最优代数免疫度的三变元非线性布尔函数,递归构造了一类代数免疫度最优、代数次数较高的平衡布尔函数.给出了这类布尔函数非线性度的一个下界,偶数变元时,其下界严格大于Lobanov给出的下界.     

最优布尔函数的一个性质

Walsh谱只有3个值:0,±2m+2,且同时达到代数次数上界n-m-1和非线性度上界2n-1-2m+1的n元m阶弹性布尔函数(m>n/2-2)称为饱和最优函数(saturatedbest简写为SB).本文将给出关于SB函数非零谱值位置分布的一个性质,利用这一性质我们给出构造非线性度为56的4次7兀2阶弹性布尔函数的一种方法.     

具有等变量极值的多元函数

定义.D是n维欧氏室空中一个点集,n≥2,f(x_1,x_2,…,x_n)是定义在D上的一个n元函数。如果f在D上极值存在,并且位于诸变量相等时,那末,称f在D上具有等变量极值。定理. 设f(x_1,x_2,…,x_n)(n≥3)是定义在D上的一个n元函数。如果f(x_1,x_2,…,x_n)在D上具有极大(小)值,且任意固定     

代数免疫度为1的布尔函数

布尔函数的代数免疫度是在流密码的代数攻击中所产生的重要概念.研究了代数免疫度为1的布尔函数,得到的主要结果有:对代数免疫度为1的布尔函数给出了一个谱刻画,给出了其个数的精确计数公式,最后给出了此类函数的非线性度的紧的上界.     

奇可标号图类最优界定函数的相关研究

令G表示一类图.如果存在一个函数f使得对于任意的G∈G都有χ(G)≤f(ω(G)),那么称G是χ-界图类,且称f是G的一个界定(binding)函数.本文研究奇可标号图类最优界定函数相关问题,证明一类无4-洞奇可标号图有线性界定函数.     

两类极易混淆的对称问题

先看这样两道习题: 1.若函数y=f(x)对定义域内任意的自 变量x都有f(x-1)=f(1-x),则该函数的 图像关于直线＿＿对称. 2.(1997年全国高考试题)函数y=f(x -1)与y=f(1-x)的图象关于直线＿＿对 称.(注:原题是一道选择题) 这两道习题涉及到两类对称问题,即一个     

效应代数的表示

本文讨论了抽象效应代数的表示问题. 对于一个抽象效应代数(E,⊕, 0, 1), 如果存在一个Hilbert 空间 H 和一个单态射 φ:E →ε(H), 那么称 E 为可表示的且称(φ,H) 是E 的一个表示, 其中ε(H) 表示 H 上所有正压缩算子构成的效应代数. 给出了一些可表示的和不可表示的效应代数的例子, 证 明了非空集 X 上的任一模糊集系统 F 和Boolean 代数B_X 都是可表示的效应代数.     

一类含绝对值的斜率型不等式的统一求解模式

先看两道试题:1.如果对于函数f(x)的定义域内任意的x1,x2,都有|f(x1)-f(x2)|≤|x1-x2|成立,那么就称函数f(x)是定义域上的"平缓函数".设a,m为实常数,m>0,若f(x)=alnx是[m,∞)上的"平缓函数",试求a的取值范围.     

求三角函数周期的一种方法

在三角函数中,求周期是一个重要内容,也是一个难点。在常见的一些题目中,如求y=|sinx| |cosx|,y=(1-sinx)~(1/2) (1 sinx)~(1/2)的周期等一类,学生做起来总觉得不顺手,掌握比较困难,为了使这类问题易于解决,不妨试用“不变量函数方幂法”。什么叫“不变量函数方幂法”呢? 定义若函数y=f(x)在定义域A上恒非负,或者恒非正,则称函数y=f(x)为A上的不变量函数。定理若函数y=f(x)是定义在A上的不变量函数,且y=f~a(x)也是A上的不变量函数(a为非零有理数),则函数y=f(x)与y=     

求函数极值的图解法

求函数极值问題,已有不少的论述。在代数里,讲过y=ax~2+bx+c的图象以后,求二次函数的最大值和最小值得到了较彻底的解决。本文就在此基础上,借助于求解非线性规划问題的思想,用图形来解答一些常见的具有约束条件的极值问题。这类问题的一般形式是:在约束条件下,要求找出变量x_i(i=1,2,…,n)的值,使得给定的函数 L=f(x_1,x_2,…,x_n) (2)取最大值或最小值。这里gi(x_1,x_2,…,x_n) (i=1,2,…,m)和f(x_1,x_2,…,x_n)都是变量x_1,x_2,…,x_n的有理整函数;“V”表示=,≤,≥中的某一个符号。式(2)称为目标函数。     

Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, based on the knowledge of compositions of an integer, we present two new kinds of construction of rotation symmetric Boolean functions having optimal algebraic immunity on either odd variables or even variables. Our new functions are of much better nonlinearity than all the existing theoretical constructions of rotation symmetric Boolean functions with optimal algebraic immunity. Further, the algebraic degree of our rotation symmetric Boolean functions are also high enough.     

Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n²) time and O(n) space complexity. We use the term “Annihilator Immunity” instead of “Algebraic Immunity” referred in the recent papers [3–5, 9, 18, 19]. Please see Remark 1 for the details of this notational change     

Exact relations between nonlinearity and algebraic immunity

We sharpen some lower bounds on the higher order nonlinearity of a Boolean function in terms of the value of its algebraic immunity and obtain new tight bounds. We prove a universal tight lower bound, which enables us to reduce the problem of estimating higher order nonlinearity to finding the dimension of certain linear subspaces in the space of Boolean functions. As a simple corollary of this result, we obtain all previously known estimates in this area. For polynomials with disjoint terms, finding the dimension of those linear subspaces reduces to a simple combinatorial inspection. We prove a tight lower bound on the second order nonlinearity of a Boolean function in terms of the value of its algebraic immunity.     

On extended algebraic immunity

Algebraic immunity (AI) measures the resistance of a Boolean function f against algebraic attack. Extended algebraic immunity (EAI) extends the concept of algebraic immunity, whose point is that a Boolean function f may be replaced by another Boolean function f ^c called the algebraic complement of f. In this paper, we study the relation between different properties (such as weight, nonlinearity, etc.) of Boolean function f and its algebraic complement f ^c . For example, the relation between annihilator sets of f and f ^c provides a faster way to find their annihilators than previous report. Next, we present a necessary condition for Boolean functions to be of the maximum possible extended algebraic immunity. We also analyze some Boolean functions with maximum possible algebraic immunity constructed by known existing construction methods for their extended algebraic immunity.     

On a method of derivation of lower bounds for the nonlinearity of Boolean functions

The calculation of the exact value of the rth order nonlinearity of a Boolean function (the power of the distance between the function and the set of functions is at most r) or the derivation of a lower bound for it is a complicated problem (especially for r > 1). Lower bounds for nonlinearities of different orders in terms of the value of algebraic immunity were obtained in a number of papers. These estimates turn out to be sufficiently strong if the value of algebraic immunity is maximum or close to maximum. In the present paper, we prove a statement that allows us to obtain fairly strong lower bounds for nonlinearities of different orders and for many functions with low algebraic immunity.     

On the maximal component algebraic immunity of vectorial Boolean functions

Under study is the component algebraic immunity of vectorial Boolean functions. We prove a theorem on the correspondence between the maximal component algebraic immunity of a function and its balancedness. Some relationship is obtained between the maximal component algebraic immunity and matrices of a special form. We construct several functions with maximal component algebraic immunity in case of few variables.     

On the security of the Feng–Liao–Yang Boolean functions with optimal algebraic immunity against fast algebraic attacks

In the past few years, algebraic attacks against stream ciphers with linear feedback function have been significantly improved. As a response to the new attacks, the notion of algebraic immunity of a Boolean function f was introduced, defined as the minimum degree of the annihilators of f and f + 1. An annihilator of f is a nonzero Boolean function g, such that fg = 0. There is an increasing interest in construction of Boolean functions that possess optimal algebraic immunity, combined with other characteristics, like balancedness, high nonlinearity, and high algebraic degree. In this paper, we investigate a recently proposed infinite class of balanced Boolean functions with optimal algebraic immunity, optimum algebraic degree and much better nonlinearity than all the previously introduced classes of Boolean functions with maximal algebraic immunity. More precisely, we study the resistance of the functions against one of the new algebraic attacks, namely the fast algebraic attacks (FAAs). Using the special characteristics of the family members, we introduce an efficient method for the evaluation of their behavior against these attacks. The new algorithm is based on the well studied Berlekamp–Massey algorithm.     

Construction of balanced Boolean functions with high nonlinearity,good local and global avalanche characteristics

Boolean functions possessing multiple cryptographic criteria play an important role in the design of symmetric cryptosystems. The following criteria for cryptographic Boolean functions are often considered: high nonlinearity, balancedness, strict avalanche criterion, and global avalanche characteristics. The trade-off among these criteria is a difficult problem and has attracted many researchers. In this paper, two construction methods are provided to obtain balanced Boolean functions with high nonlinearity. Besides, the constructed functions satisfy strict avalanche criterion and have good global avalanche characteristics property. The algebraic immunity of the constructed functions is also considered.     

A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed–Muller code

Because of the recent algebraic attacks, optimal algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. In this paper, we firstly determine the concrete coefficients in the linear expression of the column vectors with respect to a given basis of the generator matrix of Reed–Muller code, which is an important tool for constructing Boolean functions with optimal algebraic immunity. Secondly, as applications of the determined coefficients, we provide simpler and direct proofs for two known constructions. Further, we construct new Boolean functions on odd variables with optimal algebraic immunity based on the generator matrix of Reed–Muller code. Most notably, the new constructed functions possess the highest nonlinearity among all the constructions based on the generator matrix of Reed–Muller code, although which is not as good as the nonlinearity of Carlet–Feng function. Besides, the ability of the new constructed functions to resist fast algebraic attacks is also checked for the variable \(n=11,13\) and 15.