密码函数二阶非线性度快速算法及其紧下界研究

The second order nonlinearity of Boolean functions is an important measurement indicator in the security analysis of stream cipher and block cipher. On the other hand, the second order nonlinearity has a close connection with the covering radii of Reed-Muller codes. Currently, a fast algorithm to calculate the second order nonlinearity is precious, and for an arbitrary cryptographic function, it is also a difficult task to give its sharp lower bound. The main research contents are as follows. 1) We will investigate the sharp lower bound on the second order nonlinearity of Boolean functions with high nonlinearity, by using the continuously recursive method and combing the exponential sum and the list decoding techniques of Reed-Muller codes. We will try to give the new theoretical method to prove the sharp lower bound of the second order nonlinearity. 2) We will design a fast algorithm to compute the second order nonlinearity by considering an improved iterated divided and conquer method and combing the discrete transformation and the solving equations. 3)We will study the covering radii of the second order Reed-Muller codes by analyzing some specific functions, and further study the covering radii of arbitrary order Reed-Muller codes by employing the iterated directional derivatives. The aim of this project is to propose a new method to prove the sharp lower bound and a new algorithm to calculate the second order nonlinearity. Our results will provide a theoretical support and a security guarantee for the design of cryptosystems and their applications.

布尔函数的二阶非线性度在评估流密码和分组密码的安全性方面有非常重要的作用，同时二阶非线性度也和二阶Reed-Muller码的覆盖半径密切相关。当前缺少计算二阶非线性度的快速算法，并且对任意一个布尔函数，给出二阶非线性度紧下界也是困难的。本项目主要研究内容包括：1）利用逐次递归方法，指数和与Reed-Muller码列表译码结合方法研究具有高非线性度密码函数的二阶非线性度紧下界；试图给出证明二阶非线性度紧下界的新型理论方法。2）利用改进的迭代分别征服方法和离散变换与解方程结合法研究二阶非线性度的快速算法；3）利用特定函数分析法研究二阶Reed-Muller码的覆盖半径，并利用迭代方向导数扩展研究任意阶Reed-Muller码的覆盖半径。力图给出证明高次密码函数二阶非线性度紧下界的新方法以及计算密码函数二阶非线性度的快速算法，为密码及其应用方案的设计提供系统的理论支撑和安全保证。

密码函数的非线性度是衡量目标函数与仿射函数类的距离。随着计算技术的不断进步，人们发现某些易解的二次函数组成的方程组也可能存在快速求解算法。这使得人们开始关注密码函数与二次函数及仿射函数的距离，即密码函数的二阶非线性度。本项目针对密码函数的二阶非线性度及其下界展开研究。针对特定类型的密码函数给出其二阶非线性度下界，研究了密码函数在区块链，安全多方计算以及多线性映射中的应用。项目取得研究成果：已发表或录用SCI或EI检索学术论文14 篇；申请8项国内专利，已经授权3项。重要结果：1）在密码函数二阶非线性度方面，针对四次Bent和半Bent函数（这些函数由法国密码学家Charpin等提出，具有较好的非线性度）采用了分别征服方法，基于二次型和迹函数给出了这些函数所有导数的非线性度的下界。最后给出了这类四次函数的二阶非线性度下界。与此同时，我们给出了这些函数有最佳二阶非线性度的条件，并给出了达到该条件的函数类。这些结果表明此类布尔函数具有较好的二阶非线性度，能够抵抗二次逼近攻击。2）针对下一代密码算法中使用的多线性映射提出了一种新的攻击方法。其中利用了布尔逻辑提出了一种称为 “downgrading” 的攻击方法,使攻击者能够从一个高级编码得到一个低级编码。攻击者可以在CDH假设下攻击多线性映射。除此之外，这种方法对属性加密的身份基聚合签名都是有效的。这种方法可以分析基于多线性映射构造的密码算法的潜在安全弱点。3）原计划中希望采用的寻找密码函数的二阶非线性度快速方法并不奏效，还需要寻找其他替代方法展开相关研究。另外，原计划中计划使用Reed-Muller码覆盖半径计算密码函数的二阶非线性度及其下界的方法，对于特殊类型的函数是起作用的，但通常会得到一些与编码方面的平行结果。本项目的结果对于密码函数在密码算法设计和分析以及其应用具有一定的指导意义。