The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity

The rth order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. This paper tightens the lower bounds of the second order nonlinearity of three classes of Boolean functions in the form f(x)=tr(x^d) in n variables, where (1) d=2^m+1+3 and n=2m, or (2) , n=2m and m is odd, or (3) d=2^2r+2^r+1+1 and n=4r.     

On lower bounds of second-order nonlinearities of cubic bent functions constructed by concatenating Gold functions

We consider the problem of identifying the classes of Boolean functions having high second-order nonlinearities. In this paper, we demonstrate that the cubic bent functions obtained by Leander and McGuire (J. Combin. Theory Ser. A, 116 (2009), pp. 960–970), which are concatenations of the quadratic Gold functions, possess high second-order nonlinearities.     

具有线性结构的弹性函数非线性度的新上界

讨论了具有线性结构的弹性函数的两个指标:沃什谱和非线性度,得到了具有线性结构的布尔函数的一些性质.利用沃尔什变换和汉明重量的方法,发现了:如果V是n元布尔函数,f(x)的线性结构,那么得到f(x)的沃尔什变换在为零这一事实,同时得到了一个布尔函数没有k(k≥0)维线性结构的充分条件.最后,利用以上结果推出了具有线性结构的弹性函数的非线性度的上界表达式.     

一类三次Bent函数的二阶非线性度*

研究了形如yTr(x5)+Tr(x3)的三次Bent函数,通过研究其导数的非线性度的下界,得到了该函数的二阶非线性度的下界,将所得结果与Carlet的结果进行了比较,结果表明,该函数的二阶非线性度大于Carlet给出的下界。     

一类特殊布尔函数的代数免疫度研究

构造具有好的代数免疫度的布尔函数是布尔函数研究的重要问题之一。基于布尔函数的级联构造方法,给出了一类具有好的代数免疫度的布尔函数;分析了所构造函数的性质,证明了构造布尔函数hn+1与其子函数代数免疫度之间的关系,并确定了已构造一阶级联函数的代数次数、平衡性以及非线性度。研究结果表明,在级联构造方法下,i次级联构造函数比一阶构造H0的代数免疫度有显著提高。     

On the lower bounds of the second order nonlinearities of some Boolean functions

The rth order nonlinearity of a Boolean function is an important cryptographic criterion in analyzing the security of stream as well as block ciphers. It is also important in coding theory as it is related to the covering radius of the Reed-Muller code R(r,n). In this paper we deduce the lower bounds of the second order nonlinearities of the following two types of Boolean functions:

1.

with d=2^2r+2^r+1 and , where n=6r.

2.

, where x,y∈F_2^t,n=2t,n?6 and i is an integer such that 1?i<t,gcd(2^t-1,2ⁱ+1)=1.

For some λ, the functions of the first type are bent functions, whereas Boolean functions of the second type are all bent functions, i.e., they possess the maximum first order nonlinearity. It is demonstrated that in some cases our bounds are better than the previously obtained bounds.     

爬山算法对一阶相关免疫函数非线性度的优化研究

在布尔函数的设计中,总是希望得到满足多个密码特性的密码函数,但是这些密码特性之间存在着一定的制约关系。利用爬山算法对一阶相关免疫函数进行了优化,得到了大量高非线性度的布尔函数并通过MATLAB 实验对八元、九元一阶相关免疫函数进行了优化。实验结果表明,该算法可进一步优化相关免疫函数的非线性度。     

基于T-D猜想上MAI函数的构造

对涂自然等人提出的组合猜想上的构造方法及有关结论进行了改良推广,在假设更一般的组合猜想成立的前提下构造了一种具有最优代数免疫度的偶数元布尔函数f,同时还利用f构造了一种具有最优代数免疫度的平衡的偶数元布尔函数F。且这些函数也具有很高的代数次数和非线性度,对代数攻击具有较强的抵抗能力。     

New upper bounds on the Boolean circuit complexity of symmetric functions

In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5n+o(n) for any symmetric function of n variables, as well as circuits of size 3n for function.     

Constructions of balanced Boolean functions with high nonlinearity and high algebraic degree

Three of the most essential criteria for cryptographically strong Boolean functions are balancedness, high nonlinearity and high algebraic degree. In this paper, we give two methods for constructing balanced Boolean functions with high nonlinearity via modifying Maiorana–McFarland type bent functions. The algebraic immunity of the constructed functions is also considered.     

相关免疫函数的一个新下界

