布尔函数的迹Walsh谱

布尔函数线性Walsh谱和高阶Walsh谱的研究对构造能够抵抗线性逼近攻击和二次或较高次逼近攻击的密码函数发挥了重要作用.为了抵抗采样攻击,提出了布尔函数迹Walsh谱和迹Walsh循环谱概念,并给出该Walsh谱的一些简单性质.利用这一谱值的分布特性,可以很好地分析布尔函数的迹函数逼近问题,对序列密码采样攻击研究具有重要意义.     

具有特定非零Walsh谱值个数的布尔函数的研究及构造

布尔函数与其变元的相关性与流密码的相关攻击有紧密联系，Walsh变换则是研究布尔函数相关特性的主要工具，本文研究了非零Walsh谱值个数k=9，10的布尔函数，证明了k=9的函数的不存在性，并构造了所有k=10的函数。     

布尔函数Walsh变换的非零取值个数

设Wf(y)(y∈F2^r)是布尔函数f：F2^r→F2的Walsh变换．Sf为Wf(y)≠0的y个数，S为所有Sf的并集(其中f过所有可能的布尔函数)．决定集合S是通信和信息安全领域一个重要问题．本文利用群环工具给出研究这一问题的新方法．用这种方法以统一方式证明了[4]中的结果．并利用群环方法给出了关于集合S的一系列新结果．     

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

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.     

最优布尔函数的一个性质

Walsh谱只有3个值:0,±2m+2,且同时达到代数次数上界n-m-1和非线性度上界2n-1-2m+1的n元m阶弹性布尔函数(m>n/2-2)称为饱和最优函数(saturatedbest简写为SB).本文将给出关于SB函数非零谱值位置分布的一个性质,利用这一性质我们给出构造非线性度为56的4次7兀2阶弹性布尔函数的一种方法.     

布尔函数的密码性质

当前,密码学面临的一个挑战性问题是构造具有多种密码学性能的布尔函数,用来作为流密码和分组密码的密钥,以同时抵抗现有的多种破译和攻击方式。本文综述了近年来国内外在这方面的研究和进展。     

m值逻辑函数的谱分解式及广义Bent函数的递归构造

本文用概率方法得到ｍ值逻辑函数Ｃｈｒｅｓｔｅｎｓｏｎ循环谱的分解式,据此考察了ｍ值广义Ｂｅｎｔ函数一些新的性质,给出了递归构造ｍ（ｍ≠２ｍｏｄ４）值广义Ｂｅｎｔ函数的一般方法．     

Bent函数的一般构造法

本文用概率方法给出小项表示的布尔函数谱的性质,据此得到了Ｂｅｎｔ函数的特征矩阵的等价刻画,原则上给出了Ｂｅｎｔ函数的一般构造法,并为Ｂｅｎｔ函数的计数问题提供了一个模型。文中还提出了Ｂｅｎｔ矩阵的概念,考察了Ｂｅｎｔ矩阵的性质,并借助Ｂｅｎｔ矩阵得到由已知Ｂｅｎｔ函数构造新的Ｂｅｎｔ函数构造新的Ｂｅｎｔ函数的方法。     

关于两个P-值逻辑函数的和函数的Chrestenson谱公式

类似于两个布尔函数的和函数的ｗａｌｓｈ谱公式,本文给出了两个３－值、５－值、７－值逻辑函数和函数的Ｃｈｒｅｓｔｅｎｓｏｎ谱公式。     

广义部分Bent函数和广义Bent函数的关系

Bent函数是一类特殊的布尔函数,因其非线性性和稳定性在密码学和通信等领域有很重要的应用,但它们数量少,不平衡且无相关免疫性,为了弥补Bent函数的不足,Claud Carlet提出了部分Bent函数的概念,部分Bent函数是包含Bent函数的更大的函数类,后来,人们又将这两种函数概念先后都拓广到了环zm^n(m为正整数）上,分别被称为zm^n上的广义Bent函数和广义部分Bent函数,本文利用zp^n(p为素数）上广义部分Bent函数的Chrestenson循环谱特征讨论了zp^n上的广义部分Bent函数和广义Bent函数之间的关系,给出了这两种函数之间的函数关系式和谱值关系式。     

一类非线性弹性函数的构造

In this paper the decomposition formula of Walsh spectrum of boolean functions is used to construct a class of nonlinear resilient functions.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Several classes of even-variable 1-resilient rotation symmetric Boolean functions with high algebraic degree and nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, some classes of 2m-variable (m is an odd integer) 1-resilient rotation symmetric Boolean functions are got, whose nonlinearity and algebraic degree are studied. For the first time, we obtain 2m-variable 1-resilient rotation symmetric Boolean functions having high nonlinearity and optimal algebraic degree. In addition, we obtain a class of non-linear rotation symmetric 1-resilient function for every $n\ge 5$, and a class of quadratic rotation symmetric $(k?1)$-resilient function of $n=3k$ variables, where k is an integer.     

布尔函数的判定树复杂性及问题

设f（x₁,x₂,…,x_n）是一个布尔函数。如果计算f（x₁,x₂,…,x_n）的每个判定树算法在最坏情况下都要检查所有n个变量才能求得f的值,则称f是诡秘函数。1988年,A.C.C.Yao提出一个问题:如果一个单调非平凡的布尔函数f（x₁,x₂,…,x_n）在循环群C_m×C_n的直积的可迁作用下不变,则f是诡秘的吗?对这个问题的肯定回答支持著名的Rivest-Vuillemin猜想.本文将部分地解答这一问题.     

Walsh函数的一种新定义及快速算法设计

传统的Walsh函数是以Rademacher函数为基函数生成 .本文运用对称复制的观点 ,定义了一种新函数 G函数 ,并以G函数为基础 ,定义了四种序的Walsh函数 ,同时 ,运用序码分析方法 ,实现了两种序Walsh变换的快速算法设计 .     

Realization of Boolean functions by repetition-free formulas in a particular base

Siberian Mathematical Journal - Under study are the representations of Boolean functions by formulas. We offer a criterion for the Boolean functions to be repetition-free in the base {V,·,...     

Algorithmic aspects of the substitution decomposition in optimization over relations,set systems and Boolean functions

In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. This paper gives a broad treatment of a particular aspect of this approach, viz. the design of algorithms to compute the decomposition possibilities for a large class of discrete structures. The decomposition considered is thesubstitution decomposition (also known as modular decomposition, disjunctive decomposition, X-join or ordinal sum). Under rather general assumptions on the type of structure considered, these (possibly exponentially many) decomposition possibilities can be appropriately represented in acomposition tree of polynomial size. The task of determining this tree is shown to be polynomially equivalent to the seemingly weaker task of determining the closed hull of a given set w.r.t. a closure operation associated with the substitution decomposition. Based on this reduction, we show that for arbitrary relations the composition tree can be constructed in polynomial time. For clutters and monotonic Boolean functions, this task of constructing the closed hull is shown to be Turing-reducible to the problem of determining the circuits of the independence system associated with the clutter or the prime implicants of the Boolean function. This leads to polynomial algorithms for special clutters or monotonic Boolean functions. However, these results seem not to be extendable to the general case, as we derive exponential lower bounds for oracle decomposition algorithms for arbitrary set systems and Boolean functions.