Verifying the determinant in parallel

In this paper, we investigate the complexity of verifying problems whose computation is equivalent to the determinant, both in the Boolean arithmetic circuit and in the Boolean circuit model. We observe that for a few problems, there exists an easy (NC ¹) verification algorithm. To characterize the harder ones, we define the class of problems that are reducible to the verification of the determinant, under two different reductions, and establish a list of complete problems in these classes. In particular, we prove that computing the rank is equivalent under AC ⁰ reductions to verifying the determinant. We show in the Boolean case that none of the complete problems can be recognized in NC ¹ unless L = NL. On the other hand, we show that for functions, there exists an NC ¹ checker even if they are hard to verify, and that they can be extended into functions whose verification is easy. received 24 August 1995     

Computation of signal output probability for Boolean functions represented by OBDD

In [l] and [2], two algorithms have been proposed to calculate the output probability of Boolean functions represented by OBDDs, assuming that the input variables are equiprobable and each variable is statistically independent from others. In this paper, we point out that under these assumptions, the output probability calculation is equivalent to counting the number of minterms of the corresponding Boolean functions. An algorithm is proposed to compute the output probability using simple integer arithmetic as opposed to floating point arithmetic involved in [1,2]. To compute output probability of Boolean functions represented by shared OBDI)s and OBDDs with edge negation, we further propose a generalized algorithm.     

On cross-correlation properties of Boolean functions

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.     

Construction of 1-resilient Boolean functions with optimum algebraic immunity

In this paper, for an integer n≥10, two classes of n-variable Boolean functions with optimum algebraic immunity (AI) are constructed, and their nonlinearities are also determined. Based on non-degenerate linear transforms to the proposed functions, we can obtain 1-resilient n-variable Boolean functions with optimum AI and high nonlinearity if n?1 is never equal to any power of 2.     

A construction of Boolean functions with good cryptographic properties

The two important qualities of a cipher are security and speed. Frequently, to satisfy the security of a Boolean function primitive, speed may be traded-off. In this paper, we present a general construction that addresses both qualities. The idea of our construction is to manipulate a cryptographically strong base function and one of its affine equivalent functions, using concatenation and negation. We achieve security from the inherent qualities of the base function, which are preserved (or increased), and obtain speed by the simple Boolean operations. We present two applications of the construction to demonstrate the flexibility and efficiency of the construction.     

一类H布尔函数的代数次数、相关免疫性与代数免疫性的关系

以布尔函数的导数和自定义的e-导数为研究工具,研究了一类特定Hamming重量的H布尔函数的代数次数、代数免疫性、相关免疫性之间的关联问题.得出H布尔函数的组成部分e-导数的代数次数决定了H布尔函数的代数次数;H布尔函数的e-导数与H布尔函数的代数免疫阶的大小紧密关联;H布尔函数的e-导数可将H布尔函数的代数免疫性、零化子、相关免疫性、代数次数联系到一起等.同时,导出了公式法和级联法两类求解H布尔函数最低代数次数零化子的不同方法.     

The autocorrelation distribution of balanced Boolean function

The global avalanche characteristics (the sum-of-squares indicator and the absolute indicator) measure the overall avalanche characteristics of a cryptographic Boolean function. Sung et al. (1999) gave the lower bound on the sum-of-squares indicator for a balanced Boolean function satisfying the propagation criterion with respect to some vectors. In this paper, if balanced Boolean functions satisfy the propagation criterion with respect to some vectors, we give three necessary and sufficient conditions on the auto-correlation distribution of these functions reaching the minimum the bound on the sum-of-squares indicator. And we also find all Boolean functions with 3-variable, 4-variable, and 5-variable reaching the minimum the bound on the sum-of-squares indicator.     

Permutation equivalence of cubic rotation symmetric Boolean functions

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.     

Counterexamples to the long-standing conjecture on the complexity of BDD binary operations

In this article, we disprove the long-standing conjecture, proposed by R.E. Bryant in 1986, that his binary decision diagram (BDD) algorithm computes any binary operation on two Boolean functions in linear time in the input–output sizes. We present Boolean functions for which the time required by Bryant?s algorithm is a quadratic of the input–output sizes for all nontrivial binary operations, such as ∧, ∨, and ⊕. For the operations ∧ and ∨, we show an even stronger counterexample where the output BDD size is constant, but the computation time is still a quadratic of the input BDD size. In addition, we present experimental results to support our theoretical observations.     

三元组布尔置换的构造

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

What can we do with a linear optical logic gate?

In an earlier paper [H.J. Caulfield, J. Westphal, The logic of optics and the optics of logic, Information Sciences 162 (2004) 21-33], we considered a simple interferometer (initially conceived as Mach-Zehnder) with two uniform intensity mutually coherent inputs. By encoding those inputs with phases 0 and π representing Boolean 0 and 1 and identifying the detected values of the outputs as logical Boolean values, we found that the outputs could be identified as the Boolean operations XOR and COINC (sometimes called XNOR). Here, we show that this seemingly simple interferometer can perform many additional functions if we use phases to interpret its outputs. But the XOR/COINC are the only non-trivial logic gate we can get no matter how we cascade Mach-Zehnder interferometers. We also generalize those operations upwards (to three or four arguments). We show that the three argument interferometer or four-argument interferometer cannot produce a Fredkin gate or its variation.     

