一类Bent函数的二阶非线性度下界

为了防止存在有效的低次函数逼近,对于较小的正整数r,用于对称密码系统中的布尔函数应具有较高的r-阶非线性度.当r>1时,准确计算布尔函数的r-阶非线性度十分困难,已有的研究工作主要是通过分析其导函数的(r-1)-阶非线性度来确定布尔函数的r-阶非线性度下界.对于整数n≡2(mod 4),文中确定了一类由Niho指数生成的Bent函数的二阶非线性度下界.与相同变元个数的两类Bent函数和三类布尔函数相比,这类Bent函数具有更紧的二阶非线性度下界.     

向量值函数的代数免疫度与非线性度

本文讨论了向量值函数代数免疫度的定义,给出了向量值函数的代数免疫度与其非线性度之间的关系,研究了布尔函数的重量与其代数免疫度之间的关系,利用该关系,给出了达到最大代数免疫度的平衡布尔函数个数的一个下界。     

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

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

多输出Plateaued函数的构造方法

Plateaued函数具有很高的非线性度,可以满足相关免疫性、平衡性,在密码函数领域具有重要作用。为此,基于Carlet等提出的单输出Plateaued函数构造方法(FSE’03会议论文集),利用m序列的状态转移矩阵,构造一类多输出Plateaued函数,并参考Johansson方法中的引理5(IEEE Transactions on Information Theory, 2003, No.2),提出另一种多输出Plateaued函数的构造方法,由此得到的2种函数适用于S盒、滤波(组合)函数、杂凑函数等的设计。     

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

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

具有高代数免疫阶的弹性布尔函数构造

提出一种二阶级联构造方法,通过选择恰当的参数s,使每次级联增加2个变元的同时代数免疫阶增加1、代数次数增加1。该方法在保持布尔函数弹性的同时能有效提高非线性度。在此基础上设计一类非线性度高于已知构造方法的代数免疫最优布尔函数以及一类非线性度好且满足一阶弹性的代数免疫至少次优的布尔函数,并利用二阶级联迭代构造密码学性质好的布尔函数。     

布尔函数线路复杂度的一个新的下界

布尔函数的线路复杂下界问题与Ｐ＝？ＮＰ问题有密切关系，若证明了ＮＰ中某问题的线路复杂度是非多项式的，则Ｐ≠ＮＰ。但证明了一个具体的布尔函数具有非线性的线路复杂度下界却是计算复杂性理论中最难的问题之一。迄今此问题的最好结果是由Ｎ．Ｂｌｕｍ于１８９４年给出的，他证明了一个布尔函数具有３ｎ－３的线路复杂度下界。本文针对同一个布尔函数，给出一个更好的下界３ｎ＋１。     

基于plateaued函数的平衡布尔函数构造

布尔函数在对称密码的设计和分析中起着重要的作用。通过对谱不相交函数集中子函数平衡性的问题的研究给出了包含4个plateaued函数的函数集中有3个为平衡函数的充分条件。在此基础上,基于3个平衡的谱不相交plateaued函数,一类特殊的布尔置换以及一个高非线性度平衡函数,提出了一个构造高非线性度平衡布尔函数的方法。通过分析可知,利用该方法可以构造代数次数达到最优、非线性度不小于2^2k-1-2^k-1-2^k/2-2^{⌈(k-1)/2⌉}的2k元平衡函数。     

前提不匹配的模糊时滞系统镇定条件的改进

本文研究了前提不匹配的Tagaki-Sugeno(T–S)模糊时滞系统的镇定问题.与一般的T–S模糊时滞系统相比,该系统中模糊模型与模糊控制器拥有不同的模糊规则数与不同的隶属度函数.基于Lyapunov稳定性理论,通过引进新型积分不等式,给出了包含隶属度函数信息的镇定条件.本文提出的新方法充分考虑了隶属度函数的信息,同时得到了Lyapunov函数导数的最小下界,因此新的镇定条件比以往结果具有更小的保守性.另一方面给出前提不匹配的控制器设计方法,由于模糊控制器的隶属度函数可以任意选取,因此提高了控制器设计的灵活性.最后仿真实例证明了本文方法的有效性及优越性.     

S盒抗DPA能力与非线性度的关系

S盒作为高级加密标准(AES)中的唯一非线性部件,是影响算法性能的重要因素之一,在研究其性质的基础上,将透明阶作为衡量密码系统抗差分功耗分析(DPA)能力的一个指标,推导出高非线性函数透明阶的下界计算公式。实验结果表明,该算法是有效的,在类似AES的分组密码中,S盒非线性度与密码抗DPA能力成反比关系。     

三类布尔函数的相关函数研究

