Research On The Algebraic Attack On Stream Ciphers With Multi-outputs

Algebraic attack is one of the focuses in the cryptography nowadays. In this paper we will study the algebraic attack on stream ciphers with several outputs deeply, our contributions mainly include the following three parts:1. We study the annihilator functions of multi-outputs Boolean function. We give the algebraic structure of the set of annihilator functions, prove that the set of annihilator functions of multi-outputs Boolean function is equal to the set of annihilator of combinatorial function of component functions; analyze the method of finding annihilator of Boolean function in [19], present two methods of finding annihilator functions of multi-outputs Boolean function.2. We study the algebraic immunity of multi-outputs Boolean function. We show the relation of three algebraic immunity, prove that the algebraic immunity of annihilator functions is equal to the algebraic immunity of combinatorial function of component functions; show the relationship between algebraic immunity and other cryptographic properties, such as balance and nonlinearity; prove that the upper bound algebraic immunity of n-inputs m-outputs Boolean function is [(n-1)/2]; analyze the method of computing the algebraic immunity in [35], present a method of computing the algebraic immunity of multi-outputs function.3. We study the algebraic attack on stream ciphers with linear feedback. We give the method of algebraic attack on stream ciphers with multi-outputs using the annihilator function; using the relativity between inputs of Boolean function in stream with linear feedback of different clock, convert Boolean function to multi-outputs Boolean function, and find low-degree functions about the key using annihilator functions, thereby gain the improved algebraic attack on stream ciphers with linear feedback. Finally, we analyze the computational complexity of our attack which is better than the algebraic attack in [14], and in some stream ciphers with linear feedback, our attack is better than fast algebraic attack, and test the result by computer simulations; the memory complexity and the computation complexity of our attack on simplified version of LILI-128 are equal to fast algebraic attack, but the date complexity is much lower.