一种快速构造降次函数的新算法  

A new fast algorithm for constructing depressed functions

作　　者：陈杰[1] 胡予濮[1] 韦永壮[1] 

机构地区：[1]西安电子科技大学计算机网络与信息安全教育部重点实验室,陕西西安710071

出　　处：《西安电子科技大学学报》2005年第5期790-793,共4页Journal of Xidian University

基　　金：国家自然科学基金资助项目(60273084);高等学校博士点专项科研基金资助项目(20020701013);现代通信国家重点实验室基金项目(51436030105DZ0105)

摘　　要：基于密码函数分拆的思想提出了一种快速有效构造降次函数g的新算法.该算法通过每次选取不同变量进行分拆,在函数分解﹂k/2」次后建立方程组,最后通过求解此方程组得到满足条件的降次函数g.新算法可以求解代数次数至多为﹂k/2」的降次函数g,使得函数f*g的代数次数至多为「k/2﹁.该算法计算复杂度为O(2k/2)w+2,在k较大时,小于已有算法的计算复杂度O((2k-1)w).结果表明,在很低的计算复杂度下,能快速构造出降次函数g.This paper presents a new fast algorithm for constructing depressed functions g based on cryptographic functions splitting idea. By splitting different selected variables using the algorithm, we can construct a system of equations after [k/2] times of function decomposition and solving the system of equations will result in the depressed functions g. The degree of the functions g solved by this algorithm is at most [k/2] such that the degree of f＊ g is at most [k/2] . Its computational complexity is given as O（2^k/2）^w＋2 , which is lower than the computational complexity O（（2^k-1）^w） available when k is large. The result turns out that depressed functions g can be constructed in lower complexity.

关 键 词：代数攻击 计算复杂度 布尔函数 代数次数 

分 类 号：TN918.1[电子电信—通信与信息系统]