Computation of Filtering Functions for Cryptographic Applications

Large Linear Complexity (LC) is a fundamental requirement for a binary sequence to be used in secret key cryptography. In this paper, a method of computing all the nonlinear filtering functions applied to a shift register with a linear complexity LC >= ((L)(k) + (L)(k-1)) , where L is the register's length and k the order of the filter, is proposed. Emphasis is on the simple algebraic operations (addition and shifting of functions) included in the calculations. The method formally completes the family of nonlinear functions whose filtered sequences satisfy the previous lower bound on LC. In cryptographic terms, it means an easy and useful way of designing sequence generators for cryptographic purposes.