Bent函数构造方法研究

Bent函数的概念由Rothaus在1976年提出.因为Bent函数既是非线性度最优的布尔函数,又达到了一阶Reed-Muller码的覆盖半径,并且与Hadamard矩阵、差集等组合对象有紧密联系,所以其应用涉及密码、编码、组合数学等多个领域.对Bent函数的研究一直是热门方向,其中包含了大量的关于Bent函数构造的结果.除了布尔Bent函数,在不同的应用背景下还定义了Bent函数的各类推广形式,比如:广义Bent函数、p值Bent函数、向量Bent函数、超Bent函数等.本文对Bent函数的构造方法做一个系统的综述,介绍Bent函数及其各类推广形式的构造,包括广义Bent函数、p值Bent函数、向量Bent函数和超Bent函数.在每一部分的介绍中,着重介绍最具有代表形式的Bent函数,如Maiorana-Mc Farland类、PS(Partial Spread)类、二次型以及一些特殊的指数形式.

一类多输出Bent函数的构造

推广了半Bent函数的概念,提出了多输出半Bent函数的概念,并由此给出了多输出Bent函数的一种构造方法.该方法通过级联两个多输出半Bent函数得到多输出Bent函数.与原有的方法相比,该方法具有结构简单、使用方便的优点.用此方法可构造具有任意偶数个变元的多输出Bent函数.此外,还给出了多输出半Bent函数的一种构造方法.除了可用于构造多输出Bent函数外,多输出半Bent函数还可应用于多输出前馈网等方面.

WDC算法与6元Bent函数计数

一般情况下,在布尔函数的研究中,给定一部分地址处Walsh谱值的集合A={(λ_(i),a_(i))|λ_(i)∈F_(2)^(n),a_(i)∈Z,i=0,1,2,…,m-1},寻找满足在这些地址具有给定谱值的所有n元布尔函数是很困难的。但是如果给定的地址集合是一个向量子空间,则有简单的求解方法。文章给出一种WDC算法,求解具有子空间结构地址的Walsh谱值的所有n元布尔函数以及个数。该算法包括3方面的内容:①如何构造满足这些条件的n元布尔函数;②满足这些条件的n元布尔函数有多少个?③子空间地址上的谱值满足什么条件时,才能保证满足这些条件的n元布尔函数存在。另外,Bent函数是非线性度最高的布尔函数,具有非常好的密码学性质。文章利用WDC算法并借助计算机搜索,求解出所有的6元Bent函数,共有5425430528个。

关于部分Bent函数

首先从广义部分Bent函数的定义出发,利用线性变换的若干理论,证明Galois域上广义部分Bent函数等价于广义Bent函数与仿射函数之和。该结论覆盖了文献[1]的主要结果。然后给出关于部分Bent函数的类似结论,改进了Claud Carlet的关于部分Bent函数的结论。作为新结论的具体应用,最后修正了参考文献中的两个结论。

k阶拟Bent函数在密码设计和通信中的应用

王育民、何大可提出了布尔函数关于线性函数的r阶相关度E(r)的概念来刻划布尔函数抵抗相关攻击的能力,本文以极小化所有非零相关度E(r)为主要目的,利用k阶拟Bent函数的特殊性质,给出了一类基于k阶拟Bent函数的“最佳”非线性组合设计的实现,构造了一类平衡的,具有高阶相关免疫性,而且非零相关度一致地小的非退化的布尔函数,并比较了它与基于部分Bent函数的“最佳”非线性组合设计的优劣。最后我们又利用k阶拟Bent函数构造了一类Bent互补函数族和Bent侣,Bent互补函数族和Bent侣在最佳信号设计方面意义重大,这也表明k阶拟Bent函数在密码设计和通信领域都有比较广的应用前景。

一类多输出半Bent函数的构造及其密码学性质

给出了多输出半Bent函数的一种构造方法.该方法通过级联两个低阶多输出Bent函数得到高阶多输出半Bent函数.由于在多输出Bent函数的构造方面,目前已有许多较好的结果,因此新方法是一个非常有效的方法,能构造出大量的多输出半Bent函数.还进一步讨论了这类函数的平衡性、非线性性、稳定性及扩散性等密码学性质.这些性质显示,多输出半Bent函数是一类密码学性质良好的奇数元多输出函数,除了可应用于多输出前馈网,它还可用作分组密码体制的非线性组合器.

多维超Bent函数的构造

有限域Fp2m上的超Bent函数是与Fp上所有m序列的距离都达到最大的函数,该文研究了22mF上超Bent函数与GF2m(2)上Bent函数之间的关系,对一类超Bent函数的性质作了深入细致的刻画,给出了有限域Fp2m上多维超Bent函数的两种构造方法.

代数次数为3的6元3维Bent函数的结构分析

