WDC算法与6元Bent函数计数

摘要

一般情况下，在布尔函数的研究中，给定一部分地址处Walsh谱值的集合■,寻找满足在这些地址具有给定谱值的所有n元布尔函数是很困难的。但是如果给定的地址集合是一个向量子空间，则有简单的求解方法。文章给出一种WDC算法，求解具有子空间结构地址的Walsh谱值的所有n元布尔函数以及个数。该算法包括3方面的内容：(1)如何构造满足这些条件的n元布尔函数；(2)满足这些条件的n元布尔函数有多少个?(3)子空间地址上的谱值满足什么条件时，才能保证满足这些条件的n元布尔函数存在。另外，Bent函数是非线性度最高的布尔函数，具有非常好的密码学性质。文章利用WDC算法并借助计算机搜索，求解出所有的6元Bent函数，共有5 425 430 528个。

关键词

WDC算法 / Walsh谱 / Bent函数 / 哈德玛矩阵