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.     

Linear structures of symmetric functions over finite fields

It is shown that nonlinear symmetric functions over finite fields GF(p) have no linear structures other than equal component vectors.     

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.     

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.     

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.     

Upper bound for algebraic immunity on a subclass of Maiorana McFarland class of bent functions

Studying algebraic immunity of Boolean functions is recently a very important research topic in cryptography. It is recently proved by Courtois and Meier that for any Boolean function of n-variable the maximum algebraic immunity is . We found a large subclass of Maiorana McFarland bent functions on n-variable with a proven low level of algebraic immunity . To the best of our knowledge we provide for the first time a new upper bound for algebraic immunity for a nontrivial class of Boolean functions. We also discuss that this result has some fascinating implications.     

On the lower bounds of the second order nonlinearities of some Boolean functions

The rth order nonlinearity of a Boolean function is an important cryptographic criterion in analyzing the security of stream as well as block ciphers. It is also important in coding theory as it is related to the covering radius of the Reed-Muller code R(r,n). In this paper we deduce the lower bounds of the second order nonlinearities of the following two types of Boolean functions:

1.

with d=2^2r+2^r+1 and , where n=6r.

2.

, where x,y∈F_2^t,n=2t,n?6 and i is an integer such that 1?i<t,gcd(2^t-1,2ⁱ+1)=1.

For some λ, the functions of the first type are bent functions, whereas Boolean functions of the second type are all bent functions, i.e., they possess the maximum first order nonlinearity. It is demonstrated that in some cases our bounds are better than the previously obtained bounds.     

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.     

雪崩布尔函数的构造方法及个数估计

研究了满足严格雪崩准则布尔函数的性质,证明了雪崩布尔函数的汉明重量只能为偶数,并且得到了雪崩布尔函数的汉明重量之集,给出了不同汉明重量的雪崩布尔函数的构造方法。改进了雪崩布尔函数个数的下界。     

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

A lower bound on the mod 6 degree of the OR function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z _m . In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}ⁿ, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n ^{1/ r} ) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power. received 29 September 1994     

Comments on the ‘m out of n oblivious transfer’

This paper analyses the ‘m out of n oblivious transfer’, presented at the ACISP 2002 Conference. It is shown that the schemes presented in the paper fail to satisfy the requirements of the oblivious transfer.     

(r|p)-centroid problems on networks with vertex and edge demand

This paper analyzes (r|p)-centroid$(r|p)\mathrm{-}\mathrm{centroid}$ problems on networks with vertex and edge demand under a binary choice rule. Bilevel programming models are presented for the discrete problem class. Furthermore, NP-hardness proofs for the discrete and continuous (1|p)-centroid$(1|p)\mathrm{-}\mathrm{centroid}$ problem on general networks with edge demand only are provided. Nevertheless, an efficient algorithm to determine a discrete (1|p)-centroid$(1|p)\mathrm{-}\mathrm{centroid}$ of a tree network with vertex and edge demand can be derived.     

GF(p)上ECC的有效实现———MCS51微处理器系列

文章详细描述了在192-bit素域上椭圆曲线公钥密码体制ECC(EllipticCurvepublickeyCryptography)在IntelMCS51微处理器系列智能卡上的实现过程。采用了Generalized-Mersenne素数作基域GF(p)(p=2192-264-1),利用模数的特殊形式及椭圆曲线的特殊参数,实现了GF(p)上ECC的全部过程,并且建立了软件库。运行速度表明ECC在计算资源受限、低功耗微处理器上实现是可行的。     

On the uniform finite generation of SO(n, )

A Lie group G, generated by two one-parameter subgroups is said to be uniformly finitely generated by them if there exists a positive integer N such that every element of G can be expressed as a product of at most N elements chosen alternately from the two one-parameter subgroups. In this paper we construct pairs of generators of so(n) whose one-parameter subgroups uniformly finitely generate SO(n) and as a consequence, we put an upper bound on the number of switches required to join any two points on a manifold M trajectories of two particular vector fields on M.     

A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs

We study a problem of lower bounds on straight line drawings of planar graphs. We show that at least 1.235·n points in the plane are required to draw each n-vertex planar graph with edges drawn as straight line segments (for sufficiently large n). This improves the previous best bound of 1.206·n (for sufficiently large n) due to Chrobak and Karloff [Sigact News 20 (4) (1989) 83-86]. Our contribution is twofold: we improve the lower bound itself and we give a significantly simpler and more straightforward proof.     

Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials

We improve some lower bounds which have been obtained by Strassen and Lipton. In particular there exist polynomials of degree n with 0–1 coefficients that cannot be evaluated with less than $\text{n}\text{/(4}\text{log}\text{n)}$ nonscalar multiplications/divisions. The evaluation of p(x) $\text{∑}\text{δ=0}\text{n}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>2\delta </mtext>}}\text{x}{}^{\mathrm{\delta }}$ requires at least $\text{n}\text{(12}\text{log}\text{n)}$ multiplications/divisions and at least $\text{n/(8}\text{log}\text{n)}$ nonscalar multiplications/divisions. We specify polynomials with algebraic coefficients that require $\text{1}\text{2}\text{n}$ multiplications/divisions.     

Lp(R0) (p ⩾ 1) stability in the mean m (m ⩾ 1) of a class of stochastic volterra integral equations

In this paper we consider a class of stochastic nonlinear Volterra integral equation. The problem of L^P(R₀ (p ? 1) stability in the mean m (m ? 1) is examined.In Section 2, the random Banach fixed-point theorem is used to establish the existence and uniqueness of solutions of the system in some general Banach spaces. These results are then used to study the L^P(R₀) (p ? 1) stability in the mean m (m ? 1) of the system.For illustration, an example of the visually induced height orientation of the fly (Musca domestica) is considered.