在仿射等价类中找具有好的密码学性质的布尔函数

The Boolean functions in an affine equivalence class are of the same algebraic degree and nonlinearity, but may satisfy different order of correlation immunity and propagation criterion. A method is presented in this paper to find Boolean functions with higher order correlation immunity or satisfying higher order propagation criterion in an affine equivalence class. 8 AES s-box functions are not better Boolean functions in their affine equivalence class.     

On Partial Classes Containig All Monotone and Zero-Preserving Total Boolean Functions

We describe sets of partial Boolean functions being closed under the operations of superposition. For any class A of total functions we define the set ??(A) consisting of all partial classes which contain precisely the functions of A as total functions. The cardinalities of such sets ??(A) can be finite or infinite. We state some general results on ??(A). In particular, we describe all 30 closed sets of partial Boolean functions which contain all monotone and zero-preserving total Boolean functions.     

Asymptotic Nonlinearity of Boolean Functions

Boolean functions on the space are not only important in the theory of error-correcting codes, but also in cryptography. In these two cases, the nonlinearity of these functions is a main concept. Carlet, Olejár and Stanek gave an asymptotic lower bound for the nonlinearity of most of them, and I gave an asymptotic upper bound which was strictly larger. In this article, I improve the bounds and get an exact limit for the nonlinearity of most of Boolean functions. This article is inspired by a paper of G. Halász about the related problem of real polynomials with random coefficients. AMS Classification (2000) Primary: 11T71 · Secondary: 06E30 · 42A05 · 94C10     

用反链方法估计可分布尔函数的个数

用单层神经网络可表示的ｎ元布尔函数的计数问题一直未得到解决,本文利用反链工具给出这一计数的新的估计方法．     

Vectorial Resilient PC（l） of Order k Boolean Functions from AG-Codes

Propagation criteria and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1–4, 7, 8, 10, 11, 16]). Kurosawa, Stoh [8] and Carlet [1] gave a construction of Boolean functions satisfying PC(l) of order k from binary linear or nonlinear codes. In this paper, the algebraic-geometric codes over GF(2m) are used to modify the Carlet and Kurosawa-Satoh’s construction for giving vectorial resilient Boolean functions satisfying PC(l) of order k criterion. This new construction is compared with previously known results.     

The Mean-value of Meromorphic Functions with Respect to a Generalized Boolean Transformation

A formula for the mean-value distribution of certain meromorphic functions on a vertical line s = σ +iR under a generalized Boolean transformation, called rational Boolean transformation from R into itself, is derived using Birkhoff 's ergodic theorem. This formula is represented as a computable integral. Using the Cauchy's integral theorem, values of this integral corresponding to various possible cases are explicitly computed.     

Boolean transformations with unique fixed points

We determine the Boolean transformations F: B ⁿ → B ⁿ which have unique fixed points.      

Approximation of Boolean Functions by Local Search

Usually, local search methods are considered to be slow. In our paper, we present a simulated annealing-based local search algorithm for the approximation of Boolean functions with a proven time complexity that behaves relatively fast on randomly generated functions. The functions are represented by disjunctive normal forms (DNFs). Given a set of m uniformly distributed positive and negative examples of length n generated by a target function F(x ₁,...,x _n), where the DNF consists of conjunctions with at most literals only, the algorithm computes with high probability a hypothesis H of length m · such that the error is zero on all examples. Our algorithm can be implemented easily and we obtained a relatively high percentage of correct classifications on test examples that were not presented in the learning phase. For example, for randomly generated F with n = 64 variables and a training set of m = 16384 examples, the error on the same number of test examples was about 19% on positive and 29% on negative examples, respectively. The proven complexity bound provides the basis for further studies on the average case complexity.     

On Affine Normal Forms and a Classification of Homogeneous Surfaces in Affine Three-Space

We classify homogeneous surfaces in real and complex affine three-space. This is achieved by choosing affine coordinates so that the surface is defined by a function whose Taylor series is in a preferred normal form.     

Boolean Functions with Five Controllable Cryptographic Properties

