Cubic Boolean functions with highest resiliency

We classify those cubic m-variable Boolean functions which are (m-4)-resilient. We prove that there are four types of such functions, depending on the structure of the support of their Walsh spectra. We are able to determine, for each type, the Walsh spectrum and, then, the nonlinearity of the corresponding functions. We also give the dimension of their linear space. This dimension equals m-k where k=3 for the first type, k=4 for the second type, k=5 for the third type, and 5/spl les/k/spl les/9 for the fourth type.     

Constructions of rotation symmetric 2-resilient functions with 4t-1 number of variables

Some properties of rotation symmetric orbits were proposed in n dimensional vector space over finite field of characteristic 2,a matrix on the distributions of number pairs such as 00,01 and 11 was defined,and a new characterization of 2-resilient rotation symmetric functions was introduced.Constructions of rotation symmetric 2-resilient Boolean functions with 4t-1 number of variables were presented by modifying the support of the linear rotation symmetric functions,such as f₀(x)=x₁+x₂+…+x_n,where n=4t-1.At last,an example was demonstrated to introduce the spirit of the proposed method to construct 2-resilient rotation symmetric functions with 4t-1 number of variables.     

多输出布尔函数的特征值分析

为了研究自变量是独立而非均匀分布条件下的多输出布尔函数的密码学性质,文章定义了多输出布尔函数的谱值和特征值,给出了多输出函数的特征值的一般表达式和估计式,并且计算出了n阶布尔置换和t-弹性函数特征值的上界.     

Construction and Count of 1-Resilient Rotation Symmetric Boolean Functions on 4p Variables

This paper studies the properties of orbit matrix and gives a formula to compute the number of these orbit matrices on 4p variables, where p is an odd prime. It has been demonstrated that the construction of 1-resilient Rotation symmetric Boolean functions (RSBFs) on 4p variables is equivalent to solving an equation system. By the proposed method, all 1-resilient RSBFs on 12 variables can be constructed. We present a counting formula for the total number of all 1-resilient RSBFs on 4p variables. As application of our method, some 1-resilient RSBFs on 12 variables are presented.     

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/.     

Cryptographic properties of the Welch-Gong transformation sequencegenerators

Welch-Gong (WG) transformation sequences are binary sequences of period 2ⁿ - 1 with two-level autocorrelation. These sequences were discovered by Golomb, Gong, and Gaal (1998) and they verified the validity of their construction for 5 ⩽ n ⩽ 20. Later, No, Chung, and Yun (1998) found another way to construct the WG sequences and verified their result for 5 ⩽ n ⩽ 20. Dillon (1998) first proved this result for odd n, and, finally, Dobbertin and Dillon (1999) proved it for even n. In this paper, we investigate a two-faced property of the WG transformation sequences for application in stream ciphers and pseudorandom number generators. One is to present the randomness or unpredictability of the WG transformation sequences. The other is to exhibit the security properties of the WG transformations regarded as Boolean functions. In particular, we prove that the WG transformation sequences, in addition to the known two-level autocorrelation and three-level cross correlation with m-sequences, have the ideal 2-tuple distribution, and large linear span increasing exponentially with n. Moreover, it can be implemented efficiently. This is the first type of pseudorandom sequences with good correlation, statistic properties, large linear span, and efficient implementation. When WG transformations are regarded as Boolean functions, they have high nonlinearity. We derive a criterion for the Boolean representation of WG transformations to be r-resilient and show that they are at least 1-resilient under some basis of the finite field GF (2ⁿ). An algorithm to find such bases is given. The degree and linear span of WG transformations are presented as well     

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

设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阶扩散准则布尔函数的构造.     

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

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

布尔函数的代数厚度

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

具有最优代数免疫阶的1阶弹性函数的构造

这里研究了两种二阶级联构造的密码学性质,发现对初始函数增加2个变元,构造方法I和Ⅱ都能使代数免疫阶增加1阶,同时分别获得高的非线性度和1阶弹性。通过选择置换s,构造I能迭代产生非线性度高的代数免疫最优的布尔函数。最后利用级联构造I和II给出了一种具有1阶弹性的代数免疫最优布尔函数的构造方法.     

Optimization of fixed-polarity Reed-Muller circuits using dual-polarity property

In the optimization of canonical Reed-Muller (RM) circuits, RM polynomials with different polarities are usually derived directly from Boolean expressions. Time efficiency is thus not fully achieved because the information in finding RM expansion of one polarity is not utilized by others. We show in this paper that two fixed-polarity RM expansions that have the same number of variables and whose polarities are dual can be derived from each other without resorting to Boolean expressions. By repeated operations, RM expansions of all polarities can be derived. We consequently apply the result in conjunction with a hypercube traversal strategy to optimize RM expansions (i.e., to find the best polarity RM expansion). A recursive route is found among all possible polarities to derive RM expansion one by one. Simulation results are given to show that our optimization process, which is simpler, can perform exhaustive search as efficiently as other good exhaustive-search methods in the field.     

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

利用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循环谱,进而分析了该类多输出布尔函数的相关免疫性和代数免疫性。     

Plateaued函数谱支撑集的性质

本文对Plateaued函数的谱支撑集的结构与性质进行了深入研究,给出了r阶Plateaued函数的全体非0谱值点集合与线性结构集的维数之间的关系.利用谱指标对2阶Plateaued函数和4阶Plateaued函数的自相关性进行了详细分析,给出了其自相关系数的分布.分析了r阶Plateaued函数的谱支撑集和零谱值点集的结构特征,给出了多个r阶Plateaued函数的谱支撑集在不相交时自相关系数之间的关系以及谱支撑集与函数平衡性的关系.     

