共查询到16条相似文献,搜索用时 140 毫秒
1.
在流密码和分组密码的设计中,所用布尔函数应该具有好的密码学性质来抵抗已知的各种有效攻击.布尔函数的低次零化子空间维数与其补函数低次零化子空间维数之和是评价该函数抵抗代数攻击能力的一个重要参数.根据Maiorana-McFarlands(M-M)Bent函数和布尔置换之间的一一对应关系,给出了一组布尔函数组并证明了它们是线性无关的.借助所给的线性无关布尔函数组和布尔置换中向量函数非零线性组合均是平衡函数的特性,给出了一类特殊M-M Bent函数低次零化子空间的维数与其补函数低次零化子空间的维数之和的一个上限.就这类特殊M-M Bent函数而言,该上限低于已知的限.进一步给出了适合所有M-M Bent函数的新上限. 相似文献
2.
3.
研究了旋转对称布尔函数的最高扩散次数、最高非线性度、代数免疫性和最优代数免疫函数的存在性与构造等问题。利用导数和e-导数证明了非线性度达到最高的旋转对称布尔函数的存在性,并利用导数,由扩散性达到最高n次的Bent函数来验证一类旋转对称Bent函数的存在性。同时证明了1阶代数免疫和2阶以上代数免疫旋转对称布尔函数的存在性。另外,利用旋转对称Bent函数构造了非齐次完全旋转对称最优代数免疫布尔函数以及一类众多的最优代数免疫布尔函数,并证明了这两类函数的存在性。同时,也得到了非齐次完全旋转对称相关免疫布尔函数。 相似文献
4.
对布尔函数零化子的计数问题进行研究,在布尔函数系数矩阵的基础上给出线性独立零化子的一种新计数方式。提出布尔函数低次零化子概念,并在线性独立零化子新计数方式的基础上找到一种寻找布尔函数低次零化子的方法。对利用布尔函数低次零化子建立低错方程组实施攻击的思想进行了阐述。 相似文献
5.
基于研究布尔函数在子空间的限制,得到关于Gbent函数的一个充分必要条件。给出了两类简单的正则的Gbent函数。在此基础上,通过间接构造Bent函数的方法,利用已知的Gbent函数构造出了更多的Gbent函数。 相似文献
6.
平衡性,非线性,扩散性是具有高度密码特性的布尔函数要满足的最重 要的三个性质,本文给出了用Bent函数来构造满足高次扩散准则的,具有较高非线性度的平衡布尔函数的一些方法。 相似文献
7.
8.
布尔函数的线路复杂下界问题与P=?NP问题有密切关系,若证明了NP中某问题的线路复杂度是非多项式的,则P≠NP。但证明了一个具体的布尔函数具有非线性的线路复杂度下界却是计算复杂性理论中最难的问题之一。迄今此问题的最好结果是由N.Blum于1894年给出的,他证明了一个布尔函数具有3n-3的线路复杂度下界。本文针对同一个布尔函数,给出一个更好的下界3n+1。 相似文献
9.
10.
Plateaued函数是包含Bent函数和部分Bent函数的更大函数类,具有许多优良的密码学性质。基于布尔函数非线性度与代数免疫阶之间的关系,利用Walsh谱等工具,讨论奇数变元的plateaued函数的代数免疫性质,得到其存在低次零化子的一个充分条件,并进一步刻画变元个数n与plateaued函数的阶r之间的具体关系,利用此关系可确定函数代数免疫阶的上界。 相似文献
11.
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. 相似文献
12.
jakobsen,、kuhdsen利用lagrange插值公式对分组密码给出了一个攻击。该问题可抽象为黑盒子问题即需要多少输入输出可以唯一确定s-盒。该文利用逻辑函数的迹表示给出了s-盒的一种线性复杂度度量。并计算了一些构造性方法构造的逻辑函数的线性复杂度。 相似文献
13.
14.
Ingo Wegener 《Acta Informatica》1980,13(2):109-114
Summary Neciporuk [3], Lamagna/Savage [1] and Tarjan [6] determined the monotone network complexity of a set of Boolean sums if each two sums have at most one variable in common. By this result they could define explicitely a set of n Boolean sums which depend on n variables and whose monotone complexity is of order n
3/2. In the main theorem of this paper we prove a more general lower bound on the monotone network complexity of Boolean sums. Our lower bound is for many Boolean sums the first nontrivial lower bound. On the other side we can prove that the best lower bound which the main theorem yields is the n
3/2-bound cited above. For the proof we use the technical trick of assuming that certain functions are given for free. 相似文献
15.
The influence of oppositely classified examples on the generalization complexity of Boolean functions 总被引:1,自引:0,他引:1
In this paper, we analyze Boolean functions using a recently proposed measure of their complexity. This complexity measure, motivated by the aim of relating the complexity of the functions with the generalization ability that can be obtained when the functions are implemented in feed-forward neural networks, is the sum of a number of components. We concentrate on the case in which we use the first two of these components. The first is related to the "average sensitivity" of the function and the second is, in a sense, a measure of the "randomness" or lack of structure of the function. In this paper, we investigate the importance of using the second term in the complexity measure, and we consider to what extent these two terms suffice as an indicator of how difficult it is to learn a Boolean function. We also explore the existence of very complex Boolean functions, considering, in particular, the symmetric Boolean functions. 相似文献
16.
Ashley Montanaro 《Theoretical computer science》2011,412(35):4619-4628
This work studies the quantum query complexity of Boolean functions in an unbounded-error scenario where it is only required that the query algorithm succeeds with a probability strictly greater than 1/2. We show that, just as in the communication complexity model, the unbounded-error quantum query complexity is exactly half of its classical counterpart for any (partial or total) Boolean function. Moreover, connecting the query and communication complexity results, we show that the “black-box” approach to convert quantum query algorithms into communication protocols by Buhrman-Cleve—Wigderson [STOC’98] is optimal even in the unbounded-error setting.We also study a related setting, called the weakly unbounded-error setting, where the cost of a query algorithm is given by q+log(1/2(p−1/2)), where q is the number of queries made and p>1/2 is the success probability of the algorithm. In contrast to the case of communication complexity, we show a tight multiplicative Θ(logn) separation between quantum and classical query complexity in this setting for a partial Boolean function. The asymptotic equivalence between them is also shown for some well-studied total Boolean functions. 相似文献