共查询到20条相似文献,搜索用时 5 毫秒
1.
On the number of rotation symmetric Boolean functions 总被引:2,自引:0,他引:2
FU ShaoJing LI Chao & QU LongJiang Science College of National University of Defense Technology Changsha China State Key Laboratory of Information Security Beijing National Mobile Communications Research Laboratory Southeast University Nanjing 《中国科学:信息科学(英文版)》2010,(3):537-545
Rotation symmetric Boolean functions (RSBFs) have been used as components of different cryptosystems. This class of functions are invariant under circular translation of indices. In this paper, we investigated balanced RSBFs and 1st order correlation immune RSBFs. Based on constructive techniques, we give an accurate enumeration formula for n-variable balanced RSBFs when n is a power of a prime. Furthermore, an original and efficient method to enumerate all n-variable (n prime) 1st order correlationimmune f... 相似文献
2.
Larry J. Stockmeyer 《Theory of Computing Systems》1976,10(1):323-336
A property of the truth table of a symmetric Boolean function is given from which one can infer a lower bound on the minimal number of 2-ary Boolean operations that are necessary to compute the function. For certain functions ofn arguments, lower bounds between roughly 2n and 5n/2 can be obtained. In particular, for eachm 3, a lower bound of 5n/2 –O(1) is established for the function ofn arguments that assumes the value 1 iff the number of arguments equal to 1 is a multiple ofm. Fixingm = 4, this lower bound is the best possible to within an additive constant. 相似文献
3.
QU LongJiang LI Chao 《中国科学F辑(英文版)》2008,(2)
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. 相似文献
4.
Thomas W. Cusick 《国际计算机数学杂志》2015,92(8):1568-1573
Rotation symmetric Boolean functions have been extensively studied for about 15 years because of their applications in cryptography and coding theory. Until recently little was known about the basic question of when two such functions are affine equivalent. The simplest case of quadratic rotation symmetric functions which are generated by cyclic permutations of the variables in a single monomial was only settled in 2009. For the much more complicated case of cubic rotation symmetric functions generated by a single monomial, the affine equivalence classes under permutations which preserve rotation symmetry were determined in 2011. It was conjectured then that the cubic equivalence classes are the same if all nonsingular affine transformations, not just permutations, are allowed. This conjecture is probably difficult, but here we take a step towards it by proving that the cubic affine equivalence classes found in 2011 are the same if all permutations, not just those preserving rotation symmetry, are allowed. The needed new idea uses the theory of circulant matrices. 相似文献
5.
A problem of polynomial expansion of symmetric Boolean functions is considered. A matrix method for polynomial expansion of symmetric functions that can be used to calculate the working numbers of homogeneous polynomial symmetric Boolean functions is proposed. 相似文献
6.
《国际计算机数学杂志》2012,89(4):415-420
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. 相似文献
7.
E. Demenkov A. Kojevnikov A. Kulikov G. Yaroslavtsev 《Information Processing Letters》2010,110(7):264-267
In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5n+o(n) for any symmetric function of n variables, as well as circuits of size 3n for function. 相似文献
8.
Rotation symmetric Boolean functions(RSBFs) have been used as components of different cryptosystems.In this paper,we investigate n-variable(n even and n≥12) RSBFs to achieve maximum algebraic immunity(AI),and provide a construction of RSBFs with maximum AI and nonlinearity.These functions have higher nonlinearity than the previously known nonlinearity of RSBFs with maximum AI.We also prove that our construction provides high algebraic degree in some case. 相似文献
9.
10.
11.
代数免疫度达到最大的偶变元对称布尔函数的特征仍然是个公开问题。结合组合数学和数论的相关结论研究这类函数的性质,得到了此类函数值向量的几个特征。最后,对于变元个数为两类特殊偶数的情况,得到了代数免疫度达到最大的对称函数的一个特征。 相似文献
12.
Thecorrelation between two Boolean functions ofn inputs is defined as the number of times the functions agree minus the number of times they disagree, all divided by 2
n
. In this paper we compute, in closed form, the correlation between any twosymmetric Boolean functions. As a consequence of our main result, we get that every symmetric Boolean function having an odd period
has anexponentially small correlation (inn) with the parity function. This improves a result of Smolensky [12] restricted to symmetric Boolean functions: the correlation
between parity and any circuit consisting of a Mod
q
gate over AND gates of small fan-in, whereq is odd and the function computed by the sum of the AND gates is symmetric, is bounded by 2−Ω(n).
In addition, we find that for a large class of symmetric functions the correlation with parity isidentically zero for infinitely manyn. We characterize exactly those symmetric Boolean functions having this property.
This research was supported in part by NSF Grant CCR-9057486. Jin-Yi Cai was supported in part by an Alfred T. Sloan Fellowship
in computer science. The work of F. Green was done in part while visiting Princeton University, while the work of T. Thierauf
was done in part while visiting Princeton University and the University of Rochester. The third author was supported in part
by DFG Postdoctoral Stipend Th 472/1-1 and by NSF Grant CCR-8957604. 相似文献
13.
《国际计算机数学杂志》2012,89(10):2035-2041
The relationship among cross-correlation of arbitrary four Boolean functions is presented. Several known cross-correlation properties of Boolean functions are generalized. Based on them, a lower bound for the maximal cross-correlation (in absolute value) of two Boolean functions (if one of the functions is bent) is obtained. 相似文献
14.
15.
16.
17.
The parity decision tree model extends the decision tree model by allowing the computation of a parity function in one step. We prove that the deterministic parity decision tree complexity of any Boolean function is polynomially related to the non-deterministic complexity of the function or its complement. We also show that they are polynomially related to an analogue of the block sensitivity. We further study parity decision trees in their relations with an intermediate variant of the decision trees, as well as with communication complexity. 相似文献
18.
This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes Dp and pSAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship. 相似文献
19.
The properties of the 2m-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. 相似文献
20.
In this paper, we prove two general theorems on monotone Boolean functions which are useful for constructing a learning algorithm for monotone Boolean functions under the uniform distribution. 相似文献