The strict avalanche criterion (SAC) was introduced by Webster and Tavares [10] in a study of cryptographic design criteria. This is an indicator for local property. In order to improve the global analysis of cryptographically strong functions, Zhang and Zheng [11] introduced the global avalanche characteristics (GAC). The sum-of-squares indicator related to the GAC is defined as _f = _{v f} ²(v), where _f (v)=x (–1) ^f (x)f(x v). In this paper, we give a few methods to construct Boolean functions controlling five good cryptographic properties, namely balancedness, good local and GAC, high nonlinearity and high algebraic degree. We improve upon the results of Stanica [8] and Zhang and Zheng [11].     

Generating cryptographically strong Boolean functions using partial information

Periodica Mathematica Hungarica - In our paper we study the usage of partially defined Boolean functions (PDBFs) for generating cryptographically strong Boolean functions. A PDBF can be considered...     

On the coefficients of binary bent functions

We prove a 2-adic inequality for the coefficients of binary bent functions in their polynomial representations. The 2-adic inequality implies a family of identities satisfied by the coefficients. The identities also lead to the discovery of some new affine invariants of Boolean functions on .

     

Covering Sequences of Boolean Functions and Their Cryptographic Significance

We introduce the notion of covering sequence of a Boolean function, related to the derivatives of the function. We give complete characterizations of balancedness, correlation immunity and resiliency of Boolean functions by means of their covering sequences. By considering particular covering sequences, we define subclasses of (correlation-immune) resilient functions. We derive upper bounds on their algebraic degrees and on their nonlinearities. We give constructions of resilient functions belonging to these classes. We show that they achieve the best known trade-off between order of resiliency, nonlinearity and algebraic degree.     

Error Bounds of Constrained Quadratic Functions and Piecewise Affine Inequality Systems

We consider the error bounds for a piecewise affine inequality system and present a necessary and sufficient condition for this system to have an error bound, which generalizes the Hoffman result. Moreover, we study the error bounds of the system determined by a quadratic function and an abstract constraint.     

亏格为4黎曼曲面上循环群作用的拓扑分类

本文主要考虑循环群作用 Riemann曲面的分类问题 ,我们列出了所有的循环群作用亏格为 4Riem ann曲面的拓扑分类和弱拓扑分类     

随机迭代函数系统的仿射变换

对分形图形的一种构造方法——随机迭代函数系统,给出了确定一个随机迭代函数系统的原图像经过仿射变换后得到的新图像所对应的随机迭代函数系统的具体步骤,最后用平移、旋转、拉伸和对称变换的例子作了详细的说明.     

The completeness of the isomorphism relation for countable Boolean algebras

We show that the isomorphism relation for countable Boolean algebras is Borel complete, i.e., the isomorphism relation for arbitrary countable structures is Borel reducible to that for countable Boolean algebras. This implies that Ketonen's classification of countable Boolean algebras is optimal in the sense that the kind of objects used for the complete invariants cannot be improved in an essential way. We also give a stronger form of the Vaught conjecture for Boolean algebras which states that, for any complete first-order theory of Boolean algebras that has more than one countable model up to isomorphism, the class of countable models for the theory is Borel complete. The results are applied to settle many other classification problems related to countable Boolean algebras and separable Boolean spaces. In particular, we will show that the following equivalence relations are Borel complete: the translation equivalence between closed subsets of the Cantor space, the isomorphism relation between ideals of the countable atomless Boolean algebra, the conjugacy equivalence of the autohomeomorphisms of the Cantor space, etc. Another corollary of our results is the Borel completeness of the commutative AF -algebras, which in turn gives rise to similar results for Bratteli diagrams and dimension groups.

     

m值逻辑函数的多分块仿射逼近

文章定义了ｍ值逻辑函数在Ｄｚｎｍ上的Ｃｈｒｅｓｔｅｎｓｏｎ变换,并考察了这类变换的性质,在此基础上提出了对ｍ值逻辑函数进行多分块仿射逼近的方法,并分析了这种方法的优越性。特别地,重点给出了布尔函数的多分块仿射逼近,并用此方法得到了文献［２］所给出的最大相关子。