与Walsh-Hadamard变换相关的新变换：理论、方法及密码学应用

Walsh-Hadamard transform is a key tool for studying cryptographic functions. However, it only measures the correlation between a function and a linear function, which leads to a possible attack on such functions and hence have certain restrictions in applications. The project will study a new form of Walsh-Hadamard transform, namely q-transform. The q-transform measures the correlation between a function and another (linear or nonlinear) function. So it generalizes the Walsh-Hadamard transform that only measures the correlation between a function and linear functions. There are two main research topics in the project. One topic is to improve the mathematical theory of q-transform, which includes the computation, the mathematical expectation of q-transform and other mathematical problems. The other is to investigate cryptographic applications of q-transform systematically. We will discuss new cryptographic measures based on q-transform, such as q-bent functions, q-nearly bent functions, q-correlation immune functions and q-resilient functions. The applications of q-transform is very useful for designing secure cryptographic algorithms and resisting attacks. It has positive significance to enhance cryptographic primitives. We hope that the research can build a new system of the theory of q-transform and its Cryptographic Applications.

Walsh-Hadamard变换是研究密码函数一个关键的理论工具，但它仅能考量一个函数与线性函数的相关性，导致这类函数在应用中可能存在潜在的攻击。本项目拟研究一种与Walsh-Hadamard变换相关的新变换，即q-变换，它考量的是一个函数与另一函数（包括线性与非线性）的相关性。项目主要研究：一是完善q-变换的数学理论。涉及q-变换的计算问题、q-变换的数学期望及其它的数学问题，为其应用奠定理论基础。二是系统探索q-变换的密码学应用。讨论基于q-变换所定义的密码学新指标，如q-bent函数、q-nearly bent函数、q-相关免疫函数、 q-弹性函数等新概念。在相关安全密码算法的设计中，q-变换的应用将有助于选择具有更高密码强度的密码函数，以更有效地抵御密码攻击，因此在理论研究和实际应用上都具有积极的意义。希望通过项目的研究，初步建立关于q-变换理论及其密码学应用的新体系。

Walsh-Hadamard变换（离散傅立叶变换）是研究密码本原的一个重要的理论工具。本项目围绕Walsh-Hadamard变换，结合A. Klapper提出的q-变换，在布尔函数的设计分析、伪随机序列的设计与分析取得阶段性成果，主要有两个方面：..一是初步建立q-变换在密码学上的应用。深入讨论以q-变换定义的相关布尔函数特性，涉及q-bent函数、q-nearly bent函数、q-相关免疫函数等。（1）我们假设存在q-bent函数的前提下，证明了q-bent函数的自相关取值是三值的，并借助偏差集理论，解决了A.Klapper提出的公开问题：q-bent函数是不存在的；（2）我们证明了q-nearly bent函数的存在性及特性；（3）我们引进了q-相关免疫函数相关概念，并刻画了它的等价特性；（4）我们借助布尔函数的自相关的计算原理，给出了q-变换的计算算法，把q-变换与离散傅立叶变换关联起来。总体上，进一步完善了q-变换在密码学上的应用。q-变换对衡量一个函数的非线性逼近、研究高阶非线性度等问题更有优势。因此，它可以为密码函数的深入研究提供一个新思路，对提高密码本原（体制）的强度有积极的意义。..二是以离散傅立叶变换基本工具，深入研究伪随机序列的迹表示、线性复杂度、k-错线性复杂度等特性，涉及 Legendre序列、Ding-Helleseth-Lam序列、基于RSA模数的广义割圆序列、有限域上二次特征序列、费马-欧拉商序列等。（1）我们讨论了Legendre序列、Ding-Helleseth-Lam序列、基于RSA模数的广义割圆序列的迹表示；（2）我们讨论了费马-欧拉商序列的线性复杂度及其稳定性；（3）我们讨论了两类周期为p^2与2p^2的序列的稳定性；（4）我们讨论了几类离散对数序列的稳定性。研究成果进一步完善了序列密码理论，为序列的应用提供必要的理论支撑。. .本项目的研究，拓展了布尔函数的安全性分析，拓展了伪随机序列的研究与应用，在理论上有积极、重要的意义，也进一步完善了对称密码学的相关理论。项目成果在许多权威刊物发表，如IEEE Trans. Inform. Theory、SCIENCE CHINA Inform. Sci.、Designs, Codes and Cryptography等, 并得到国内外同行的认可及引用。