h=g*g型布尔函数的星积分解

On*product Decomposition of Boolean Functions in Form h=g*g

串联结构是非线性反馈移位寄存器(简称NFSR)结构研究中的一种重要模型,已应用于许多密码算法的设计中,如Grain v1、Grain-128、Grain-128a、Sprout、Fruit等.1970年,美国学者Green等人通过引入布尔函数的星积运算,将NFSR的串联结构与特征函数的星积运算一一对应,使得对NFSR的串联结构研究本质上可以转化为对特征函数的星积性质研究.特征函数的星积分解是一个兼具理论和现实意义的问题,同时也是一个富有挑战性的问题,截至目前仅对分解中含有线性布尔函数的情形有较高效的分解算法.本文研究在g未知的条件下,如何由h=gg来求解g.针对两类情形,我们分别给出了求取g的高效算法.在第一类情形中,基于对布尔函数求偏导降次的思想,我们将g*g的分解问题转化为l*g的分解问题,其中l是线性布尔函数,进而利用现有的高效分解算法求得g.在第二类情形中,我们首先构建关于布尔函数求偏导的函数方程,然后利用按次数进行“分层剥离”的思想依次求取g[d];g[d-1];……;g[1],从而最终求取g,其中g[k]是g中所有k次项之和,d=deg(g).上述g[k]的求取也是转化为l*g[k]的分解来实现.此外,本文从星积分解的角度给出了两个特征函数较为“接近”的一种刻画,并将较为“接近”的特征函数的星积分解问题转化为h=g*g的星积分解问题.

As an important model of nonlinear feedback shift registers(NFSRs),the cascade connection of NFSRs has been used in the design of many cryptographic algorithms,such as Grain v1,Grain-128,Grain-128a,Sprout,Fruit,etc.In 1970,a new operation of Boolean functions called*product was introduced by Green et al.It is shown that there is a one-to-one correspondence between the cascade connection of NFSRs and the*-product of characteristic functions of NFSRs.Therefore,the research on the cascade connection of NFSRs can essentially be transformed into that on the properties of*-product of characteristic functions.The*-product decomposition of characteristic functions is an important and challenging problem,which has theoretical and practical significance.So far,an efficient decomposition algorithm is found only for the case where the decomposition contains a linear Boolean function.This paper studies how to recover g from h=g*g provided that h is known while g is unknown.Efficient decomposition algorithms are given for two cases.In the first case,based on the idea of reducing the degree of Boolean functions with some suitable partial derivatives,the decomposition of g*g is transformed into the decomposition of l*g,where l is a linear Boolean function,and then g is recovered by the decomposition of l*g.In the second case,an equation associated with g is given,and then g[d];g[d-1];……;g[1]is recovered,where g[k]is the sum of all terms of g with degree k and d=deg(g).The recovery of g[k]is also transformed into the decomposition of l*g[k].In addition,a description is given for two characteristic functions f and g who are“close”from the perspective of the*-product decomposition,and then the decomposition of f*g is converted into that of g*g.