多输出弹性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-旋转对称布尔函数进行仿真测试.     

On cross-correlation indicators of an S-box

Substitution boxes (S-boxes) are often used as the most important nonlinear components in many symmetric encryption algorithms. The cryptographic properties of an S-box directly affect the security of the whole cipher system. Recently, generalized global avalanche characteristics (GGAC) were introduced to measure the correlation between two arbitrary Boolean functions. In this paper, to better evaluate the security of an S-box, we present two cross-correlation indicators for it. In addition, by studying the related properties of the cross-correlation between two balanced Boolean functions, we propose the lower bounds on the sum-of-squares indicator related to GGAC for two balanced functions and also for an S-box.     

On the relationship between fuzzy and Boolean cellular automata

Fuzzy cellular automata (FCA) are continuous cellular automata where the local rule is defined as the “fuzzification” of the local rule of a corresponding Boolean cellular automaton in disjunctive normal form. In this paper, we are interested in the relationship between Boolean and fuzzy models and, for the first time, we analytically show the existence of a strong connection between them by focusing on two properties: density conservation and additivity.We begin by showing that the density conservation property, extensively studied in the Boolean domain, is preserved in the fuzzy domain: a Boolean CA is density conserving if and only if the corresponding FCA is sum preserving. A similar result is established for another novel “spatial” density conservation property. Second, we prove an interesting parallel between the additivity of Boolean CA and oscillations of the corresponding fuzzy CA around its fixed point. In fact, we show that a Boolean CA is additive if and only if the behaviour of the corresponding fuzzy CA around its fixed point coincides with the Boolean behaviour. Finally, we give a probabilistic interpretation of our fuzzification which establishes an equivalence between convergent fuzzy CA and the mean field approximation on Boolean CA, an estimation of their asymptotic density.These connections between the Boolean and the fuzzy models are the first formal proofs of a relationship between them.     

Recognition of interval Boolean functions

Interval functions constitute a special class of Boolean functions for which it is very easy and fast to determine their functional value on a specified input vector. The value of an n-variable interval function specified by interval [a,b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval [a,b]. In this paper we study the problem of deciding whether a given disjunctive normal form represents an interval function and if so then we also want to output the corresponding interval. For general Boolean functions this problem is co-NP-hard. In our article we present a polynomial time algorithm which works for monotone functions. We shall also show that given a Boolean function f belonging to some class which is closed under partial assignment and for which we are able to solve the satisfiability problem in polynomial time, we can also decide whether f is an interval function in polynomial time. We show how to recognize a “renamable” variant of interval functions, i.e., their variable complementation closure. Another studied problem is the problem of finding an interval extension of partially defined Boolean functions. We also study some other properties of interval functions.      

On the equal-weight symmetric Boolean functions

Two important classes of symmetric Boolean functions are the equal-weight Boolean functions and the elementary (or homogeneous) symmetric Boolean functions. In this paper we studied the equal-weight symmetric Boolean functions. First the Walsh spectra of the equal-weight symmetric Boolean functions are given. Second the sufficient and necessary condition on correlation-immunity of the equal-weight symmetric Boolean function is derived and other cryptology properties such as the nonlinearity, balance and propagation criterion are taken into account. In particular, the nonlinearity of the equal-weight symmetric Boolean functions with n (n ≥ 10) variables is determined by their Hamming weight. Considering these properties will be helpful in further investigations of symmetric Boolean functions.     

最优代数免疫布尔函数的完全构造

任意的布尔函数可以唯一地表示成有限域上的单变元多项式函数,利用布尔函数的单变元多项式表示和代数编码理论,讨论了布尔函数的代数免疫达到最优的判别条件,得到了布尔函数的变元个数为奇数时,布尔函数具有最优代数免疫(MAI)的等价判别条件。利用该等价判别条件,给出3元布尔函数满足MAI的等价判别条件,进而构造出所有3元的MAI布尔函数。     

Searching for information in an online public access catalogue (OPAC): the impacts of information search expertise on the use of Boolean operators

Abstract Boolean systems still constitute most of the installed base of online public access catalogues (OPACs) in the French universities even if many studies have shown that Boolean operators are not frequently used by ‘non‐librarian’ users (by contrast with professional librarians). The first study examined the use of Boolean operators by French university students; In the second study, elaborated to evaluate the impact of information search expertise on this use, Boolean operators are explicitly presented and participants were explicitly invited to use them. We assumed that university students would not frequently use the operators in searching, and that even if they were explicitly invited to make use of them. Results obtained with the first study based on transaction logs analyses confirmed that French university students did not frequently use Boolean operators. The impact of information search expertise, analysed in the second study, compared three levels of expertise: Novice (university students), intermediate (future professional librarians), and expert (professional librarians). Results showed that, even if the three groups were invited to use Boolean operators, this use increased significantly with the level of information search expertise. University students, if they manage procedural functions of connectives in natural language, do not always manage the whole set of procedural functions carried by such connectives when used in the documentary language. So, the relevance of presenting explicit Boolean operators in the OPACs when users are ‘non‐librarians’ is questioned.