Rothaus在其文章《OnBentFunctions》中指出代数次数为3的6元Bent函数只有3个等价类.本文则推导出代数次数为3的6元Bent函数各等价类中函数的具体结构形式,并由此给出了以任意一个代数次数是3的6元Bent函数为分量的多维Bent函数的构造法.

关于一类Bent函数的研究

在Bent函数和半Bent函数的理论基础上证明了四分Bent函数的概念,并给出了半Bent函数的一种构造办法。求出了F62上全部3次齐次Bent函数。

一类k阶拟Bent函数密码性质的矩阵特征

由于非线性组合函数的密码性质通常可以由函数的Walsh谱和自相关函数来刻划 ,因而对函数的密码性质的分析通常要计算大量的Walsh循环谱值和自相关函数值来验证 .该文利用一类k阶拟Bent函数的特殊性质 ,把对这类函数的密码性质的研究转化为对矩阵性质的研究 ,如平衡性、相关免疫性、扩散性、最高代数次数等 .这种转化避开了大量的计算 ,同时为构造密码性质好的k阶拟Bent函数提供了一种更为简洁且易于实现的方法 .

关于Negabent函数的若干结论

利用二次不定方程的求解,研究了Negabent函数的判别和构造问题,给出了Negabent函数的一个直观判别条件和一种间接构造法,同时,证明了一类Maiorana-McFarland bent函数不是Negabent函数。

超Bent函数的性质和构造

借助置换函数的性质和构造,找到了布尔函数是超Bent函数的充要条件以及超Bent函数与PS类Bent函数的关系.给出了多输出超Bent函数的一般构造方法,并利用这种方法构造了具有高非线性度的平衡多输出函数.

一类Bent函数的构造

给出了具有任意偶数个变元的Bent函数的一种构造办法.该方法通过级联二个半Bent函数得到Bent函数,所构造的Bent函数具有极大的代数次数和可控的单项式项数。

广义Bent函数的稳定性及其构造

在ｐ是素数时，用ｐ次本原单位根给出广义Ｂｅｎｔ函数的谱判别条件，并由此对广义Ｂｅｎｔ函数的稳定性的概率意义进行了考察，最后，利用谱分解式研究了广义Ｂｅｎｔ函数的性质和构造，并据此给出了广义Ｂｅｎｔ函数的一种运算形式更一般的新的构造方法。

具有最高代数次数的2n元n维Bent函数的构造

本文给出了代数次数达到最高的一类布尔置换的代数标准形 ;并用m序列的状态转移矩阵和所得置换 ,构造了一类代数次数达到最高的 2n元n维Bent函数 ,用这类函数所构造的S盒具有较高的安全强度 .

广义部分Bent函数和广义Bent函数的关系

Bent函数是一类特殊的布尔函数 ,因其非线性性和稳定性在密码学和通信等领域有很重要的应用 .但它们数量少、不平衡且无相关免疫性 .为了弥补Bent函数的不足 ,Claud Carlet提出了部分 Bent函数的概念 ,部分 Bent函数是包含 Bent函数的更大的函数类 .后来 ,人们又将这两种函数概念先后都拓广到了环znm(m为正整数 )上 ,分别被称为 znm 上的广义 Bent函数和广义部分 Bent函数 .本文利用 znp(p为素数 )上广义部分 Bent函数的 Chrestenson循环谱特征讨论了 znp上的广义部分 Bent函数和广义 Bent函数之间的关系 。

代数次数为2的Bent函数的性质及其应用

本文证明了任意代数次数为2的n元Bent函数都与形式为x1x2+x3x4+…+xn-1xn的Bent函数线性等价;给出了以任意已知代数次数为2的n元Bent函数为分量的多维Bent函数的构造法;利用本文所给的方法,对任一主对角线上元素全为0的n阶可逆对称矩阵M1,都可以构造造k-1个主对角线上元素全为0的n阶可逆对称矩阵M2…,Mk,使得M1,M2…,Mk的任意非零线性组合仍是主对角线上元素全为0的阶可逆对称矩阵.

半Bent函数的密码学特性

给出了半bent函数的定义与Walsh谱特征 ,并讨论了其密码学特性 .

一类k阶拟Bent函数的构造

通过映射构造了一类布尔函数,利用布尔函数循环Walsh谱的方法给出了该类布尔函数是k阶拟Bent函数的充分必要条件,并利用集合性质给出了满足该条件的方法.另外,给出了一类k阶拟Bent函数的递归构造.

一类高阶Bent函数的构造方法

提出一类高阶Bent函数的构造方法,将级联后的Bent序列转化为矩阵形式,对矩阵作任意行列置换,得到一类新的Bent序列,根据Bent序列的性质,对2个已知的n元Bent函数进行Kronecker积运算,由此构造一个2n元的Bent函数,同理对m个n元Bent函数进行Kronecker积运算,构造mn元高阶Bent函数,并对构造的mn元Bent函数进行矩阵变换,得到数量更多的高阶Bent函数。