Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)

Pseudonoise generators for cryptographic applications consisting of several linear feedback shift registers with a nonlinear combining function have been proposed as running key generators in stream ciphers. These running key generators eau sometimes be broken by (ciphertext-only) correlation attacks on individual subsequences. A new class of combining functions is presented, which provides better security against such attacks. The security is quantified by the smallest numberm + 1of subsequences that must be simultaneously considered in a correlation attack. A necessary condition for suchmth-order correlation-immunity is proved. A recursive construction is given that permits the construction of anmth-order immune combining function fornsubsequences for anymandnwith1 ≤ m < n. Finally, the trade-off between the length of the linear equivalent of the nonlinear generator and the ordermof its immunity against correlation attacks is considered.