The nonhomomorphicity of boolean functions

Xian Mo Zhang, Yuliang Zheng

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

3 Citations (Scopus)

Abstract

We introduce the notion of nonhomomorphicity as an alternative criterion that forecasts nonlinear characteristics of a Boolean function. Although both nonhomomorphicity and nonlinearity reflect a “difference” between a Boolean function and all the affine functions, they are measured from diffierent perspectives. We are interested in nonhomomorphicity due to several reasons that include (1) unlike other criteria, we have not only established tight lower and upper bounds on the nonhomomorphicity of a function, but also precisely identified the mean of nonhomomorphicity over all the Boolean functions on the same vector space, (2) the nonhomomorphicity of a function can be estimated efficiently, and in fact, we demonstrate a fast statistical method that works both on large and small dimensional vector spaces.

Original languageEnglish
Title of host publicationSelected Areas in Cryptography - 5th Annual International Workshop, SAC 1998, Proceedings
PublisherSpringer, Springer Nature
Pages280-295
Number of pages16
Volume1556
ISBN (Print)3540658947, 9783540658948
Publication statusPublished - 1999
Event5th Annual Workshops on Selected Areas in Cryptography, SAC 1998 - Kingston, Canada
Duration: 17 Aug 199818 Aug 1998

Publication series

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

Other

Other5th Annual Workshops on Selected Areas in Cryptography, SAC 1998
CountryCanada
CityKingston
Period17/08/9818/08/98

Keywords

  • Boolean functions
  • Cryptography
  • Nonhomomorphicity
  • Nonlinear characteristics

Fingerprint Dive into the research topics of 'The nonhomomorphicity of boolean functions'. Together they form a unique fingerprint.

  • Cite this

    Zhang, X. M., & Zheng, Y. (1999). The nonhomomorphicity of boolean functions. In Selected Areas in Cryptography - 5th Annual International Workshop, SAC 1998, Proceedings (Vol. 1556, pp. 280-295). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1556). Springer, Springer Nature.