An anisotropic reference matrix for image steganography

A lot of image steganographic techniques (also called data hiding) conceal secret data by utilizing a reference matrix (RM), and some new types of RMs, such as the turtle shell, an octagon-shaped shell, the Sudoku table, and so on, have been proposed in recent years. In this article, we present a novel type of RM called anisotropic RM. By employing a full search strategy, we have found the optimal parameters for constructing the anisotropic RM. To judge the performance of a parameter set quickly, a theoretical peak signal-to-noise ratio (PSNR) evaluation method is proposed. In addition, we extend the RM to three-dimensional (3D) space. Experimental results show that our data hiding scheme, based on the anisotropic RM, has a better quality stego image than previous methods. Moreover, the 3D RM works better than the traditional 2D RM using the same embedding capacity.     

Almost k -Wise Independent Sample Spaces and Their Cryptologic Applications

An almost k -wise independent sample space is a small subset of m bit sequences in which any k bits are ``almost independent'. We show that this idea has close relationships with useful cryptologic notions such as multiple authentication codes (multiple A -codes), almost strongly universal hash families, almost k -resilient functions, almost correlation-immune functions, indistinguishable random variables and k -wise decorrelation bias of block ciphers. We use almost k -wise independent sample spaces to construct new efficient multiple A -codes such that the number of key bits grows linearly as a function of k (where k is the number of messages to be authenticated with a single key). This improves on the construction of Atici and Stinson \cite{AS96}, in which the number of key bits is Ω (k ² ) . We introduce the concepts of ɛ -almost k -resilient functions and almost correlation-immune functions, and give a construction for almost k -resilient functions that has parameters superior to k -resilient functions. We also point out the connection between almost k -wise independent sample spaces and pseudorandom functions that can be distinguished from truly random functions, by a distinguisher limited to k oracle queries, with only a small probability. Vaudenay \cite{Vaudenay99} has shown that such functions can be used to construct block ciphers with a small decorrelation bias. Finally, new bounds (necessary conditions) are derived for almost k -wise independent sample spaces, multiple A -codes and balanced ɛ -almost k -resilient functions. Received September 1999 and revised January 2001 Online publication 29 August 2001     

相关免疫H布尔函数的代数免疫和代数次数

将导数和自定义的e-导数结合在一起作为新的研究工具,而这两者(导数和e-导数)结合在一起能直接明确反映布尔函数的重量,深入到布尔函数取值的内部结构中去,讨论相关免疫H布尔函数的代数免疫阶、代数次数等问题,即严格雪崩性质、相关免疫性、代数免疫性及最高代数次数的相容性问题,得出Hamming重量为2n-1+2n-2这类H布尔函数的最低代数次数和最高代数次数、最优代数免疫等结果。同时,也给出了一些求布尔函数代数次数和最优代数免疫的方法。     

On the construction of odd-variable boolean functions with optimal algebraic immunity

Algebraic immunity is an important cryptographic property of Boolean functions. In this paper, odd-variable balanced Boolean functions with optimal algebraic immunity are obtained by m-sequence and consequently, we get bases with special constructions of vector space. Furthermore, through swapping some vectors of these two bases, we establish all kinds of odd-variable balanced Boolean functions with optimal algebraic immunity.     

Algebraic immunity for cryptographically significant Boolean functions: analysis and construction

Recently, algebraic attacks have received a lot of attention in the cryptographic literature. It has been observed that a Boolean function f used as a cryptographic primitive, and interpreted as a multivariate polynomial over F/sub 2/, should not have low degree multiples obtained by multiplication with low degree nonzero functions. In this paper, we show that a Boolean function having low nonlinearity is (also) weak against algebraic attacks, and we extend this result to higher order nonlinearities. Next, we present enumeration results on linearly independent annihilators. We also study certain classes of highly nonlinear resilient Boolean functions for their algebraic immunity. We identify that functions having low-degree subfunctions are weak in terms of algebraic immunity, and we analyze some existing constructions from this viewpoint. Further, we present a construction method to generate Boolean functions on n variables with highest possible algebraic immunity /spl lceil/n/2/spl rceil/ (this construction, first presented at the 2005 Workshop on Fast Software Encryption (FSE 2005), has been the first one producing such functions). These functions are obtained through a doubly indexed recursive relation. We calculate their Hamming weights and deduce their nonlinearities; we show that they have very high algebraic degrees. We express them as the sums of two functions which can be obtained from simple symmetric functions by a transformation which can be implemented with an algorithm whose complexity is linear in the number of variables. We deduce a very fast way of computing the output to these functions, given their input.     

布尔函数的线性结构的特征

本文首先利用布尔函数的特征集合对布尔函数的线性结构进行了刻划,给出了寻找布尔函数的线性结构的一种方法。其次引入了布尔函数的r型线性结构的概念,并对其进行了研究,同时还指出了布尔函数的r型线性结构的密码学意义。     

基于有效布尔矩阵的线性最近邻量子电路综合?

量子电路要求满足最近邻约束，只允许在相邻的量子位之间交互，线性量子电路是量子电路的一个重要部分。研究了表示线性最近邻量子电路的布尔矩阵有效性的快速判定方法，时间复杂度从n!(n-1)变为O(n2)。提出了基于有效布尔矩阵的大规模线性最近邻量子电路的并行综合算法，对128线的任意线性最近邻量子电路在不到10 s内完成了电路综合。提出的并行方法不仅保证了精度，也大大减少了量子电路的综合时间，扩大了求解电路的规模。