完全非线性函数的关键问题研究

项目名称： 完全非线性函数的关键问题研究

项目编号： No.60803154

项目类型： 青年科学基金项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 张习勇

作者单位： 中国人民解放军信息工程大学

项目金额： 18万元

中文摘要： 完全非线性函数可以抵抗差分攻击，也与一类相对差集密切相关，因而在密码学、组合数学等领域中具有重要的理论价值和应用价值。本课题首先研究完全非线性函数的刻画和构造，得到了许多不存在性结果，包括刻画了特征为p和2p的两个输入一个输出的完全非线性函数，给出了一种多输入多输出的四值完全非线性函数的新构造法和有限域上单变元的新二次完全非线性函数，构造了新的几乎完全非线性函数和新的高次低差分一致性函数。 其次，利用函数分解和降阶的方法，证明了Cusick2002年关于一类三次旋转对称布尔函数的重量和非线性度相等的猜想；证明了Cusick 关于初等对称函数的平衡性的2006年的猜想的部分情况；利用旋转对称布尔函数构造了偶数元最优代数免疫的函数；给出了二次旋转对称布尔函数的几种指数和计算方法。 最后，刻画和构造了许多具有"综合优良"密码学性质的密码学函数，包括确定了变元个数不超过6的拟Bent函数的代数结构，提出扩展组合函数族概念并得到了一种拟Bent函数的递归构造；给出了p值 k阶广义拟 Bent函数的循环谱的取值分布，得到了它们与仿射函数的符合率; 直接修改Bent函数构造高非线性的平衡函数。

中文关键词： 完全非线性函数；几乎完全非线性函数；旋转对称布尔函数；Bent函数；非线性度；

英文摘要： The study on perfect nonlinear functions is important in cryptography and combinatorics from not only the theoretic but the practical point of views. In this project, our results include： Firstly, we give many new results on the existences and constructions of perfect nonlinear functions, as well as its applications in cryptography. The details is listed as follows: 1. Study the existences and constructions of perfect nonlinear functions in Abelian groups with exponent p and 2p; 2. Present some new constructions of perfect nonlinear functions on Abelian groups with exponent 4 and perfect nonlinear functions of order 2 over finite fields; 3. Construct some new almost perfect nonlinear functions and some functions of ordr 3 with low differential uniformity. Secondly, prove the conjecture proposed by Cusick et al. on rotation symmetric boolean functions and partially prove the conjecture about balanced elementary symmetric boolean functions; Construct rotation symmetric boolean functions with optimum algebraic immunity; Propose some methods of evaluation of the exponential sum of rotation symmetric boolean functions of order 2. At last, characterize and construct some "overall excellent" cryptographic functions. We characterize the structures of quasi-bent functions in GF^n(2) where n<7. After introducing the concept of extended building functions (EBFs) in general finite Abelian groups, a recursion construction of Quasi-Bent functions and Bent functions are presented using the tool of EBFs; The spectrum distribution characteristics of kth-order generalized quasi-Bent functions over ring Zp is proposed, followed by the coincide ratio of such functions with all affine functions; Construct balanced boolean functions with high nonlinearity is given by adding bent function to the indicator function of its subset E．

英文关键词： perfect nonlinear functions; almost perfect nonlinear functions; rotation symmetric boolean functions; bent functions; nonlinearity;