主要讨论相关免疫函数的构造与计数问题,改善了温巧燕等人提出的2阶相关免疫函数以及m阶相关免疫函数的下界。     

2-分解H布尔函数和高非线性度布尔函数

以布尔函数的导数和自定义的e-导数为主要研究工具,研究满足一次扩散准则、可2-分解为两个子函数乘积的一类H布尔函数的非线性度、相关免疫性和代数免疫性等密码学性质。得到了这类H布尔函数的相关免疫阶与两个子函数的关系,以及这类H布尔函数的相关免疫阶可达到 n2 －1的结论。还得到了利用两个子函数使布尔函数的非线性度易于求解的方法,以及这类H布尔函数的最低代数次数零化子与两个子函数的关系。进一步地,在这类H布尔函数上述特点的基础上,利用导数和e-导数构造出了非线性度提高到2n－2+2n－3、具有相关免疫性和2阶代数免疫性的一族H布尔函数。由此,解决了提高布尔函数的非线性度问题,以及同时具有较高非线性度、扩散性、相关免疫性和较高阶代数免疫性的布尔函数的存在性问题。     

On the global avalanche characteristics between two Boolean functions and the higher order nonlinearity

The criterion for the global avalanche characteristics (GAC) of cryptographic functions is an important property. To measure the correlation between two arbitrary Boolean functions, we propose two new criteria called the sum-of-squares indicator and the absolute indicator of the cross-correlation between two Boolean functions. The two indicators generalize the GAC criterion. Based on the properties of the cross-correlation function, we deduce the rough lower and the rough upper bounds on the two indicators by hamming weights of two Boolean functions, and generalize some properties between the Walsh spectrum and the cross-correlation function. Furthermore, we give the tight upper and the tight lower bounds on the two indicators. Finally, we show some relationships between the upper bounds on the two indicators and the higher order nonlinearity.     

Linear control of nonlinear systems based on nonlinearity measures

In reality, virtually every process is a nonlinear system. Nevertheless, linear controller design methods have proved to be adequate in many applications. In practice, the linear controller design is usually done disregarding a possible nonlinear plant/linear model mismatch. In this work we introduce a general framework for the development of linear controllers for nonlinear systems based on nonlinearity measures. Nonlinearity measures are tools to assess the extent of a system’s inherent nonlinearity instead of just recognizing a system as being linear or nonlinear. Recent work shows that nonlinearity measures characterize the magnitude of the modeling error when an optimal linear model is used for the nonlinear system. The best linear model can then be used to design a linear controller that robustly stabilizes the linear system in presence of the nonlinear modeling error. A crucial point is that both, the best linear model and the modeling error, are determined for a specified region of operation, thus significantly increasing the class of applicable nonlinear systems. Examples demonstrate the (necessity and) effectiveness of the proposed approach.     

Effect of process nonlinearity on linear quadratic regulator performance

In this paper, a new local measure of nonlinearity is introduced to quantify the sensitivity of controller performance for linear controllers operating on a nonlinear plant. The measure, called the performance sensitivity measure, quantifies the departures from optimality of locally linear quadratic regulators. A root mean squared measure, the RMSPSM, is proposed to summarize average nonlinearity effects over a region of interest. The measure applies to nonlinear systems that admit a controllable and observable linearization.     

一种快速的布尔函数极小化方法

基于偏序集及多维体理论，文中提出了Ｌ－集概念，并将布尔函数极小化问题抽象为Ｌ－集的极大内多维体。还设计了一个基于Ｌ－集的图搜索的快速布尔函数极小化算法，使可解输入变量数达到２６个。     

从布尔代数到布尔微积分

布尔函数作为最简单的有限值函数具有特殊的重要性．它在包括信息、控制等许多领域有着广泛的应用．本文综合介绍有关布尔函数的理论基础．包括从布尔代数到布尔微积分的主要理论结果,它们在信息与控制中的一些重要应用,以及其前沿动态与新进展．介绍的一个重点是矩阵半张量积在这些领域的应用．     

Construction of high degree resilient S-boxes with improved nonlinearity

We present a simple method to use an [n−d−1,m,t+1] code to construct an n-input, m-output, t-resilient function with degree d>m and nonlinearity ²n−1−²n−⌈(d+1)/2⌉−(m+1)²n−d−1. For any fixed values of parameters n,m,t and d, with d>m, the nonlinearity obtained by our construction is higher than the nonlinearity obtained by Cheon in Crypto 2001.