Enumerating Boolean functions of cryptographic significance

In this paper we describe applications of functions from GF(2) ^m onto GF(2) ⁿ in the design of encryption algorithms. If such a function is to be useful it must satisfy a set of criteria, the actual definition of which depends on the type of encryption technique involved. This in turn means that it is important to ensure that the selected criteria do not restrict the choice of function too severely, i.e., the set of functions must be enumerated. We discuss some of the possible sets of criteria and then give partial results on the corresponding enumeration problems. Many open problems remain, some of them corresponding to well-known hard enumeration questions.     

Further enumerating boolean functions of cryptographic significance

Open problems about enumerating Boolean functions of cryptographic significance are (partially) solved in this paper.Project supported by Trans-Century Training Programme Foundation for the Talents by the State Education Commission.     

几类密码函数的线性结构研究

线性结构是度量密码函数安全性的一个重要指标。本文基于线性分组码理论，分析了文献[1～4]所构造的密码函数的线性结构，并指出这些函数均具有线性结构，且其线性结构集和构造这些函数所运用的线性分组码的对偶码有关。这就说明了文献[1～4]的密码函数本质上是密码学意义下的弱函数。     

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.     

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

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

密码学中布尔函数的零化子

布尔函数的零化子与代数攻击息息相关,但是如何构造一个给定函数的低次零化子仍然是一个悬而未决的问题.本文对此问题进行了研究,研究结果表明,如果布尔函数的零点集有一个k维子空间,那么,函数就会有代数次数为n-k的零化子.然而如何找到函数的具有最低代数次数的零化子仍然是一个亟待解决的难题.     

The structured design of cryptographically good s-boxes

We describe a design procedure for the s-boxes of private key cryptosystems constructed as substitution-permutation networks (DES-like cryptosystems). Our procedure is proven to construct s-boxes which are bijective, are highly nonlinear, possess the strict avalanche criterion, and have output bits which act (vitually) independently when any single input bit is complemented. Furthermore, our procedure is very efficient: we have generated approximately 60 such 4 × 4 s-boxes in a few seconds of CPU time on a SUN workstation.This work was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

Z_q~n上函数的非线性度研究

本文对Z_q~n上函数的非线性度进行了研究,证明了函数非线性度的一些性质     

多输出plateaued函数的性质和构造

该文用仿射变换、级联、单射集及m序列的状态转移矩阵等方法构造了多输出plateaued函数,并明确了构造中阶数的变换情况,给出了由上述方法所构造的多输出plateaued函数的广义一阶Walsh循环谱值.另外,还给出了单射集的构造方法.由此,可以构造出一系列不同阶数、新的多输出plateaued函数.     

γ-型线性结构函数的性质

本文讨论了r型线性结构函数的谱特征,证明了具有r型线性结构函数的有关性质,给出了两个判别r型线性结构的充要条件。     

Constructions of vector output Boolean functions with high generalized nonlinearity

Carlet et al. recently introduced generalized nonlinearity to measure the ability to resist the improved correlation attack of a vector output Boolean function. This article presents a construction of vector output Boolean fimctions with high generalized nonlinearity using the e-biased sample space. The relation between the resilient order and generalized nonlinearity is also discussed.     

两类Plateaued函数的Walsh谱值分布

Based on the properties of trace functions and quadratic forms, this paper presents value distributions of Walsh spectrum of the Plateaued functions of the form Tr(R(x)) with n=3r or 4r variables, where r > 1 is an odd integer. Our results can be used to determine the numbers of non-zero Walsh spectrum values and the nonlinearities of these functions, and estimate their resiliency orders. Especially, the value distributions can be used to deduce the tight lower bounds of the second order nonlinearity of two classes of Boolean functions. It is demonstrated that our bounds are better than the previously obtained bounds.     

旋转对称布尔函数线性结构的2个公开问题

证明了代数次数为 的偶变元平衡旋转对称布尔函数不存在非零线性结构这个公开问题,给出了代数次数为 的奇变元旋转对称布尔函数不存在非零线性结构这个公开问题成立的充分条件和不成立的必要条件。     

k-阶旋转对称函数性质分析与轨道计数

研究了k-阶旋转对称函数的性质,证明了k-阶旋转对称函数的Walsh谱和自相关函数都满足k-阶的旋转对称。分析发现k-阶旋转对称函数的很多性质都可以利用其轨道来刻画,并给出了k-阶旋转对称函数的轨道中的长圈和短圈的计数公式。     

相关免疫布尔函数的计数

本文给出一种关于相关免疫布尔函数的计数方法，并由此给出了一些小重量的相关免疫布尔函数的确切计数公式。本文还根据Rao不等式分析了高阶相关免疫函数计数的性质，并得到了对于高阶相关免疫函数存在的一个关于重量的必要条件，证明了文献【1】中提出的一个猜想是正确的。     

全局雪崩准则的刻画及函数构造

从研究全局雪崩准则的表达方式出发,提出了全局雪崩准则的矩阵刻画方法,为研究全局雪崩准则提供了新的工具。根据全局雪崩准则平方和指标的性质,提出了一种改造M-M型函数的奇数元几乎最优函数,其满足多个密码学性质,具有较小的平方和指标。构造全局雪崩准则性质优良的密码函数是当前研究的一个难点,利用构造新的映射的方法来改造M-M型函数是一种行之有效的办法。     

素数元旋转对称弹性布尔函数的构造与计数

通过对素数元旋转对称弹性布尔函数特征矩阵的研究,给出了其特征矩阵的若干性质,得到了素数元旋转对称布尔函数为弹性函数的一个充要条件,由此完全决定了旋转对称弹性函数的构造以及这类函数的精确计数公式,最后还给出了所有的三元、五元、七元旋转对称弹性布尔函数的构造方案与精确计数。     

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.