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

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

A constructive count of rotation symmetric functions

In this paper we present a constructive detection of minimal monomials in the algebraic normal form of rotation symmetric Boolean functions (immune to circular translation of indices). This helps in constructing rotation symmetric Boolean functions by respecting the rules we present here.     

一类代数免疫度达到最优的布尔函数的构造

给出了一种具有最优代数免疫度的偶数元布尔函数的构造,同时还给出了一种具有最优代数免疫度的平衡旋转对称偶数元布尔函数的构造.在构造过程中用到了线性代数和组合计数中的有关结论,这些函数对代数攻击均有很强的抵抗能力.构造的平衡旋转对称布尔函数还可用在Hash算法的轮函数中,增加了算法的安全性.     

一类代数免疫度达到最优的布尔函数的构造

给出了一种具有最优代数免疫度的偶数元布尔函数的构造,同时还给出了一种具有最优代数免疫度的平衡旋转对称偶数元布尔函数的构造.在构造过程中用到了线性代数和组合计数中的有关结论,这些函数对代数攻击均有很强的抵抗能力.构造的平衡旋转对称布尔函数还可用在Hash算法的轮函数中,增加了算法的安全性.     

On affine (non)equivalence of Boolean functions

In this paper we construct a multiset S(f) of a Boolean function f consisting of the weights of the second derivatives of the function f with respect to all distinct two-dimensional subspaces of the domain. We refer to S(f) as the second derivative spectrum of f. The frequency distribution of the weights of these second derivatives is referred to as the weight distribution of the second derivative spectrum. It is demonstrated in this paper that this weight distribution can be used to distinguish affine nonequivalent Boolean functions. Given a Boolean function f on n variables we present an efficient algorithm having O(n2²ⁿ ) time complexity to compute S(f). Using this weight distribution we show that all the 6-variable affine nonequivalent bents can be distinguished. We study the subclass of partial-spreads type bent functions known as PS _ap type bents. Six different weight distributions are obtained from the set of PS _ap bents on 8-variables. Using the second derivative spectrum we show that there exist 6 and 8 variable bent functions which are not affine equivalent to rotation symmetric bent functions. Lastly we prove that no non-quadratic Kasami bent function is affine equivalent to Maiorana–MacFarland type bent 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.     

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.     

Improved lower bound on the number of balanced symmetric functions over GF(p)

The lower bound on the number of n-variable balanced symmetric functions over finite fields GF(p) presented by Cusick et al. in [T.W. Cusick, Y. Li, P. Staˇnicaˇ, Balanced symmetric functions over GF(p), IEEE Trans. Inform. Theory 54 (3) (2008) 1304-1307] is improved in this paper. An equivalent characterization is also presented for the general case.     

New upper bounds on the Boolean circuit complexity of symmetric functions

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.     

Monotone Boolean dualization is in co-NP[logn]

In 1996, Fredman and Khachiyan [J. Algorithms 21 (1996) 618-628] presented a remarkable algorithm for the problem of checking the duality of a pair of monotone Boolean expressions in disjunctive normal form. Their algorithm runs in n^o(logn) time, thus giving evidence that the problem lies in an intermediate class between P and co-NP. In this paper we show that a modified version of their algorithm requires deterministic polynomial time plus O(log²n) nondeterministic guesses, thus placing the problem in the class co-NP[log²n]. Our nondeterministic version has also the advantage of having a simpler analysis than the deterministic one.     

最高非线性度旋转对称布尔函数与最优代数免疫函数

研究了旋转对称布尔函数的最高扩散次数、最高非线性度、代数免疫性和最优代数免疫函数的存在性与构造等问题。利用导数和e-导数证明了非线性度达到最高的旋转对称布尔函数的存在性,并利用导数,由扩散性达到最高n次的Bent函数来验证一类旋转对称Bent函数的存在性。同时证明了1阶代数免疫和2阶以上代数免疫旋转对称布尔函数的存在性。另外,利用旋转对称Bent函数构造了非齐次完全旋转对称最优代数免疫布尔函数以及一类众多的最优代数免疫布尔函数,并证明了这两类函数的存在性。同时,也得到了非齐次完全旋转对称相关免疫布尔函数。     

An application of H differentiability to generalized complementarity problems over symmetric cones

In this paper, we focus on a generalized complementarity problems over symmetric cone GSCCP(f,g) when the underlying functions f and g are H-differentiable. By introducing the concepts of relatively uniform Cartesian P-property, relatively Cartesian P(P₀)-property, the Cartesian semimonotone (E₀)-property (strictly Cartesian semimonotone (E)-property), and the relatively regular point with respect to the merit function Ψ(x), we extend various similar results proved in GCP(f,g) to generalized complementarity problems over symmetric cone GSCCP(f,g) and establish various conditions on f and g to get a solution to GSCCP(f,g).     

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

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

On the correlation of symmetric functions

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 ⁿ . 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.     

多输出弹性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 the 2<Superscript>m</Superscript>-variable symmetric Boolean functions with maximum algebraic immunity

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.     

Efficient and exact computation of Hubbard and t-J models using quantum diagonalization method

The quantum Monte Carlo diagonalization or stochastic diagonalization serves as a computational method of solving exactly quantum Hamiltonian models. While based on a variational method, in which the solution approaches the optimal eigenstate of a huge Hamiltonian matrix, the diagonalization method in practice has difficulty because of the rapidly increasing number of quantum states. In this paper, we suggest an improved implementation method of finding the ground state via exact diagonalization of the Hubbard and t-J model Hamiltonians. Achieved is a great increase in the computational capability through an optimized code based on Boolean operations, a reduction of the state space using symmetry properties, and an effective variation on the trial ground state. Our method is restricted mainly by the memory capacity to keep the components of the trial ground state. Carried out on a single personal computer, the method turns out to find exact solutions in a relatively short time with ¹⁰⁸-¹⁰⁹ basis states.     

Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.     

A compact model for the I–V characteristics of an undoped double-gate MOSFET

An analytic model for the I–V characteristics of a symmetric, undoped, double gate MOSFET is presented. The model is two-dimensional and extends recent work by Chen and Taur. The formulae involve the LambertW function recently used by Ortiz-Conde to obtain threshold voltage approximations of an undoped single gate MOSFET. The drift diffusion equations are also solved numerically and our approximate solution for the Fermi potential is shown to be in close agreement with the exact numeric solution. We present a compact model for the complete I–V characteristics of an undoped double gate MOSFET.