对称密码中的非线性函数设计与分析

Nonlinear functions play a central role in symmetric cryptosystems. Because of the introduction of some new attacks, such as fast algebraic attacks, attacks on the nonlinear equivalence class and higher order algebraic attacks, there are no nonlinear functions satisfying all the cryptographic criteria. It is urgent to design secure Boolean functions and vectorial Boolean functions. Based on our previous work, we will generalize the method of constructing Boolean functions using primitive polynomials, and design some infinite classes of Boolean functions with all desired features: balancedness, high algebraic degree, high nonlinearity, high algebraic immunity, high fast algebraic immunity and all Boolean functions nonlinear equivalent to them also have good cryptographic properties. We will investigate further the construction of vectorial Boolean functions using extension fields, and construct some infinite classes of vectorial Boolean functions with good cryptographic properties: permutation, low differential uniformity, high nonlinearity, high algebraic degree and good behavior against algebraic attacks. We will analyze these functions in detail, and particularly, investigate their ability to resist higher order algebraic attacks. Moreover, we will establish a complete theory of higher order algebraic attacks, and prove that some classes of Boolean functions proposed by others are weak against higher order algebraic attacks. Accomplishment of this project can provide nonlinear functions with all desired features which can be used to design secure stream ciphers and block ciphers.

非线性函数在对称密码中起着至关重要的作用。由于快速代数攻击、非线性等价攻击和高阶代数攻击等新兴攻击方法的引入，目前已没有一类非线性函数能被证明具有所有必要的密码性质，设计安全的布尔函数和向量值函数是亟待解决的重要课题。本课题将在原有工作基础上，把利用本原多项式构造布尔函数的方法进行推广，设计几类布尔函数具有所有必要的密码性质：平衡、高的代数次数、高的非线性度、高的代数免疫、高的快速代数免疫且所有与其非线性等价的布尔函数亦具有好的密码性质。我们还将深入研究利用扩域构造向量值函数的方法，构造几类具有好的密码性质的向量值函数：置换、低的差分均匀度、高的非线性度、高的代数次数以及好的抵制代数攻击的能力，我们会对这些非线性函数进行详细分析，特别研究其抵制高阶代数攻击的能力。本课题的完成，将构造出具有所有必要性质的布尔函数和向量值函数，从而可以用来设计安全的序列密码和分组密码。

非线性布尔函数在对称密码中起着至关重要的作用。本项目重点研究了序列密码中布尔函数和分组密码中向量布尔函数的设计与分析，取得了一系列成果，完成了专著一本，英文论文十余篇，其中已有9篇论文接受或发表。现将结果主要概括如下：.（1）提出了几种构造布尔函数的新方法，构造了几类具有好的密码性质的布尔函数，并在其它性质保持最优的情况下，导出了迄今为止最好的非线性度下界。.（2）首次将Hidden weighted bit function引入密码学领域，并证明其具有非常好的密码性质，这是首个具有好的密码性质且极易于软硬件实现的布尔函数。基于hwbf，我们又构造出了更多极易于软硬件实现且密码性质比hwbf 更好的布尔函数。.（3）前人所构造的布尔函数存在一个共同的问题，即当变元数目多于20 时，很难进行软硬件实现。而密码学界一般认为，布尔函数的变元数目至少要达到25，才会比较安全。如何构造真正实用的布尔函数，是一个多年来的开放性问题。本项目首次提出了一种系统的方法来构造具有好的密码性质且可对大变元数目进行软硬件实现的布尔函数，该方法可提供大量能实际应用于序列密码设计的布尔函数。.（4）构造了几类差分均匀度为4的置换，其与已知函数CCZ不等价，且具有最优代数次数和相对高的非线性度。.本项目的成果促进了布尔函数研究领域的发展，并可用来设计安全的序列密码和分组密码，具有极大的科学意义和应用价值。