概率方法在布尔函数相关免疫性研究中的应用

本文揭示了布尔函数的Ｗａｌｓｈ谱及“相关度”的概率实质，证明了Ｗａｌｓｈ谱的两条重要性质，正确地揭示了多维布尔向量函数的相关免疫性与其各分量的相关免疫性之间的关系；定义了布尔向量函数的Ｗａｌｓｈ变换及Ｗａｌｓｈ谱，并由此给出了与Ｘｉａｏ－Ｍａｓｓｅｙ定理相应的判别条件。     

广义部分Bent函数和广义Bent函数的关系

Bent函数是一类特殊的布尔函数,因其非线性性和稳定性在密码学和通信等领域有很重要的应用,但它们数量少,不平衡且无相关免疫性,为了弥补Bent函数的不足,Claud Carlet提出了部分Bent函数的概念,部分Bent函数是包含Bent函数的更大的函数类,后来,人们又将这两种函数概念先后都拓广到了环zm^n(m为正整数）上,分别被称为zm^n上的广义Bent函数和广义部分Bent函数,本文利用zp^n(p为素数）上广义部分Bent函数的Chrestenson循环谱特征讨论了zp^n上的广义部分Bent函数和广义Bent函数之间的关系,给出了这两种函数之间的函数关系式和谱值关系式。     

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

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

布尔函数的代数免疫性与设计准则

本文讨论了布尔函数的重量与代数免疫性之间的关系,给出了判断布尔函数是否有低次零化子的一个充分条件,并对由几类传统的构造方法所获得的布尔函数的代数免疫性进行了分析.     

布尔“复合函数”的Walsh循环谱和自相关函数

本文利用布尔随机变量联合分布的分解式给出了布尔“复合函数”和某布尔函数符合率的分解算式,由此求得了布尔“复合函数”的 Walsh循环谱和自相关函数的计算公式,公式清楚地表明了“复合”所得布尔函数的 Walsh循环谱与起“复合”作用的函数和被“复合”的各函数所有线性组合的 Walsh循环谱之间的关系、“复合”所得布尔函数的自相关函数与起“复合”作用的函数谱和被“复合”的各函数的谱及相关函数之间的关系,这两个公式在布尔函数的密码学性质研究中会有广泛的应用.     

相关免疫函数阶的判别方法

在密码学中,为了抵抗相关攻击,要求选用的布尔函数具有相关免疫性,高阶的相关免疫函数都是一阶的,一阶的却不一定是高阶的,本文给出了二种判断一阶相关免疫函数是否为二阶或更高阶的新方法.     

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

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

组间平衡区组设计的性质及应用

区组设计的平衡性是对区组设计研究的重要概念,而组间平衡是其中基于重复次数概念的一种平衡性.探讨了组间平衡性的相关哲学概念和数学性质,并且从理论上证明了组间平衡区组设计的数学判定条件,并给出了计算机验证组间平衡性的方法.作为应用,在一般象数学的试验设计模型的基础上,证明了具有组间平衡性质的广义正交表,不但使得试验因子效应的估计无偏和方差最小,而且可以使得对试验中心值或者总体均值的估计无偏和方差最小,并且在区组试验数据较大时,其估计和区组大小的分解式基本无关,保证试验的数据分析结论具有再现性.     

完全组内平衡区组设计的性质及应用

本文研究了完全组内平衡性的相关哲学概念和数学性质.利用多边矩阵理论,证明了完全组内平衡区组设计的数学判定条件,给出了计算机验证完全组内平衡性的方法,推广了正交表的平衡性质.     

平衡规划问题的熵函数方法及其在混合交通流中的应用

将参变极值问题的极大熵函数方法应用到求解平衡规划问题中,通过先验分布信息和Kullback熵概念,给出了平衡规划问题基于Kullback熵表示的熵函数求解方法,并将平衡规划的极大熵函数方法应用于求解混合交通平衡分配问题．     

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.     

Covering Sequences of Boolean Functions and Their Cryptographic Significance

We introduce the notion of covering sequence of a Boolean function, related to the derivatives of the function. We give complete characterizations of balancedness, correlation immunity and resiliency of Boolean functions by means of their covering sequences. By considering particular covering sequences, we define subclasses of (correlation-immune) resilient functions. We derive upper bounds on their algebraic degrees and on their nonlinearities. We give constructions of resilient functions belonging to these classes. We show that they achieve the best known trade-off between order of resiliency, nonlinearity and algebraic degree.     

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.     

The core of a cooperative game without side payments

For cooperative games without side payments, there are several types of conditions which guarantee nonemptiness of the core, for example balancedness and convexity. In the present paper, a general condition for nonempty core is introduced which includes the known ones as special cases. Moreover, it is shown that every game with nonempty core satisfies this condition.     

Properties of balanced and perfect matrices

In this paper we define wheel matrices and characterize some properties of matrices that are perfect but not balanced. A consequence of our results is that if a matrixA is perfect then we can construct a polynomial number of submatricesA _I,,A _n ofA such thatA is balanced if and only if all the submatricesA ₁,,A _n ofA are perfect. This implies that if the problem of testing perfection is polynomially solvable, then so is the problem of testing balancedness.Partial support under NSF Grants DMS-8606188, ECS-8800281 and DDM-8800281.     

Balancedness conditions for exact games

We provide two new characterizations of exact games. First, a game is exact if and only if it is exactly balanced; and second, a game is exact if and only if it is totally balanced and overbalanced. The condition of exact balancedness is identical to the one of balancedness, except that one of the balancing weights may be negative, while for overbalancedness one of the balancing weights is required to be non-positive and no weight is put on the grand coalition. Exact balancedness and overbalancedness are both easy to formulate conditions with a natural game-theoretic interpretation and are shown to be useful in applications. Using exact balancedness we show that exact games are convex for the grand coalition and we provide an alternative proof that the classes of convex and totally exact games coincide. We provide an example of a game that is totally balanced and convex for the grand coalition, but not exact. Finally we relate classes of balanced, totally balanced, convex for the grand coalition, exact, totally exact, and convex games to one another.     

Local unimodularity of matrix-vector pairs

The main theorem establishes a close relationship between the seemingly separate concepts of balancedness and total unimodularity of {0,1} matrices. The result involves classes of Eulerian matrices, and it is presented using terms “local unimodularity” and “local total unimodularity” recently proposed by Hoffman and Oppenheim.     

Balancedness of Sequencing Games with Multiple Parallel Machines

We provide simple constructive proofs of balancedness of classes of m-PS (m-Parallel Sequencing) games, which arise from sequencing situations with m parallel machines. This includes the setting that is studied by Calleja et al. (2001) and Calleja et al. (2002), who provided a complex constructive proof and a simple non-constructive proof of balancedness of a restricted class of 2-PS games, respectively. Furthermore, we provide a counterexample to illustrate that our balancedness results cannot be extended to a general setting.     

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.     

Totally balanced combinatorial optimization games

Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty for every induced subgame of it.?We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, and minimum coloring games. Received: November 5, 1998 / Accepted: September 8, 1999?Published online February 23, 2000