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

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

项目编号： No.61502372

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

立项/批准年度： 2016

项目学科： 自动化技术、计算机技术

项目作者： 李雪莲

作者单位： 西安电子科技大学

项目金额： 22万元

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

中文关键词： 非线性度；覆盖半径；Walsh谱；指数和

英文摘要： 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.

英文关键词： Nonlinearity;Covering radii;Walsh spectrum;Exponential sum