非线性函数原像集和像集的组合性质

Nonlinear functions are key components of block ciphers like DES cryptosystems. Nonlinear functions with desired properties, such as low differential uniformity, have attracted much attention for the past few decades. The objective of this project is to investigate nonlinear functions in a combinatorial way: 1) to construct new difference sets or partial difference sets using the preimage sets and image sets of certain nonlinear functions; 2) to construct optimal difference system of sets, partitioned difference families from the preimage sets of some generalized nonlinear functions; 3) to try to find some new planar functions or APN functions. This project will use some standard methods in combinatorial designs, and is expected to develop some new techniques. Throughout this project, we concentrate on the combinatorial properties of the preimage and image sets rather than nonlinear functions themselves. Due to the close and natural relations to other objects including difference system of sets and difference families, this project is expected to contribute to not only the theory of combinatorial designs, but also to cryptography and communication systems.

非线性函数是分组密码等密码学系统的关键组成部分，多年以来，构造具有低差分一致性等相关特性的非线性函数一直是国际上的研究热点。本项目拟用组合方法对非线性函数原像集、像集的性质进行深入的研究：利用某些非线性函数的原像集、像集构造新的差集、部分差集等组合设计对象；用非线性函数相关函数的原像集构造集合差系统、差族等其它组合对象；探索构造新的平面函数、APN函数等非线性函数。本项目在采用近几年国际上证明差集性质方法的基础上，专注于通过原像集、像集的组合性质研究非线性函数，争取在组合性质的证明上有所突破和创新，同时紧密联系集合差系统、差族等其它组合对象，因而对组合设计、密码学、通信系统等领域均具有重要的理论意义和实际应用价值。

非线性函数是分组密码等密码学系统的关键组成部分，构造具有低差分一致性等相关特性的非线性函数一直是国际上的研究热点。本项目主要研究目标为对非线性函数原像集、像集的组合性质进行深入的研究：利用某些非线性函数的原像集、像集构造新的差集、几乎差集等组合设计对象；用非线性函数的原像集构造集合差系统、差族等其它组合对象；将非线性函数的原像集、像集的相关性质和结果应用于纠错编码、密码学、序列设计等领域中。本项目组成员较好完成了既定各项任务目标，并对相关研究任务有一定拓展，在国际知名期刊发表高水平论文5篇（SCI检索），会议发表论文1篇（EI检索），引起国内外相关领域研究者的广泛关注。相关研究工作包括：.1. 新型LDPC码的构造：由有限域上的对称矩阵空间构造了两类新的LDPC码，对这两类LDPC码的围长、维数、最小距离、阻止距离等参数，均进行了深入了研究。仿真结果表明，这两类LDPC码的中长码均具有优于随机LDPC码的优越性能。这是国际上首次在LDPC码的构造中引入矩阵几何的方法，从而极大的丰富了LDPC码的构造和参数多样性。这一结果发表在信息论、编码国际旗舰期刊IEEE Trans. Inform. Theory上；.2. 利用八阶分圆陪集构造了一类具有良好自相关值的四元随机序列，扩展了一类四元序列，并确定其它几类四元序列的线性复杂度。这一结果发表在Springer知名期刊Cryptography and Communications上；.3. 构造两大类非交换几乎差集：一是利用McFarland差集的相关思想，二是在Dihedral群中构造非交换几乎差集。后者的意义在于，在Dihedral群中猜想不存在差集，我们通过构造给出了Dihedral群存在几乎差集的肯定回答。该工作发表在Springer知名期刊Designs Codes and Cryptography上；.4. 系统研究了t几乎设计（t-adesign）的参数，并给出了一些构造：不同于t设计，t几乎设计不一定是(t-1)几乎设计。基于强正则图构造了一系列的3几乎设计，并证明他们也是2设计；同时系统讨论了t几乎设计的相关参数限制，给出了充分条件。该工作发表在Springer知名期刊Designs Codes and Cryptography上；.5. 完成了一篇关于差集、强正则图、低相关系列的调研论文。