Abstract: 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(2k/2)w+2, which is lower than the computational complexity O((2k-1)w) available when k is large. The result turns out that depressed functions g can be constructed in lower complexity.

Key words: algebraic attacks, computational complexity, Boolean functions, algebraic degree