Skip to main content
placeholder image

On constructions and nonlinearity of correlation immune functions

Chapter


Abstract


  • A Boolean function is said to be correlation immune if its output leaks no information about its input values. Such functions have many applications in computer security practices including the construction of key stream generators from a set of shift registers. Finding methods for easy construction of correlation immune functions has been an active research area since the introduction of the notion by Siegenthaler. In this paper we study balanced correlation immune functions using the theory of Hadamard matrices. First we present a simple method for directly constructing balanced correlation immune functions of any order. Then we prove that our method generates exactly the same set of functions as that obtained using a method by Camion, Carlet, Charpin and Sendrier. Advantages of our method over Camion et al’s include (1) it allows us to calculate the nonlinearity, which is a crucial criterion for cryptographically strong functions, of the functions obtained, and (2) it enables us to discuss the propagation characteristics of the functions. Two examples are given to illustrate our construction method. Finally, we investigate methods for obtaining new correlation immune functions from known correlation immune functions. These methods provide us with a new avenue towards understanding correlation immune functions.

Publication Date


  • 1994

Citation


  • Seberry, J., Zhang, X. M., & Zheng, Y. (1994). On constructions and nonlinearity of correlation immune functions. In Unknown Book (Vol. 765 LNCS, pp. 181-199). doi:10.1007/3-540-48285-7_16

International Standard Book Number (isbn) 13


  • 9783540576006

Scopus Eid


  • 2-s2.0-85007446434

Web Of Science Accession Number


Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 181

End Page


  • 199

Abstract


  • A Boolean function is said to be correlation immune if its output leaks no information about its input values. Such functions have many applications in computer security practices including the construction of key stream generators from a set of shift registers. Finding methods for easy construction of correlation immune functions has been an active research area since the introduction of the notion by Siegenthaler. In this paper we study balanced correlation immune functions using the theory of Hadamard matrices. First we present a simple method for directly constructing balanced correlation immune functions of any order. Then we prove that our method generates exactly the same set of functions as that obtained using a method by Camion, Carlet, Charpin and Sendrier. Advantages of our method over Camion et al’s include (1) it allows us to calculate the nonlinearity, which is a crucial criterion for cryptographically strong functions, of the functions obtained, and (2) it enables us to discuss the propagation characteristics of the functions. Two examples are given to illustrate our construction method. Finally, we investigate methods for obtaining new correlation immune functions from known correlation immune functions. These methods provide us with a new avenue towards understanding correlation immune functions.

Publication Date


  • 1994

Citation


  • Seberry, J., Zhang, X. M., & Zheng, Y. (1994). On constructions and nonlinearity of correlation immune functions. In Unknown Book (Vol. 765 LNCS, pp. 181-199). doi:10.1007/3-540-48285-7_16

International Standard Book Number (isbn) 13


  • 9783540576006

Scopus Eid


  • 2-s2.0-85007446434

Web Of Science Accession Number


Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 181

End Page


  • 199