Structures of cryptographic functions with strong avalanche characteristics

Jennifer Seberry, Xian Mo Zhang, Yuliang Zheng

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

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 βl23and β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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings
PublisherSpringer, Springer Nature
Pages119-132
Number of pages14
Volume917
ISBN (Print)9783540593393
Publication statusPublished - 1995
Event4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994 - Wollongong, Australia
Duration: 28 Nov 19941 Dec 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume917
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994
CountryAustralia
CityWollongong
Period28/11/941/12/94

Fingerprint Dive into the research topics of 'Structures of cryptographic functions with strong avalanche characteristics'. Together they form a unique fingerprint.

Cite this