Spectral characterisation of ternary threshold functions

In this communication, the question of characterising a ternary threshold function by a few coefficients of its series expansion in terms of Chrestenson functions is examined. It is shown that an n-place ternary threshold function may be uniquely characterised by (n+2) coefficients; (n+1) of them correspond to particular elements of the Chrestenson spectrum of the function and the n+2nd is the summation over all magnitude-squared spectral elements.     

Characterisation of threshold functions under the Walsh transform and linear translation

Some new results showing the classification of Boolean functions of order n, n ? 5, under the Rademacher?Walsh transform, together with the operation of spectral translation, are examined. It is found that there are 48 prototype functions, of which 21 are threshold functions. Examination of the canonic spectral forms of these threshold functions shows that a threshold function may be identified uniquely for n ? 5, under a sum-of-squares criterion.     

Universal threshold gates for 3-, 4- and 5-variable linearly separable (threshold) functions

The number of different possible linearly separable Boolean functions of n variables is given by the permutations of the n+1 Chow parameters. For n = 3, 4 and 5, single universal-gate design specifications are disclosed, which will realise all such possible linearly separable functions. It is suggested that practical factors preclude the building of universal functions for n > 5.     

H布尔函数的相关免疫性与重量的关系

将布尔函数的导数和与导数一起便可直接明确刻画布尔函数的重量而定义的e-导数一起作研究工具,深入到布尔函数取值的内部结构中去,讨论了在H布尔函数存在的一个大重量范围内,所有不同重量的H布尔函数的一阶、任意m阶相关免疫函数存在与否的问题。对存在m阶相关免疫性的H布尔函数,它的相关免疫阶数m与维数n的具体关系,以及m的最大值问题。给出了m阶相关免疫H布尔函数只存在于2种重量的H布尔函数中,其相关免疫阶数m的最大值为n-2,以及其余重量的H布尔函数中不存在二阶以上(包括二阶)相关免疫函数等一系列结果。同时,也给出了一些判断布尔函数相关免疫性的方法。     

Some results on the algebraic immunity of Boolean functions

From the motivation of algebraic attacks on stream and block ciphers,the concept of algebraic immunity(AI) of a Boolean function was introduced and studied extensively.High algebraic immunity is a necessary condition for resisting algebraic attacks.In this paper,we give some lower bounds on the algebraic immunity of Boolean functions.The results are applied to give lower bounds on the AI of symmetric Boolean functions and rotation symmetric Boolean functions.Some balanced rotation symmetric Boolean functions with their AI near the maximum possible value「n/2」are constructed.     

均衡弹性函数的结构与弹性阶

弹性函数是相关免疫布尔函数的自然推广。本文讨论均衡弹性函数,得到以下结果:给出了均衡弹性函数的一种结构,并因此得到了由均衡(n,m,2t)弹性函数构造均衡(n+1,m,2t+1)弹性函数的非线性方法;证明了均衡线性函数的弹性阶等于对应线性分组码的码字最小重最减1,且弹性阶上确界常常能由非线性函数所达到。     

Tr（...）的二阶非线性度下界

作为影响系统安全的重要因素,对称密码中的密码函数应具有较高的r阶非线性度。对于r>1,目前对r阶非线性度的研究主要根据布尔函数微商的非线性度与其二阶非线性度之间的关系来进行。对于正整数n≡2（mod 4）,确定了一类布尔函数Tr(x^{2n/2+2n/2-1+1})的二阶非线性度下界。与相同变元数的两类已知布尔函数相比,研究的函数具有更紧的二阶非线性度下界。     

布尔函数的代数厚度

基于布尔函数的代数次数和代数厚度,给出了布尔函数和其分解函数的代数厚度的关系,利用递归和反证法导出了n元布尔函数代数厚度的上界是2* *(n-1),这个上界回答了"是否存在代数厚度大于2* *(n-1)的n元布尔函数"这个公开问题.在此基础上改进了n元k(2≤k≤(n-1)/2)次基本对称布尔函数的代数厚度的上界,同时也得到了布尔函数的代数厚度的一些性质.     

基于阈值逻辑的逻辑函数综合算法研究

阈值逻辑门由于具有强大的逻辑功能且独自构成完备集而备受关注。为了设计以阈值逻辑门为单元结构的电路,该文首先分析了谱技术与阈值函数的关系,并通过零次、一次谱系数计算阈值函数的权值和阈值。对于非阈值函数,该文提出了新的逻辑函数综合算法,可以将任意非阈值函数转化为几个阈值函数和的形式。因此,使用一个或多个阈值逻辑门组成的网络可以实现任意布尔逻辑函数。该算法为共振隧穿二极管的电路设计提供一种新方法。     

一种计算旋转对称布尔函数的汉明重量和非线性度的新方法

旋转对称布尔函数是一类重要的密码学函数,研究其重量和非线性度等密码学性质具有很好的理论价值。区别于已有的计算方法,该文利用特定的正规基把这些布尔函数的问题转化为有限域上的指数和问题,得到了4 ?? n和n=2s 时一些二次旋转对称布尔函数的重量和非线性度的新结果。使用所提的方法,可以计算几乎全部的二次旋转对称布尔函数的重量和非线性度。所提的新方法对于研究一般的旋转对称布尔函数具有一定的参考意义。     

一类密码函数的构造与分析

