两类三次旋转对称布尔函数的汉明重量和非线性度

旋转对称布尔函数是一类具有良好密码学性质的布尔函数,自被提出来就得到了学者们的广泛关注.本文研究了形如f(x)=∑n-1 i=0 xix1+ixm+1+i和ft(x)=∑n-1 i=0 xixt+ixm+i的两类三次旋转对称布尔函数的汉明重量及非线性度.通过对F_2~n进行分解,可将函数转化为特殊形式,使得求取函数的傅里叶变换变得相对容易.再利用汉明重量及非线性度与傅里叶变换之间的关系,求出了这两类函数的汉明重量和非线性度的计算公式.     

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

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

关于满足SAC的布尔函数

首先讨论了满足ＳＡＣ的布尔函数的性质，然后构作了一类满足ＳＡＣ的布尔函数且讨论了它们的一些密码特性。     

一类非线性弹性函数的构造

In this paper the decomposition formula of Walsh spectrum of boolean functions is used to construct a class of nonlinear resilient functions.     

布尔函数的线性维数与非线性度

本文讨论了布尔函数的线性维数与非线性度的有关性质,证明了布尔函数变元个数,代数次数和线性维数之间的关系,给出了由线性维数计算二次布尔函数非线性度的公式。     

布尔函数Walsh变换的非零取值个数

设Wf(y)(y∈F2^r)是布尔函数f：F2^r→F2的Walsh变换．Sf为Wf(y)≠0的y个数，S为所有Sf的并集(其中f过所有可能的布尔函数)．决定集合S是通信和信息安全领域一个重要问题．本文利用群环工具给出研究这一问题的新方法．用这种方法以统一方式证明了[4]中的结果．并利用群环方法给出了关于集合S的一系列新结果．     

布尔函数的密码性质

当前,密码学面临的一个挑战性问题是构造具有多种密码学性能的布尔函数,用来作为流密码和分组密码的密钥,以同时抵抗现有的多种破译和攻击方式。本文综述了近年来国内外在这方面的研究和进展。     

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

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

一类变系数非线性Schrodinger方程的对称群分类和容许变换

从对称群和容许变换的角度讨论一类变系数非线性Schrodinger方程,给出所考察方程的非平凡点对称群。     

关于对称函数的一类不等式

关于对称函数的一类不等式石焕南（北京联大职业技术师院１０００１１）ｎ个正数ｘｌ，ｘＺ，…，ｘ。的初等对称函数是规定当ｋ＝０时，Ｅｋ（ｘｌ，…，。。）一１；当ｋ＜０或ｋ＞。时，Ｅｋ（。１，…，。。）一０．不难验证本文将证明如下两个定理定＆ＩＲ。；＞０，...     

Asymptotic Nonlinearity of Boolean Functions

Boolean functions on the space are not only important in the theory of error-correcting codes, but also in cryptography. In these two cases, the nonlinearity of these functions is a main concept. Carlet, Olejár and Stanek gave an asymptotic lower bound for the nonlinearity of most of them, and I gave an asymptotic upper bound which was strictly larger. In this article, I improve the bounds and get an exact limit for the nonlinearity of most of Boolean functions. This article is inspired by a paper of G. Halász about the related problem of real polynomials with random coefficients. AMS Classification (2000) Primary: 11T71 · Secondary: 06E30 · 42A05 · 94C10     

Proof of a conjecture about rotation symmetric functions

Rotation symmetric Boolean functions have important applications in the design of cryptographic algorithms. We prove the conjecture about rotation symmetric Boolean functions (RSBFs) of degree 3 proposed in Cusick and St?nic? (2002) [2] and its generalization, thus the nonlinearity of such functions is determined.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Rotation symmetric Boolean functions—Count and cryptographic properties

