三元组布尔置换的构造

布尔置换和bent函数在密码学中起着非常重要的作用。在Coulter和Mesnager所提出的三元组布尔置换广义构造方法（该三元组布尔置换可以用来构造bent函数）的基础上，给出了一个等价的构造三元组布尔置换的具体方法。利用此具体方法，提供了一个构造三元组布尔置换的算法。对三个置换之间的依赖关系做了进一步研究，提出了一个三元组置换成立的充要条件，并给出了一个构造三元组布尔置换的新算法。分析了利用三元组布尔置换所得bent函数的性质。     

P值逻辑函数的扩散性质

满足K次扩散准则的p值逻辑函数在密码设计中有重要应用。该文采用Znp上的置换定出了一类满足2n次扩散准则的p值逻辑函数,即Bent函数;定出了级联函数满足K次扩散准则的充要条件和n元2次p值逻辑函数满足m阶K次扩散准则的充要条件。     

On cross-correlation properties of Boolean functions

The relationship among cross-correlation of arbitrary four Boolean functions is presented. Several known cross-correlation properties of Boolean functions are generalized. Based on them, a lower bound for the maximal cross-correlation (in absolute value) of two Boolean functions (if one of the functions is bent) is obtained.     

Cross-Correlation Analysis of Cryptographically Useful Boolean Functions and S-Boxes

We use the cross-correlation function as a fundamental tool to study cryptographic properties of Boolean functions. This provides a unified treatment of a large section of Boolean function literature. In the process we generalize old results and obtain new characterizations of cryptographic properties. In particular, new characterizations of bent functions and functions satisfying propagation characteristics are obtained in terms of the cross-correlation and auto-correlation properties of subfunctions. The exact relationship between the algebraic structure of the non-zeros of the spectrum and the auto-correlation values is obtained for a cryptographically important class of functions. Finally we study the suitability of S-boxes in stream ciphers and conclude that currently known constructions for S-boxes may not be adequate for such applications. Received April 27, 2001, and in revised form October 30, 2001. Online publication February 20, 2002.     

On affine (non)equivalence of Boolean functions

In this paper we construct a multiset S(f) of a Boolean function f consisting of the weights of the second derivatives of the function f with respect to all distinct two-dimensional subspaces of the domain. We refer to S(f) as the second derivative spectrum of f. The frequency distribution of the weights of these second derivatives is referred to as the weight distribution of the second derivative spectrum. It is demonstrated in this paper that this weight distribution can be used to distinguish affine nonequivalent Boolean functions. Given a Boolean function f on n variables we present an efficient algorithm having O(n2²ⁿ ) time complexity to compute S(f). Using this weight distribution we show that all the 6-variable affine nonequivalent bents can be distinguished. We study the subclass of partial-spreads type bent functions known as PS _ap type bents. Six different weight distributions are obtained from the set of PS _ap bents on 8-variables. Using the second derivative spectrum we show that there exist 6 and 8 variable bent functions which are not affine equivalent to rotation symmetric bent functions. Lastly we prove that no non-quadratic Kasami bent function is affine equivalent to Maiorana–MacFarland type bent functions.     

一种密码函数存在性证明的新方法

密码函数在密码学中具有重要的研究价值.从组合的角度,给出了一种密码函数不存在性证明的新方法,并且得到了一些新结果,部分结果优于已有结论,这些结果可以部分证明不存在次数大于2的齐次旋转对称bent函数这一公开猜想.同时,利用多项式的最大公因子算法刻画了2次齐次旋转对称bent函数.该方法也可以用于刻画其他形式的bent函...     

关于涂-邓猜想的一点注记

为多种密码学构造性质良好的布尔函数一直是对称密码学研究中的一个难点问题。最近,涂自然和邓映蒲 基于一个二元组合猜想的正确性,构造了两类具有最优代数免疫度的布尔函数,其中第一类函数是具有最优代数免疫 度的13cnt函数,另一类是平衡且具有最优代数免疫度的高非线性度函数。涂一邓猜想引起了国内外密码学者的高度 关注。现通过分析涂一邓猜想中参数t满足二tC}>=3情形时的二元Hamming重量的特性,给出涂一邓猜想在二tCt}=3 情形下的证明,并以推论的形式推出二t相似文献   

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.     

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.     

最高非线性度旋转对称布尔函数与最优代数免疫函数

研究了旋转对称布尔函数的最高扩散次数、最高非线性度、代数免疫性和最优代数免疫函数的存在性与构造等问题。利用导数和e-导数证明了非线性度达到最高的旋转对称布尔函数的存在性,并利用导数,由扩散性达到最高n次的Bent函数来验证一类旋转对称Bent函数的存在性。同时证明了1阶代数免疫和2阶以上代数免疫旋转对称布尔函数的存在性。另外,利用旋转对称Bent函数构造了非齐次完全旋转对称最优代数免疫布尔函数以及一类众多的最优代数免疫布尔函数,并证明了这两类函数的存在性。同时,也得到了非齐次完全旋转对称相关免疫布尔函数。     

New constructions of balanced Boolean functions with high nonlinearity and optimal algebraic degree

In this paper, we propose a technique for constructing balanced Boolean functions on even numbers of variables. The main technique is to utilize a set of disjoint spectra functions and a special Boolean permutation to derive a balanced Boolean function with high nonlinearity and optimal algebraic degree. It is shown that the functions we construct are different from both Maiorana-McFarland's (M-M) super-class functions introduced by Carlet and modified M-M super-class functions presented by Zeng and Hu. Furthermore, we show that they have no nonzero linear structures.     