利用t+1个n元布尔函数(称为基函数)级联构造了一类n+t元布尔函数G(x,y),并给出了G(x,y)的Walsh循环谱和自相关系数。通过Krawtchouk多项式与Krawtchouk矩阵对G(x,y)和基函数的关系进行了研究。分析了G(x,y)的密码学性质:相关免疫性、扩散性和代数免疫性。特别地,当t=2时,分析了G(x,y)与基函数的具体关系。另外,一般化该构造方法构造了一类多输出布尔函数,给出了该类多输出布尔函数的广义Walsh循环谱,进而分析了该类多输出布尔函数的相关免疫性和代数免疫性。     

对称逻辑公式在经典逻辑度量空间中的分布

将密码学中对称布尔函数的概念引入到计量逻辑学理论之中,定义了对称逻辑公式和准对称逻辑公式.指出二值逻辑公式与布尔函数既密切相关,又有重要区别.证明了n元对称公式占全体n元逻辑公式的比例随n的增大而趋向于零,然而全体对称公式的真度之集却在[0,1]中稠密.最后从拓扑学的观点证明了全体对称公式之集在经典逻辑度量空间中无处稠...     

布尔函数的扩展代数免疫度

该文研究了布尔函数的扩展代数免疫度,首先给出了布尔函数的扩展代数免疫度与其代数免疫度相等的一个充分必要条件;然后讨论了两类具有最大代数免疫度的布尔函数的扩展代数免疫度,给出了其扩展代数免疫度也达到最大值的充分必要条件;最后基于代数补元素的思想,给出了布尔函数零化子结构的一种新刻画。     

Algorithm for identifying skew symmetries through Walsh transform

An algorithm for the identification of skew equivalent and skew non-equivalent symmetries in Boolean functions through Walsh spectral coefficients is presented. Experimental results on a large number of functions show that the approach is very efficient     

Generalized Bent Criteria for Boolean Functions (I)

Generalizations of the bent property of a Boolean function are presented, by proposing spectral analysis with respect to a well-chosen set of local unitary transforms. Quadratic Boolean functions are related to simple graphs and it is shown that the orbit generated by successive local complementations on a graph can be found within the transform spectra under investigation. The flat spectra of a quadratic Boolean function are related to modified versions of its associated adjacency matrix     

Expansion of Walsh Functions in Terms of Shifted Rademacher Functions and Its Applications to the Signal Processing and the Radiation of Electromagnetic Walsh Waves

The expressions for Walsh functions in terms of shifted Rademacher functions are applicable to the design of a directive and selective array antenna for Walsh waves which is capable of eliminating the interference caused by impulsive noises. They also are applicable to voice processing because of their shift-invariant property. The shifted Rademacher functions were previously introduced by shiftiAg horizontally the periodic Rademacher functions. It was shown that the Walsh functions could be expressed as a linear combination of a finite number of the shifted Rademacher functions. This paper develops the actual expansions of the Walsh functions in terms of the shifted Rademacher functions. The coefficients in this series take only the values of either + 1 or -1. The shifted Rademacher coefficients appearing in the expansion of a given function in tenns of shifted Rademacher functions have the advantage that the coefficients of a shifted function are available by shifting cyclically the original coefficients.     

一次扩散布尔函数的一些密码学性质

通过将导数和自定义的e-导数结合,作为新的研究工具引入到布尔函数密码学性质研究中来。利用导数和e-导数可将布尔函数内部取值不同特点进行区分的特性,系统地证明了不同重量一次扩散布尔函数相关免疫最高阶数问题,得出了一些用传统研究工具,如频谱理论等,不易导出的布尔函数密码学性质。这一结果对提高密码系统抵抗相关攻击的能力,提供了理论依据。     

Maximum nonlinearity of symmetric Boolean functions on odd number of variables

In this correspondence, we establish that for odd n, the maximum nonlinearity achievable by an n-variable symmetric Boolean function is 2/sup n-1/-2/sup (n-1)///sup 2/ and characterize the set of functions which achieve this value of nonlinearity. In particular, we show that for each odd n/spl ges/3, there are exactly four possible symmetric Boolean functions achieving the nonlinearity 2/sup n-1/-2/sup (n-1)/2/.     

满足扩散准则的元素之集的性质

设f(x)是V_n上的布尔函数,本文研究了f(x)的满足扩散准则的元素集合R^c_f的性质.证明了,若degf(x)=n,则R^c_f为空集.对于所有的二次布尔函数而言,均有R^c_f中的元素个数大于等于2^n-1.还对一类函数的雪崩性质进行了讨论.给出布尔函数不含有非零线性结构的充分必要条件是ζ_f中含有n个线性无关的元素,其中ζ_f={(α_i|〈ζ,l_i〉≠0,0≤i≤2ⁿ-1},l_i为线性函数φ_αi=〈x,α_i〉的序列.还给出了一种2阶扩散准则布尔函数的构造.     

On computing the spectral coefficients of a switching function

The spectral coefficients of a switching function are computed in terms of the real transform of the function, or equivalently, in terms of a disjoint sum-of-products representation of the function. Such a representation can be cast into an almost minimal form through some existing algorithms, and its complexity can be significantly less than that of a minterm expansion, which it includes as a special case. The real transform is also utilized as a mechanism for the inverse transform from the spectral domain to the Boolean domain.