Rotation symmetric (RotS) Boolean functions have been used as components of different cryptosystems. This class of Boolean functions are invariant under circular translation of indices. Using Burnside's lemma it can be seen that the number of n-variable rotation symmetric Boolean functions is 2^g_n, where g_n=(1/n)∑_t|nφ(t)2^n/t, and φ(.) is the Euler phi-function. In this paper, we find the number of short and long cycles of elements in having fixed weight, under the RotS action. As a consequence we obtain the number of homogeneous RotS functions having algebraic degree w. Our results make the search space of RotS functions much reduced and we successfully analyzed important cryptographic properties of such functions by executing computer programs. We study RotS bent functions up to 10 variables and observe (experimentally) that there is no homogeneous rotation symmetric bent function having degree >2. Further, we studied the RotS functions on 5,6,7 variables by computer search for correlation immunity and propagation characteristics and found some functions with very good cryptographic properties which were not known earlier.     

Nonlinearity of Some Invariant Boolean Functions

One of the hardest problems in coding theory is to evaluate the covering radius of first order Reed–Muller codes RM(1,m), and more recently the balanced covering radius for crypto graphical purposes. The aim of this paper is to present some new results on this subject. We mainly study boolean functions invariant under the action of some finite groups, following the idea of Patterson and Wiedemann [The covering radius of the (1, 15) Reed-Muller Code is atleast 16276. IEEE Trans Inform Theory. Vol. 29 (1983) 354.]. Our method is Fourier transforms and our results are both theoretical and numerical.     

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.     

An Upper Bound on the Number of Iterations for Transforming a Boolean Function of Degree Greater or Equal Than 4 to a Function of Degree 3

The difficulty involved in characterizing the weight distribution of all Boolean functions of degree 3 is well-known [2, p. 446]. In [1] the author introduces a transformation on Boolean functions which changes their weights in a way that is easy to follow, and which, when iterated, reduces the degree of the function to 2 or 3. He concludes that it is just as difficult to characterize the weight of any function of degree 3 as it is for any other degree. The application of this transformation on a Boolean function defined on , increases the number of its variables by two. On the other hand, in order to reduce the degree of a function to 2 or 3 it is necessary to apply the tranformation a number of times that grows exponentially with respect to m. In this paper, a factorization method on Boolean functions that allows the establishment of an upper bound for the number of applications of the transformation is presented. It shows that, in general, it is possible to significantly decrease the number of iterations in this process of degree reduction.     

Variable orderings and the size of OBDDs for random partially symmetric Boolean functions

The size of ordered binary decision diagrams (OBDDs) strongly depends on the chosen variable ordering. It is an obvious heuristic to use symmetric variable orderings, i.e., variable orderings where symmetric variables are arranged adjacently. In order to evaluate this heuristic, methods for estimating the OBDD size for random partially symmetric functions are presented. Characterizations of cases where, with high probability, only symmetric variable orderings and, with high probability, only nonsymmetric variable orderings lead to minimum OBDD size are obtained. For this analysis estimates for the number of different blocks of random Boolean matrices are used. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 49–70, 1998     

The Fourier Transform of Functions Satisfying the Lipschitz Condition on Rank 1 Symmetric Spaces

We prove an analog of the classical Titchmarsh theorem on the image under the Fourier transform of a set of functions satisfying the Lipschitz condition in L² for functions on noncompact rank 1 Riemannian symmetric spaces.     

Several classes of even-variable 1-resilient rotation symmetric Boolean functions with high algebraic degree and nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, some classes of 2m-variable (m is an odd integer) 1-resilient rotation symmetric Boolean functions are got, whose nonlinearity and algebraic degree are studied. For the first time, we obtain 2m-variable 1-resilient rotation symmetric Boolean functions having high nonlinearity and optimal algebraic degree. In addition, we obtain a class of non-linear rotation symmetric 1-resilient function for every $n\ge 5$, and a class of quadratic rotation symmetric $(k?1)$-resilient function of $n=3k$ variables, where k is an integer.