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.     

Characteristic set algorithms for equation solving in finite fields

Efficient characteristic set methods for computing zeros of polynomial equation systems in a finite field are proposed. The concept of proper triangular sets is introduced and an explicit formula for the number of zeros of a proper and monic triangular set is given. An improved zero decomposition algorithm is proposed to reduce the zero set of an equation system to the union of zero sets of monic proper triangular sets. The bitsize complexity of this algorithm is shown to be O(lⁿ)$O\left(l^n\right)$ for Boolean polynomials, where n$n$ is the number of variables and l≥2$l\ge 2$ is the number of equations. We also give a multiplication free characteristic set method for Boolean polynomials, where the sizes of the polynomials occurred during the computation do not exceed the sizes of the input polynomials and the bitsize complexity of algorithm is O(n^d)$O\left(n^d\right)$ for input polynomials with n$n$ variables and degree d$d$. The algorithms are implemented in the case of Boolean polynomials and extensive experiments show that they are quite efficient for solving certain classes of Boolean equations raising from stream ciphers.     

Gbent函数的构造

基于研究布尔函数在子空间的限制,得到关于Gbent函数的一个充分必要条件。给出了两类简单的正则的Gbent函数。在此基础上,通过间接构造Bent函数的方法,利用已知的Gbent函数构造出了更多的Gbent函数。     

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.     

The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity

The rth order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. This paper tightens the lower bounds of the second order nonlinearity of three classes of Boolean functions in the form f(x)=tr(x^d) in n variables, where (1) d=2^m+1+3 and n=2m, or (2) , n=2m and m is odd, or (3) d=2^2r+2^r+1+1 and n=4r.     

一类弹性布尔函数的谱值分布

Sarka等人在文献[1]中给出了弹性布尔函数的一种构造方法,利用该方法可以构造出非线性度、弹性阶和代数次数等密码学性质均较理想的奇数元弹性布尔函数。对其构造得到的弹性布尔函数的谱值分布进行了研究,分析了由该方法所构造得到的5元1阶和7元1阶弹性布尔函数的谱值,给出了这两类弹性布尔函数的谱值分布情形,并给出了相应谱值点的计数结果。     

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.     

Improved generalized Atkin algorithm for computing square roots in finite fields

Recently, S. Müller developed a generalized Atkin algorithm for computing square roots, which requires two exponentiations in finite fields GF(q) when . In this paper, we present a simple improvement to it and the improved algorithm requires only one exponentiation for half of squares in finite fields GF(q) when . Furthermore, in finite fields GF(pm), where and m is odd, we reduce the complexity of the algorithm from O(m³log³p) to O(m²log²p(logm+logp)) using the Frobenius map and normal basis representation.     

Consensus networks over finite fields

This work studies consensus strategies for networks of agents with limited memory, computation, and communication capabilities. We assume that agents can process only values from a finite alphabet, and we adopt the framework of finite fields, where the alphabet consists of the integers {0,…,p−1}$\{0,\dots ,p-1\}$, for some prime number p$p$, and operations are performed modulo p$p$. Thus, we define a new class of consensus dynamics, which can be exploited in certain applications such as pose estimation in capacity and memory constrained sensor networks. For consensus networks over finite fields, we provide necessary and sufficient conditions on the network topology and weights to ensure convergence. We show that consensus networks over finite fields converge in finite time, a feature that can be hardly achieved over the field of real numbers. For the design of finite-field consensus networks, we propose a general design method, with high computational complexity, and a network composition rule to generate large consensus networks from smaller components. Finally, we discuss the application of finite-field consensus networks to distributed averaging and pose estimation in sensor networks.     

Results on rotation symmetric polynomials over GF(p)

In this paper, we generalize the recent counting results about rotation symmetric Boolean functions to the rotation symmetric polynomials over finite fields GF(p). By using Möbius function, we obtain some formulas for more general n, the number of variables. Some known formula in Boolean case are simplified.     

Interaction transform for bi-set functions over a finite set

Set functions appear as a useful tool in many areas of decision making and operations research, and several linear invertible transformations have been introduced for set functions, such as the Möbius transform and the interaction transform. The present paper establish similar transforms and their relationships for bi-set functions, i.e. functions of two disjoint subsets. Bi-set functions have been recently introduced in decision making (bi-capacities) and game theory (bi-cooperative games), and appear to open new areas in these fields.     

Spectral characterization of cryptographic Boolean functions satisfying the (extended) propagation criterion of degree l and order k

The (extended) propagation criterion was defined in cryptography in order to analyze the security of cryptographic components with respect to differential cryptanalysis. In this paper, we obtain the spectral characterization of functions satisfying the (extended) propagation criterion of degree l and order k. This important problem was left open since the introduction of these functions more than ten years ago.     

一阶相关免疫对称函数的构造

n元一阶相关免疫对称函数的构造等价于方程∑Cⁱ_n-1x_i=∑Cⁱ_n-1x_i+1在二元域上的求解。通过求解与其等价的方程C⁰_n-1y₀+∑(Cⁱ_n-1-C^i-1_n-1)y_i=0构造了一阶相关免疫对称函数,并在两种情形下给出了具体的构造和计数。     

Efficient bit-parallel multipliers over finite fields GF(2)

Hardware implementation of multiplication in finite field GF(2^m) based on sparse polynomials is found to be advantageous in terms of space-complexity as well as the time-complexity. In this paper, we present a new permutation method to construct the irreducible like-trinomials of the form (x + 1)^m + (x + 1)ⁿ + 1 for the implementation of efficient bit-parallel multipliers. For implementing the multiplications based on such polynomials, we have defined a like-polynomial basis (LPB) as an alternative to the original polynomial basis of GF(2^m). We have shown further that the modular arithmetic for the binary field based on like-trinomials is equivalent to the arithmetic for the field based on trinomials. In order to design multipliers for composite fields, we have found another permutation polynomial to convert irreducible polynomials into like-trinomials of the forms (x² + x + 1)^m + (x² + x + 1)ⁿ + 1, (x² + x)^m + (x² + x)ⁿ + 1 and (x⁴ + x + 1)^m + (x⁴ + x + 1)ⁿ + 1. The proposed bit-parallel multiplier over GF(2^4m) is found to offer a saving of about 33% multiplications and 42.8% additions over the corresponding existing architectures.     

周期为pq的四元广义分圆序列的线性复杂度

基于Gray映射和Ding-广义分圆理论,在Z₄上构造了一类周期为pq的四元广义分圆序列。在有限域F_r(r≥5为奇素数)上研究了新序列对应的傅里叶谱序列,并依据傅里叶谱序列的重量确定了新序列的线性复杂度。结果表明,新序列具有良好的线性复杂度性质,能够抗击B-M算法的攻击,是密码学意义上性质良好的伪随机序列。     

奇数元二阶相关免疫对称布尔函数的构造

n元m阶相关免疫对称函数的构造等价于方程[i=0n-2Cin-2xi=i=0n-2Cin-2xi+1]在二元域上的求解。通过对该方程及其等价方程解的关系讨论,给出了构造奇数元二阶相关免疫对称函数的算法。     

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.     

Deterministic distinct-degree factorization of polynomials over finite fields

A deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a theoretical open problem of Kaltofen from 1987.