布尔函数非线性度的谱分析

任何一个密码系统都可以用一个非线性函数来描述。本文利用频谱技术研究了布尔函数的非线性度,以及布尔函数的某些运算对非线性度的影响,并指出这些结果在密码学中的应用。     

bent函数和半bent函数的二阶非线性度下界

该文研究了形如f(x,y)的n+1变元bent函数和半bent函数的二阶非线性度,其中xGF(2n), yGF(2)。首先给出了f(x,y)的2n-1个导数非线性度的精确值;然后推导出了函数f(x,y)的其余2n个导数的非线性度紧下界。进而给出了f(x,y)的二阶非线性度的紧下界。通过比较可知所得下界要优于现有的一般结论。结果表明f(x,y)具有较高的二阶非线性度,可以抵抗二次函数逼近和仿射逼近攻击。     

两类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.     

On Separable Boolean Functions

A necessary and sufficient condition for a Boolean function to be separable is presented. Several results towards a better understanding the characteristic properties of separable Boolean functions are derived. Some properties of separable plateaued functions are given.     

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.     

布尔函数的自相关原点矩

本文给出布尔函数的自相关原点矩这一概念，讨论布尔函数密码学特征在自相关原点矩上的数值表现，得到了平衡布尔函数、仿射函数、Bent函数以及部分Bent函数的自相关原点矩的数值特征。     

流密码中非线性组合函数的分析与设计

从互信息的观点出发，本文研究了非线性组合函数与其部分变量的组合之间的相关性，探讨了这种相关性对流密码安全性的影响。利用Ｗａｌｓｈ变换，分析了Ｂｅｎｔ函数与其部分变量之间的相关性，给出了一类与Ｂｅｎｔ函数有相同渐近谱特性的布尔函数的结构。     

布尔函数若干设计准则的研究

本文在简要介绍密码应用中布尔函数应满足的一些设计准则及其各自构造方法的基础上,分析了这些设计准则的作用及相互关系,提出了同时满足几个最重要设计准则的较实用的构造方法,并给出了相应的例子。     

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

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

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.     

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

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

两类极小二元线性码的构造

线性码在数据存储、信息安全以及秘密共享等领域具有重要的作用。而极小线性码是设计秘密共享方案的首选码,设计极小线性码是当前密码与编码研究的重要内容之一。该文首先选取恰当的布尔函数,研究了函数的Walsh谱值分布,并利用布尔函数的Walsh谱值分布构造了两类极小线性码,确定了码的参数及重量分布。结果表明,所构造的码是不满足Ashikhmin-Barg条件的极小线性码,可用作设计具有良好访问结构的秘密共享方案。     

相关免疫布尔函数的计数

本文首次求出了重量为4(或2n-4)和6(或2n-6)的n元相关免疫布尔函数的精确个数。同时还用递归算法改进了现有的下界公式。     

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

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

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.     

Complexity Bounds on General Hard-Core Predicates

A Boolean function b is a hard-core predicate for a one-way function f if b is polynomial-time computable but b(x) is difficult to predict from f(x) . A general family of hard-core predicates is a family of functions containing a hard-core predicate for any one-way function. A seminal result of Goldreich and Levin asserts that the family of parity functions is a general family of hard-core predicates. We show that no general family of hard-core predicates can consist of functions with O(n ^1-ε ) average sensitivity, for any ε > 0 . As a result, such families cannot consist of • functions in AC ⁰ , • monotone functions, • functions computed by generalized threshold gates, or • symmetric d -threshold functions, for d = O(n ^{1/2 - ε} ) and ε > 0 . Received April 2000 and revised September 2000 Online publication 9 April 2001     

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

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

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.