结合广义重心坐标与Voronoi 剖分的函数分片逼近

结合广义重心坐标理论,提出了一个新方法,以解决在平面区域上的函数逼近问题。 该方法通过构建基于广义重心坐标的最优分片函数来逼近目标函数。采用Voronoi 图来划分区域, 并提出一个度量逼近误差的能量函数。推导出该函数的导数后,采用一种高效的Voronoi 节点更 新方法来获得区域的最优剖分,并通过最优剖分构建最优分片函数。由于该方法对不连续函数具 有良好地逼近能力,因此将其应用在图像逼近问题中。分别在解析函数和彩色图像上对该方法进 行实验,均获得了很好的逼近效果。     

Maiorana-McFarland’s Bent函数零化子空间维数

在流密码和分组密码的设计中,所用布尔函数应该具有好的密码学性质来抵抗已知的各种有效攻击.布尔函数的低次零化子空间维数与其补函数低次零化子空间维数之和是评价该函数抵抗代数攻击能力的一个重要参数.根据Maiorana-McFarlands(M-M)Bent函数和布尔置换之间的一一对应关系,给出了一组布尔函数组并证明了它们是线性无关的.借助所给的线性无关布尔函数组和布尔置换中向量函数非零线性组合均是平衡函数的特性,给出了一类特殊M-M Bent函数低次零化子空间的维数与其补函数低次零化子空间的维数之和的一个上限.就这类特殊M-M Bent函数而言,该上限低于已知的限.进一步给出了适合所有M-M Bent函数的新上限.     

New construction of highly nonlinear resilient S-boxes via linear codes

Highly nonlinear resilient functions play a crucial role in nonlinear combiners which are usual hardware oriented stream ciphers. During the past three decades, the main idea of construction of highly nonlinear resilient functions are benefited from concatenating a large number of affine subfunctions. However, these resilient functions as core component of ciphers usually suffered from the guess and determine attack or algebraic attack since the n-variable nonlinear Boolean functions can be easily given rise to partial linear relations by fixing at most n/2 variables of them. How to design highly nonlinear resilient functions (S-boxes) without concatenating a large number of n/2 variables affine subfunctions appears to be an important task. In this article, a new construction of highly nonlinear resilient functions is proposed. These functions consist of two classes subfunctions. More specially, the first class (nonlinear part) contains both the bent functions with 2 k variables and some affine subfunctions with n/2 − k variables which are attained by using [ n/2 − k, m, d] disjoint linear codes. The second class (linear part) includes some linear subfunctions with n/2 variables which are attained by using [ n/2, m, d] disjoint linear codes. It is illustrated that these resilient functions have high nonlinearity and high algebraic degree. In particular, It is different from previous well-known resilient S-boxes, these new S-boxes cannot be directly decomposed into some affine subfunctions with n/2 variables by fixing at most n/2 variables. It means that the S-boxes (vectorial Boolean functions) which use these resilient functions as component functions have more favourable cryptography properties against the guess and determine attack or algebraic attacks.     

参数曲线近似弧长参数化的插值方法

本文提出了参数曲线近似弧长参数化的一种插值方法。参数曲线的弧长函数的单调增的，近似弧长参数化可以转化为弧长函数的保单调分段有理线性插值。用这种插值得到的近似弧长参数化曲线插值原曲线上的一组点，最后，两个实例表明了近似弧长参数化曲线能很好地逼近原曲线，且没有所不希望的波动。     

An effective parallel approach for genetic-fuzzy data mining

Data mining is most commonly used in attempts to induce association rules from transaction data. In the past, we used the fuzzy and GA concepts to discover both useful fuzzy association rules and suitable membership functions from quantitative values. The evaluation for fitness values was, however, quite time-consuming. Due to dramatic increases in available computing power and concomitant decreases in computing costs over the last decade, learning or mining by applying parallel processing techniques has become a feasible way to overcome the slow-learning problem. In this paper, we thus propose a parallel genetic-fuzzy mining algorithm based on the master–slave architecture to extract both association rules and membership functions from quantitative transactions. The master processor uses a single population as a simple genetic algorithm does, and distributes the tasks of fitness evaluation to slave processors. The evolutionary processes, such as crossover, mutation and production are performed by the master processor. It is very natural and efficient to run the proposed algorithm on the master–slave architecture. The time complexities for both sequential and parallel genetic-fuzzy mining algorithms have also been analyzed, with results showing the good effect of the proposed one. When the number of generations is large, the speed-up can be nearly linear. The experimental results also show this point. Applying the master–slave parallel architecture to speed up the genetic-fuzzy data mining algorithm is thus a feasible way to overcome the low-speed fitness evaluation problem of the original algorithm.     

混合核函数中权重求解方法

为了克服支持向量机(SVM)中单核函数的局限性,经常使用混合核函数做预测,但混合核函数中各函数权重难以确定。为解决该问题,提出了一种基于特征距离的权重求解方法。该方法首先利用支持向量机的几何意义,根据同类样本特征距离最小化和异类样本特征距离最大化原理,分析得出优化函数,然后对优化函数求解得出权重系数。实验结果表明,与传统的交叉验证法和PSO算法相比,该方法在保证预测精度的情况下,将计算时间减少了70%左右。