h=g_g布尔函数的星积分解：新算法与挑战

本文主要探讨了"串联结构的h=g∗g型布尔函数的星积分解"这一主题，它聚焦于密码学领域中的一个关键概念——非线性反馈移位寄存器(Neural Feedback Shift Register, NFSR)的串联结构。NFSR是序列密码设计中常用的构造之一，如Grainv1、Grain-128、Grain-128a、Sprout和Fruit等算法都利用了这种结构。1970年，Green等美国学者提出通过布尔函数的星积运算将NFSR的特性与特征函数的星积运算关联起来，从而简化了对NFSR结构的研究。 特征函数的星积分解是一个重要的理论问题，因为它不仅与实际密码分析密切相关，而且具有挑战性。然而，目前已有高效分解算法主要适用于含有线性布尔函数的情况。本文的创新之处在于，在g的值未知的情况下，针对两种特定情形提出了求解g的算法。 首先，对于一类情况，作者运用布尔函数求偏导降次的方法，将g∗g的分解问题转换为处理线性布尔函数l与g的乘积l∗g，这便于利用现有的高效分解技术求解g。这种方法巧妙地将复杂问题简化，使得计算更为高效。 其次，针对另一类情形，作者构建了一个关于布尔函数求偏导的函数方程，并利用按次数“分层剥离”的策略，逐次求出g的各个系数g[d], g[d-1],…, g[1]，最终得到g。这个过程同样将g的k次项分解为线性部分l∗g[k]，从而实现分解目标。 此外，文章还探讨了星积分解在刻画特征函数之间“接近性”方面的应用，将处理两个“接近”特征函数的星积分解问题转化为原始的h=g∗g类型问题。这不仅扩展了星积分解的研究范围，也为理解和分析类似布尔函数提供了新的视角。 总结来说，本文的核心贡献是提出了在g未知情况下处理h=g∗g型布尔函数的星积分解的高效算法，这对于深入理解NFSR结构和密码分析有着重要的理论价值。关键词包括序列密码、非线性反馈移位寄存器、NFSR的串联结构以及h=g∗g型星积分解，这些关键词有助于读者定位和检索相关研究。该研究成果发表在《密码学报》上，为密码学理论和实践提供了新工具和技术支持。