Efficient Probabilistic Algorithm for Estimating the Algebraic Properties of Boolean Functions for Large n
Efficient Probabilistic Algorithm for Estimating the Algebraic Properties of Boolean Functions for Large n
复制标题
估计大 n 布尔函数代数性质的高效概率算法
DOI：
10.1016/j.ins.2017.03.025
复制
发表时间：
2017-09
影响因子：
8.1
通讯作者：
Samir Hodzic
中科院分区：
文献类型：
--
作者：
Yongzhuang Wei;Enes Pasalic;Fengrong Zhang;Samir Hodzic
Although several methods for estimating the resistance of a random Boolean function against (fast) algebraic attacks were proposed, these methods are usually infeasible in practice for relatively large number of input variablesn(for instancen≥ 30) due to increased computational complexity. An efficient estimation of the resistance of Boolean functions, with relatively large number of inputsn, against (fast) algebraic attacks appears to be a rather difficult task. In this paper, the concept of partial linear relations decomposition is introduced, which decomposes any given nonlinear Boolean function into many linear (affine) subfunctions by using the disjoint sets of input variables. Based on this result, a general probabilistic decomposition algorithm for nonlinear Boolean functions is presented which gives a new framework for estimating the resistance of Boolean function against (fast) algebraic attacks. It is shown that our new probabilistic method gives very tight estimates (lower and upper bound) and it only requires aboutO(n22n) operations for a random Boolean function withnvariables, thus having much less time complexity than previously known algorithms.
登录
查看更多内容
高度非线性布尔函数和不相交谱平台函数的二次构造
影响因子：
8.1
作者：
Fengrong Zhang;Claude Carlet;Yupu Hu;Tianjie Cao
通讯作者：
Tianjie Cao
提高 1 弹性布尔函数最大非线性下限并设计满足所有密码标准的函数
影响因子：
8.1
作者：
Zhang WeiGuo;Pasalic Enes
通讯作者：
Pasalic Enes
DOI：
--
发表时间：
2014
期刊：
--
影响因子：
--
作者：
Sihem Mesnager
通讯作者：
Sihem Mesnager
DOI：
10.1007/978-3-642-34961-4_12
发表时间：
2012-12
期刊：
--
影响因子：
--
作者：
Meicheng Liu;Yin Zhang;D. Lin
通讯作者：
Meicheng Liu;Yin Zhang;D. Lin
DOI：
10.1007/978-3-540-89255-7_26
发表时间：
2008-12
期刊：
--
影响因子：
--
作者：
C. Carlet;K. Feng
通讯作者：
C. Carlet;K. Feng