《SoftwareX》：SBoxQUBOSearch: Exhaustive subset search and local basis optimization for exact algebraic S-box models
编辑推荐：
替换盒（S-box）为密码算法提供非线性特性，其代数表示直接影响密码分析模型的规模。SBoxQUBOSearch是一个C++17软件包，用于为制表型S盒生成显式与隐式关系，仅对生成的关系基中固定大小的子集进行穷举搜索，并对等价基进行启发式优化。其目标函数用于估
替换盒（S-box）为密码算法提供非线性特性，其代数表示直接影响密码分析模型的规模。SBoxQUBOSearch是一个C++17软件包，用于为制表型S盒生成显式与隐式关系，仅对生成的关系基中固定大小的子集进行穷举搜索，并对等价基进行启发式优化。其目标函数用于估计S盒方程系统中辅助变量的数量，该系统用于整个密码算法的二次无约束二元优化（QUBO）模型。该软件既不构造QUBO矩阵，也不求解QUBO问题。带版本管理的JSON/JSONL文件、可复现的任务流程以及免通信的分区机制共同保障了实验的可复现性。在AES、Ascon、ARADI与MK3上的实验验证了完整工作流；DES仅用于演示方程生成（eqgen）过程。该工作流将Ascon的估计辅助变量数从110降至17，最终得到五方程系统；将MK3的估计辅助变量数从1014降至501，最终得到28方程系统；将ARADI的估计辅助变量数从71降至8，最终得到四方程系统。
在密码学中，替换盒（S-box）是许多分组密码与轻量级密码中非线性性的主要来源。S盒的代数表示直接决定了整个密码算法代数模型的规模与结构，因为描述单个S盒的方程会在其每次出现时被复制。因此，寻找更紧凑、更高效的S盒方程系统，对于构建更小规模的密码分析模型具有重要意义。
目前存在的主要问题是：显式代数正规型（ANF）方程虽然能完整描述S盒，但并不总是对后续建模最有利。在布尔环中，同一S盒可以用多种不同的隐式关系系统来描述，而不同系统所需的辅助变量数量差异巨大，直接影响二次无约束二元优化（QUBO）模型的求解难度与规模。然而，如何系统地搜索并优化这些等价关系基，缺乏自动化工具支持。
针对上述问题，研究人员开发了SBoxQUBOSearch，一个C++17软件包，用于自动生成S盒的显式与隐式关系，对生成的关系基中固定大小的子集进行穷举搜索，并通过启发式方法优化等价基。该工具的目标函数用于估计S盒方程系统在整密码算法QUBO模型中所需要的辅助变量数量，从而指导选择最优的方程系统。它不直接构造或求解QUBO矩阵，而是为后续建模提供最优的代数输入。
研究在AES、Ascon、ARADI和MK3四种密码算法上验证了完整工作流，在DES上仅演示方程生成功能。结果显示，该工作流将Ascon的估计辅助变量数从110降至17，最终得到一个五方程系统；将MK3的估计辅助变量数从1014降至501，最终得到一个28方程系统；将ARADI的估计辅助变量数从71降至8，最终得到一个四方程系统。这些结果显著缩小了S盒代数模型的规模，证明了该方法在多种密码结构上的有效性与通用性。
研究人员采用的主要关键技术方法包括：第一，关系生成（eqgen），从制表型S盒自动生成显式ANF方程与隐式关系；第二，固定大小子集的穷举搜索，在生成的关系基中系统枚举所有候选子集，以寻找满足唯一描述S盒条件的最小方程系统；第三，局部基优化，通过启发式策略对等价基进行变换与优化，进一步降低辅助变量估计数；第四，目标函数设计，以估计辅助变量数量为核心评价指标，用于比较不同候选方程系统的优劣；第五，可复现性保障机制，采用版本化JSON/JSONL文件、可复现任务流程与免通信分区，确保实验结果的可验证性。
在实验结果部分，研究分别针对各密码算法进行了验证。对于Ascon，研究人员通过完整工作流，将估计辅助变量数从110降至17，最终得到一个五方程系统，显著压缩了S盒的代数表示。对于MK3，研究人员将估计辅助变量数从1014降至501，最终得到一个28方程系统，展示了该方法在大规模S盒上的压缩能力。对于ARADI，研究人员将估计辅助变量数从71降至8，最终得到一个四方程系统，进一步验证了方法的普适性。对于AES，研究验证了完整工作流的可行性，确认了工具在经典密码结构上的适用性。对于DES，研究人员仅演示了方程生成功能，展示了工具对非双射、输入输出宽度不等的S盒的处理能力。
在讨论部分，研究人员指出，S盒方程系统的选择对后续QUBO建模的规模有决定性影响，而辅助变量数量是衡量模型紧凑性的关键指标。通过穷举子集搜索与局部基优化的结合，能够在可接受的计算代价内找到显著更优的方程系统。版本化文件与可复现任务流程的设计，为密码分析社区提供了可靠的实验基础。
研究结论部分表明，SBoxQUBOSearch提供了一种系统化的方法，用于自动搜索和优化S盒的代数表示，显著降低了多个密码算法S盒模型的辅助变量估计数量。该方法不依赖具体密码结构，适用于多种S盒类型，为后续基于QUBO的密码分析建模提供了高效、可复现的工具支持。
