Counting Boolean functions with faster points
Counting Boolean functions with faster points
复制标题
DOI：
10.1007/s10623-020-00738-7
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
A. Sălăgean;F. Özbudak
中科院分区：
文献类型：
--
作者：
A. Sălăgean;F. Özbudak
Duan和Lai对布尔函数引入了“快点”的概念，即函数是一个方向，使得在方向上的导数的代数次数严格低于期望值。他们的研究动机是这样一个事实，即快速点的存在使许多密码差分攻击（如立方体和AIDA攻击）更有效。Duan等人在某些特殊情况下确定了具有快点的函数的个数，而在一般情况下则由Süllergean和Mandache-Süllergean确定。我们推广了快点的概念，定义了一个阶的快点是一个快点，使得方向导数的次数至少比期望次数低。我们确定了一个显式公式的次数在nvariables有快速点的顺序。此外，我们确定的degreedinvariables的函数的数量有一个给定的数量的快速点的顺序，也有一个给定的配置文件的功能的数量方面的快速点的每一个订单。我们应用我们的结果来计算一个函数的概率有快速点的顺序。我们还计算了允许线性结构（即它们在某个方向上的导数是常数）的函数的数量;这些函数在对称密码的分析中有很长的历史。
Duan and Lai introduced the notion of “fast point” for a Boolean functionfas being a directionaso that the algebraic degree of the derivative offin directionais strictly lower than the expected. Their study was motivated by the fact that the existence of fast points makes many cryptographic differential attacks (such as the cube and AIDA attack) more efficient. The number of functions with fast points was determined by Duan et al. in some special cases and by Sălăgean and Mandache-Sălăgean in the general case. We generalise the notion of fast point, defining a fast point of orderas being a fast pointaso that the degree of the derivative offin directionais lower by at leastthan the expected degree. We determine an explicit formula for the number of functions of degreedinnvariables which have fast points of order. Furthermore, we determine the number of functions of degreedinnvariables which have a given number of fast points of order, and also the number of functions which have a given profile in terms of the number of fast points of each order. We apply our results to compute the probability of a function to have fast points of order. We also compute the number of functions which admit linear structures (i.e. their derivative in a certain direction is constant); such functions have a long history of being used in the analysis of symmetric ciphers.