Z/2n环上仿射函数Walsh谱的线性时间快速算法

"这篇论文是2011年3月发表在《上海交通大学学报》上的，由常亚勤和金晨辉合作完成，主要探讨了环Z/2n上仿射函数及其Walsh谱的快速计算算法。" 在密码学领域，线性密码分析是一种重要的密码算法评估方法，它通过研究密码系统的线性特性来评估其安全性。Walsh谱在密码分析中扮演着关键角色，特别是在检测密码系统中的线性关系方面。本文关注的是在模2n剩余类环Z/2n上的仿射函数，这类函数在密码学中广泛应用，如在构造布尔函数和流密码的设计中。 仿射函数是线性函数加上一个常数项，形式为f(x) = ax + b，其中a和b是环Z/2n的元素，x是变量。在环Z/2n上，由于二进制运算的特性，仿射函数的计算和分析具有特定的规律。进位函数是仿射函数的一个关键组成部分，它影响着函数的整体性质，包括其Walsh谱。 Walsh谱是衡量一个函数非线性程度的工具，对于二元函数f，其Walsh谱W_f(h)定义为所有输入对(x, x')的离散傅立叶变换，其中x和x'的异或结果为h。在密码分析中，较小的绝对值的Walsh系数通常意味着函数的线性性质更强，可能更容易受到线性攻击。 论文的核心贡献在于提出了一种新的快速算法，用于计算Z/2n上仿射函数的Walsh谱。传统方法的计算复杂度随变量规模n呈指数增长，而新算法则将这一复杂度降低到线性时间，大大提高了计算效率。这对于大规模密码系统的研究和分析具有重大意义，因为随着n的增长，快速计算Walsh谱的能力变得至关重要。 此外，论文还扩展了这个算法以处理多输出仿射函数，这些函数在实际密码系统中更常见，例如多变量公钥密码系统。多输出仿射函数的Walsh谱计算通常更为复杂，但新的算法同样能有效地处理这个问题。 通过实验验证，该算法在实际应用中显示出了显著的性能提升，不仅降低了计算资源的需求，还提升了分析速度，从而能够更有效地评估和设计安全的密码系统。这项工作对于理解和改进基于仿射函数的密码算法提供了有力的理论支持，并为后续的密码学研究提供了新的计算工具。