高度非线性函数的性质、构造与应用

高度非线性函数是设计序列密码、分组密码和Hash函数的重要组件，本项目主要研究有限域上高度非线性函数的性质、构造与应用。以代数学、有限几何和组合设计的理论与方法为工具，给出完全非线性函数(PN函数)和几乎完全非线性函数(APN函数)新的理论刻画，寻找新的PN函数和APN函数，试图部分或者全部回答"大APN问题"和"Dobbertin猜测"；提出高度非线性函数CCZ等价不变量的有效计算方法，特别是扩展Walsh谱的计算方法，研究已有的不同形式的PN函数或APN函数之间的等价性，解决目前关于高度非线性函数等价性方面的一些遗留问题。以有限域、纠错编码和扩频通信的理论与方法为工具，决定基于PN函数和APN函数所构造的线性码的参数性能、权分布和覆盖结构，计算基于PN函数和APN函数所构造的跳频码的Hamming相关函数，给出m序列互相关函数的一些新的理论刻画。

本项目主要研究有限域上高度非线性函数的性质、构造与应用。由于密码算法的安全性分析是密码函数研究的起源和推动力，项目组在深入高度非线性函数研究的同时，也对密码算法的安全性分析方面展开了研究。项目执行期间，项目组在高度非线性函数的构造与应用、低差分函数的构造、高代数免疫度函数的构造、差分密码分析和积分分析的基础理论研究、国际著名密码算法的安全性分析等方面取得了一系列研究成果，在《IEEE Trans. on Inform. Theory》、《Design, Codes and Crypt.》、《Finite Fields & Their Appl.》等国内外著名学术期刊和FSE、SETA等国内外著名学术会议上共发表学术论文37篇，其中SCI论文23篇，EI论文13篇，超额完成了项目研究任务。下面分两方面对最重要的一些研究成果做简要概述。在高度非线性函数的性质、构造与应用方面，使用交换构造法构造了偶扩张上大量的CCZ不等价的具有最优代数次数、很高非线性度的4-差分置换类，极大地扩展了该类函数，为对称密码算法S盒的构造提供了更多选择；构造了多类具有高代数免疫度，高非线性度，高（或最优）代数次数的平衡向量值函数，在某些情况下，所构造函数的代数免疫度也达到最优；构造了一大类APN函数，并计算了它们的Walsh谱，解决了一个相关猜想；构造了多类Semi-bent函数和多类具有高非线性度的MAI函数；将CCZ等价和EA等价推广到一般交换群上，并给出了它们关系的一些新结果；首次给出有限域上函数差分均匀度取值的完全刻画等。在密码算法的安全性分析方面，给出了对SPN结构的不可能差分分析、积分区分器的扩展、MISTY结构可证明安全等密码分析基础理论方面的一些新结果；使用不可能差分攻击、中间相遇攻击、积分攻击等方法分析了CLEFIA算法、ARIA算法、Zodiac算法等，均取得了对于相应简化轮数算法的最好攻击结果；给出了对海事卫星电话中GMR-2加密算法的一种新的攻击，其在所有攻击方法中具有最低数据复杂度等。