关于二阶代数免疫布尔函数的几个结果

关于布尔函数的代数免疫性与弹性、代数次数、非线性度之间的关系的结果至今仍然很少,饱和最优布尔函数在流密码领域具有较高的理论价值,通过计算证明文献[1]中命题8给出的5元最优布尔函数都是2阶代数免疫函数,并在此基础上对这个结果做了进一步推广。     

布尔函数和伪布尔函数多项式表示的快速实现算法

布尔函数和伪布尔函数在不同的领域有着广泛的应用,利用多项式表示有利于刻划它们的一些特征属性。论文首先在已知输入都能得到输出的条件下给出了布尔函数多项式表示的快速实现算法,该算法仅用到模2加运算,运算次数少,具有简洁、易于编程实现、准确而快速的特点,而且该算法很易推广为伪布尔函数多项式表示的快速实现算法,只需把模2加运算换成实数加运算即可。接着通过比较说明了伪布尔函数多项式表示的快速实现算法,同时指出任何伪布尔函数都能通过多项式形式表示出来。最后通过实例进一步验证了算法的正确性。     

布尔函数线路复杂度的一个新的下界

布尔函数的线路复杂下界问题与Ｐ＝？ＮＰ问题有密切关系，若证明了ＮＰ中某问题的线路复杂度是非多项式的，则Ｐ≠ＮＰ。但证明了一个具体的布尔函数具有非线性的线路复杂度下界却是计算复杂性理论中最难的问题之一。迄今此问题的最好结果是由Ｎ．Ｂｌｕｍ于１８９４年给出的，他证明了一个布尔函数具有３ｎ－３的线路复杂度下界。本文针对同一个布尔函数，给出一个更好的下界３ｎ＋１。     

布尔函数表示的二元判定图方法的研究与实现

布尔函数是数字系统与计算机科学等领域的基础，有广泛的应用。本文对布尔函数的二元判定图表示方法进行了详细讨论，说明了基于布尔函数的真值表和香农展开式来构造二元判定图的方法、二元判定图的简化、以及它在数字电路设计与测试中的应用。     

几类旋转对称布尔函数的密码学性质

Sumanta Sarkar等人给出了一类具有最大代数免疫阶的旋转对称布尔函数,但对给出的旋转对称布尔函数仅研究了该函数的非线性度而对其他密码学性质未加以研究.因此,研究了上面给出的旋转对称布尔函数的其他密码学性质:代数次数、线性结构、扩散性、相关免疫性等.研究结果显示,虽然这类布尔函数的代数免疫阶达到最大,但是其他的密码学性质并不好.因此,此类布尔函数并不能直接应用在密码系统中.     

基于引力搜索的布尔函数生成算法

布尔函数是在密码学、纠错编码和扩频通信等领域有着广泛应用的密码函数,寻找性能优良的布尔函数一直是密码学领域的重要问题之一。基于引力搜索算法设计了一种搜索布尔函数的新算法。该算法模仿万有引力定律,以n维空间中的质量点表示布尔函数,以布尔函数的密码特性作为目标适应度函数进行搜索。实验结果表明,算法使用新设计的目标适应度函数可以直接生成具有1阶弹性、1阶扩散准则和高非线性度、高代数次数以及低自相关指标等多种密码学指标的平衡布尔函数,并且进一步给出了直接生成2输出平衡布尔函数的计算机搜索算法。     

对称布尔函数的算术相关函数

算术相关函数是最近提出的一种研究布尔函数密码学性质的方法,该方法通过定义多元2-adic数上的加法和乘法运算,构建一种新的环结构,实现对经典相关函数的带进位计算的模拟。首先介绍了算术相关函数的定义,并针对具有良好密码学性质的对称布尔函数讨论了其算术相关函数的性质和取值,最后利用对称布尔函数的实值对称性证明了对称布尔函数的算术自相关函数也是一个与向量的重量有关的实值对称函数,至多是n+1值的。     

对称布尔函数的算术相关函数

算术相关函数是最近提出的一种研究布尔函数密码学性质的方法,该方法通过定义多元2-adic数上的加法和乘法运算,构建一种新的环结构,实现对经典相关函数的带进位计算的模拟。首先介绍了算术相关函数的定义,并针对具有良好密码学性质的对称布尔函数讨论了其算术相关函数的性质和取值,最后利用对称布尔函数的实值对称性证明了对称布尔函数的算术自相关函数也是一个与向量的重量有关的实值对称函数,至多是n+1值的。     

非线性布尔函数处理模型研究与设计

针对序列密码算法中非线性布尔函数的实现,利用布尔函数的拆分建模,提出一种以布尔函数拆分、布尔函数计算和输出回写为基础的通用非线性布尔函数处理模型,模型能够完成不同形式的非线性布尔函数实现.为更好地评估模型的实现能力,完成了序列密码中常见的非线性布尔函数的算法适配.适配结果表明,和现有的方式相比,模型适配能力较强,资源占用低,具有较好的发展前景.     

零化多项式与仿射空间关系研究

