旋转对称布尔函数线性结构的公开问题解析

"这篇文章主要探讨了旋转对称布尔函数(linear structure)的两个公开问题，尤其是在具有不同代数次数的变量背景下。作者赵亚群和李旭分别在偶数变量和奇数变量的情况下，对布尔函数的线性结构进行了深入研究。他们证明了当布尔函数的代数次数为n-1时，对于偶数个变量的平衡旋转对称布尔函数不存在非零线性结构。同时，他们提供了代数次数为n-2时，对于奇数个变量的旋转对称布尔函数不存在非零线性结构的充分条件和必要条件。该研究涉及布尔函数、旋转对称性以及它们的代数度，对密码学和信息安全性等领域有着重要的理论意义。" 布尔函数是数字逻辑和计算机科学中的基础概念，它们将一组二进制输入映射到一个二进制输出。旋转对称布尔函数（RSBF）则是一种特殊类型的布尔函数，其在输入变量进行固定位数的循环移位后，函数值保持不变。这种函数在密码学中有着广泛的应用，因为它们可以提供良好的抗线性攻击和差分攻击的特性。 线性结构在布尔函数中指的是函数可以表示为输入变量的线性组合，通常与函数的非线性度相关。非零线性结构意味着函数不是完全线性的，具有一定的复杂性，这对于密码系统来说可能是有利的，因为它增加了破解的难度。 代数次数是布尔函数的一个重要属性，它表示函数可以表示为最小多项式次数。在本文中，代数次数n-1和n-2对应于函数的不同复杂度级别，分别对应偶数变量和奇数变量的情况。 文章解决了关于旋转对称布尔函数的两个关键问题：一是证明了当变量数量为偶数且代数次数为n-1时，这类函数没有非零线性结构，这意味着在这些函数中寻找线性关系是徒劳的；二是对于奇数变量和代数次数为n-2的情况，提供了充分和必要条件来判断是否存在非零线性结构，这对于理解和设计更安全的密码算法至关重要。 这项工作对理解旋转对称布尔函数的性质有深远影响，并可能启发新的密码设计策略。此外，通过深入研究这些函数的代数和结构特性，可能还会揭示其他未被发现的性质，为信息安全领域带来更多的理论支持和发展机遇。