Global avalanche characteristics and nonlinearity of balanced Boolean functions

Jung Je Son, Jong In Lim, Seongtaek Chee, Soo Hak Sung

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


The GAC (global avalanche characteristic) was introduced to measure cryptographic behavior, such as, propagation characteristic, in a global manner. The two indicators σf and Δf related to GAC are introduced. However, an important problem to compute lower bounds of two indicators for balanced Boolean functions was not solved yet. In this paper, we derive lower bounds on the two indicators for balanced Boolean functions: σf ≥ 22n + 2n+3 and Δf ≥ 8. Moreover, we obtain an upper bound on nonlinearity for balanced Boolean functions: Nf ≤ 2n-1 -1/22-n/2 √σf, which improves the previously known results.

Original languageEnglish
Pages (from-to)139-144
Number of pages6
JournalInformation Processing Letters
Issue number3
Publication statusPublished - 1998 Feb 13

Bibliographical note

Copyright 2020 Elsevier B.V., All rights reserved.


  • Balancedness
  • Boolean function
  • Cryptography
  • Global avalanche characteristic
  • Nonlinearity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Global avalanche characteristics and nonlinearity of balanced Boolean functions'. Together they form a unique fingerprint.

Cite this