布尔函数的相关函数能刻画其扩散特征和线性结构特征,所以研究相关函数的性质对于布尔函数理论具有重要作用。为此,根据自相关和互相关函数的定义,分析通过迹表示的二次布尔函数f(x)=Tr_1~n(x~(2~i+1)+x(2~′+1))的自相关函数值,给出互相关函数平方的一个表达式C_(f,g)~2(α)=(?)(-1)~(D_(f,g)(a)+D_(f,g)(a+ω)),利用该表达式给出任意三次布尔函数的自相关函数平方和的上界,并借助该上界进一步研究两类迹表示的三次布尔函数的绝对值指标上界问题。     

Identification of Wiener systems with nonlinearity being piecewise-linear function

Identification of the Wiener system with the nonlinear block being a piecewiselinear function is considered in the paper, generalizing the results given by H. E. Chen to the case of noisy observation. Recursive algorithms are given for estimating all unknown parameters contained in the system, and their strong consistency is proved. The estimation method is similar to that used by H. E. Chen for Hammerstein systems with the same nonlinearity. However, the assumption imposed by H. E. Chen on the availability of an upper bound for the nonsmooth points of the piecewise-linear function has been removed in this paper with the help of designing an additional algorithm for estimating the upper bound.     

A lower bound on the mod 6 degree of the OR function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z _m . In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}ⁿ, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n ^{1/ r} ) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power. received 29 September 1994     

Connections among nonlinearity,avalanche and correlation immunity

Nonlinear Boolean functions play an important role in the design of block ciphers, stream ciphers and one-way hash functions. Over the years researchers have identified a number of indicators that forecast nonlinear properties of these functions. Studying the relationships among these indicators has been an area that has received extensive research. The focus of this paper is on the interplay of three notable nonlinear indicators, namely nonlinearity, avalanche and correlation immunity. We establish, for the first time, an explicit and simple lower bound on the nonlinearity N_f of a Boolean function f of n variables satisfying the avalanche criterion of degree p, namely, N_f⩾2ⁿ⁻¹−2^{n−1−(1/2)p}. We also identify all the functions whose nonlinearity attains the lower bound. As a further contribution of this paper, we prove that except for very few cases, the sum of the degree of avalanche and the order of correlation immunity of a Boolean function of n variables is at most n−2. The new results obtained in this work further highlight the significance of the fact that while avalanche property is in harmony with nonlinearity, both go against correlation immunity.     

基于毗连的几乎最优弹性布尔函数的构造

近年来,几乎最优弹性布尔函数的研究应用快速发展,提高几乎最优函数的非线性度有着重要的意义。针对一种性能较好的几乎最优函数进行分析和改进,结合毗连的构造方法,来构造偶数元几乎最优函数。在保持其弹性和代数次数的前提下,得到非线性度更高的几乎最优函数,使其性能得到一定提高,并给出了一种构造高非线性度弹性布尔函数的构造方法。分析表明,所提出的方案构造方法简单,容易实现,非线性度得到进一步提高,具有m阶弹性,且代数次数保持不变。     

循环程序的界函数合成

作为循环程序终止性分析的主流方法,当前的秩函数方法大多局限于线性或多项式秩函数的求解.针对循环程序若不存在对应的线性或多项式秩函数,现有秩函数方法就无法证明其终止性的问题,提出一个新的方法来合成给定循环程序对应的界函数.对于给定的循环程序,倘若能找到其界函数,则表明该循环程序是可终止的.首先将界函数的求解问题转化为一个...     

Optimization of signal-to-noise-plus-distortion ratio for dynamic-range-limited nonlinearities

Many components used in signal processing and communication applications, such as power amplifiers and analog-to-digital converters, are nonlinear and have a finite dynamic-range. The nonlinearity associated with these devices distorts the input, which can degrade the overall system performance. Signal-to-noise-plus-distortion ratio (SNDR) is a common metric to quantify the performance degradation. One way to mitigate nonlinear distortions is by maximizing the SNDR. In this paper, we analyze how to maximize the SNDR of the nonlinearities in optical wireless communication (OWC) systems. Specifically, we answer the question of how to optimally predistort a double-sided memory-less nonlinearity that has both a “turn-on” value and a maximum “saturation” value. We show that the SNDR-maximizing response given the constraints is a double-sided limiter with a certain linear gain and a certain bias value. Both the gain and the bias are functions of the probability density function (PDF) of the input signal and the noise power. We also find a lower bound of the nonlinear system capacity, which is given by the SNDR and an upper bound determined by dynamic signal-to-noise ratio (DSNR). An application of the results herein is to design predistortion linearization of nonlinear devices like light emitting diodes (LEDs).