Skip to main content
placeholder image

Structures of cryptographic functions with strong avalanche characteristics

Chapter


Abstract


  • This paper studies the properties and constructions of nonlinear functions, which are a core component of cryptographic primitives including data encryption algorithms and one-way hash functions. A main contrilMtion of this paper is to reveal the relationship between nonlinearity and propagation characteristic, two critical indicators of the cryptographic strength of a Boolean function.In particular, we prove that (i) if f, a Boolean function on Vn, satisfies the propagation criterion with respect to all but a subset R of vectors in Vn, then the nonlinearity of f satisfies Nf ≥ 2 n-1-21/2(n+t)-1, where t is the rank of R, and (ii) When |R| > 2, the nonzero vectors in R are linearly dependent. Furthermore we show that (iii) if |R|= 2 then n must be odd, the nonlinearity of f satisfies Nf = 2n-1 - 21/2(n-l), and the nonzero vector in R must be a linear structure of f.(iv) there exists no function on Vn such that |R| = 3.(v) if |R| = 4 then n must be even, the nonlinearityof f satisfies Nf = 2n-1-21/2n, and the nonzero vectors in R must be linear structures of f.(vi) if |R|=5 then n must be odd, the nonlinearity of f is Nf=2n-1-21/2(n-l), the four nonzero vectors in R, denoted by βl,β2,β3and β4 are related by the equation βl ⊕β2 ⊕ β3 ⊕ β4= 0, and none of the four vectors is a linear structure of f. (vii) there exists no function on Vn such that |R| = 6. We also discuss the structures of functions with |R| = 2, 4, 5. In particular we show that these functions have close relationships with bent functions, and can be easily constructed from the latter.

Publication Date


  • 1995

Citation


  • Seberry, J., Zhang, X. M., & Zheng, Y. (1995). Structures of cryptographic functions with strong avalanche characteristics. In Unknown Book (Vol. 917, pp. 119-132).

International Standard Book Number (isbn) 13


  • 9783540593393

Scopus Eid


  • 2-s2.0-84955559535

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


  • 119

End Page


  • 132

Abstract


  • This paper studies the properties and constructions of nonlinear functions, which are a core component of cryptographic primitives including data encryption algorithms and one-way hash functions. A main contrilMtion of this paper is to reveal the relationship between nonlinearity and propagation characteristic, two critical indicators of the cryptographic strength of a Boolean function.In particular, we prove that (i) if f, a Boolean function on Vn, satisfies the propagation criterion with respect to all but a subset R of vectors in Vn, then the nonlinearity of f satisfies Nf ≥ 2 n-1-21/2(n+t)-1, where t is the rank of R, and (ii) When |R| > 2, the nonzero vectors in R are linearly dependent. Furthermore we show that (iii) if |R|= 2 then n must be odd, the nonlinearity of f satisfies Nf = 2n-1 - 21/2(n-l), and the nonzero vector in R must be a linear structure of f.(iv) there exists no function on Vn such that |R| = 3.(v) if |R| = 4 then n must be even, the nonlinearityof f satisfies Nf = 2n-1-21/2n, and the nonzero vectors in R must be linear structures of f.(vi) if |R|=5 then n must be odd, the nonlinearity of f is Nf=2n-1-21/2(n-l), the four nonzero vectors in R, denoted by βl,β2,β3and β4 are related by the equation βl ⊕β2 ⊕ β3 ⊕ β4= 0, and none of the four vectors is a linear structure of f. (vii) there exists no function on Vn such that |R| = 6. We also discuss the structures of functions with |R| = 2, 4, 5. In particular we show that these functions have close relationships with bent functions, and can be easily constructed from the latter.

Publication Date


  • 1995

Citation


  • Seberry, J., Zhang, X. M., & Zheng, Y. (1995). Structures of cryptographic functions with strong avalanche characteristics. In Unknown Book (Vol. 917, pp. 119-132).

International Standard Book Number (isbn) 13


  • 9783540593393

Scopus Eid


  • 2-s2.0-84955559535

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


  • 119

End Page


  • 132