为把流密码的代数攻击问题转化为求解布尔函数的低次数零化多项式问题,讨论布尔函数的性质,介绍{0,1}上矩阵的特殊结构,研究两者间的关系,在此基础上探讨n元布尔函数f的零化多项式次数与f的支撑点集之间的关系,实验结果表明,寻找布尔函数零化多项式等价于在布尔函数的零点集合中寻找最大的仿射空间。     

Boolean Functions as Models for Quantified Boolean Formulas

In this paper, we introduce the notion of models for quantified Boolean formulas. For various classes of quantified Boolean formulas and various classes of Boolean functions, we investigate the problem of determining whether a model exists. Furthermore, we show for these classes the complexity of the model checking problem, which is to check whether a given set of Boolean functions is a model for a formula. For classes of Boolean functions, we establish some characterizations in terms of classes of quantified Boolean formulas that have such a model. This research has been supported in part by the Air Force Office of Scientific Research under grant FA9550-06-1-0050. This research has been supported in part by the NSFC under grants 60573011 and 10410638.     

一类二阶代数免疫函数的结构

对一阶代数免疫函数的结构进行了刻画,在此基础上讨论了一类二阶代数免疫布尔函数的构造问题,给出了两个[n]元一阶代数免疫函数通过级联得到[n]+1元二阶代数免疫函数的充分条件,并且给出了它们的若干结构和几个判断二阶代数免疫函数的判别准则。     

On the 2~m-variable symmetric Boolean functions with maximum algebraic immunity

The properties of the 2~m-variable symmetric Boolean functions with maximum al- gebraic immunity are studied in this paper.Their value vectors,algebraic normal forms,and algebraic degrees and weights are all obtained.At last,some necessary conditions for a symmetric Boolean function on even number variables to have maximum algebraic immunity are introduced.     

三元组布尔置换的构造

布尔置换和bent函数在密码学中起着非常重要的作用。在Coulter和Mesnager所提出的三元组布尔置换广义构造方法（该三元组布尔置换可以用来构造bent函数）的基础上，给出了一个等价的构造三元组布尔置换的具体方法。利用此具体方法，提供了一个构造三元组布尔置换的算法。对三个置换之间的依赖关系做了进一步研究，提出了一个三元组置换成立的充要条件，并给出了一个构造三元组布尔置换的新算法。分析了利用三元组布尔置换所得bent函数的性质。     

具有最大代数免疫度的奇数元布尔函数的构造

构造一个具有最大代数免疫度的奇数元布尔函数等价于在某一已知矩阵中寻找一个可逆子矩阵。如何在这一矩阵中有效地寻找可逆子矩阵仍然是一个难题。针对上述问题研究矩阵的性质,简化矩阵的刻画方式,给出构造最大代数免疫度的奇数元布尔函数的构造方法。构造时只需对低维数的向量进行操作,避免了子矩阵可逆性的判断,能够有效地构造具有最大代数免疫度的奇数元布尔函数。     

互补对称布尔函数的非线性度

互补对称布尔函数是一类特殊的对称布尔函数。在所有代数免疫最优的对称布尔函数中,有相当的比例均属此类函数。特别是当变元数量为2m元时,有2/3比例的代数免疫最优对称布尔函数都是互补对称布尔函数。通过布尔函数非线性度、Walsh谱和Krawtchouk多项式间的关系,计算出互补对称布尔函数的非线性度。结果表明,任意n元互补对称布尔函数的非线性度为2n-1-1/2[nn/2]     

On the independence of Boolean functions

Boolean functions are widely used because they can be used to precisely describe logical circuits. Properties of Boolean functions with respect to their applications to cryptography have been studied, but relationship between Boolean functions are rarely studied. This paper studies the independence of Boolean functions, gives necessary and sufficient conditions for judging whether two given Boolean functions are independent. Some enumeration formulae are given.     

Analysis of affinely equivalent Boolean functions

By some basic transforms and invariant theory, we give two results: 1) an algorithm, which can be used to judge if two Boolean functions are affinely equivalent and to obtain the equivalence relationship if they are equivalent. This is useful in studying Boolean functions and in engineering. For example, we classify all 8-variable homogeneous bent functions of degree 3 into two classes; 2) Reed-Muller codes R(4,6)/R(1,6), R(3,7)/R(1,7) are classified efficiently.     

多输出弹性k-旋转对称布尔函数的存在性与构造

多输出布尔函数可由多个单输出布尔函数表示,在分组密码中有着广泛的应用.多输出k-旋转对称布尔函数(k-RSBF)是多输出旋转对称布尔函数(RSBF)的扩展.本文首先研究多输出旋转对称函数和多输出k-旋转对称函数的轨道分布情况,给出了计算两类函数中长度相同轨道个数的方法.其次研究了平衡多输出k-旋转对称布尔函数的存在性,给出了在选择合适的k的前提下,n=pr、n=2pr和n=2r时,平衡(n,m)k-RSBF的构造方法.之后研究弹性多输出k-旋转对称布尔函数的存在性,分别给出了r≥3,n=2r,2≤m≤2r-r,k=2时1阶弹性(n,m)k-RSBF的构造方法,以及p为奇素数,r≥2,n=pr,2≤m≤p-1,k=p时1阶弹性(n,m)k-RSBF的构造方法.最后我们还对两种方法得到的1阶弹性多输出k-旋转对称布尔函数进行仿真测试.