Skip to main content
placeholder image

Nonlinearly balanced boolean functions and their propagation characteristics

Chapter


Abstract


  • Three of the most important criteria for cryptographically strong Boolean functions are the balancedness, the nonlinearity and the propagation criterion. This paper studies systematic methods for constructing Boolean functions satisfying some or all of the three criteria. We show that concatenating, splitting, modifying and multiplying sequences can yield balanced Boolean functions with a very high nonlinearity. In particular, we show that balanced Boolean functions obtained by modifying and multiplying sequences achieve a nonlinearity higher than that attainable by any previously known construction method. We also present methods for constructing highly nonlinear bidanced Boolean functions satisfying the propagation criterion with respect to all but one or three vectors. A technique is developed to transform the vectors where the propagation criterion is not satisfied in such a way that the functions constructed satisfy the propagation criterion of high degree while preserving the balancedness and nonlinearity of the functions. The algebraic degrees of functions constructed are also discussed, together with examples illustrating the various constructions.

Publication Date


  • 1994

Citation


  • Seberry, J., Zhang, X. M., & Zheng, Y. (1994). Nonlinearly balanced boolean functions and their propagation characteristics. In Unknown Book (Vol. 773 LNCS, pp. 49-60). doi:10.1007/3-540-48329-2_5

International Standard Book Number (isbn) 13


  • 9783540577669

Scopus Eid


  • 2-s2.0-84961389779

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


  • 49

End Page


  • 60

Abstract


  • Three of the most important criteria for cryptographically strong Boolean functions are the balancedness, the nonlinearity and the propagation criterion. This paper studies systematic methods for constructing Boolean functions satisfying some or all of the three criteria. We show that concatenating, splitting, modifying and multiplying sequences can yield balanced Boolean functions with a very high nonlinearity. In particular, we show that balanced Boolean functions obtained by modifying and multiplying sequences achieve a nonlinearity higher than that attainable by any previously known construction method. We also present methods for constructing highly nonlinear bidanced Boolean functions satisfying the propagation criterion with respect to all but one or three vectors. A technique is developed to transform the vectors where the propagation criterion is not satisfied in such a way that the functions constructed satisfy the propagation criterion of high degree while preserving the balancedness and nonlinearity of the functions. The algebraic degrees of functions constructed are also discussed, together with examples illustrating the various constructions.

Publication Date


  • 1994

Citation


  • Seberry, J., Zhang, X. M., & Zheng, Y. (1994). Nonlinearly balanced boolean functions and their propagation characteristics. In Unknown Book (Vol. 773 LNCS, pp. 49-60). doi:10.1007/3-540-48329-2_5

International Standard Book Number (isbn) 13


  • 9783540577669

Scopus Eid


  • 2-s2.0-84961389779

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


  • 49

End Page


  • 60