An upper bound on the number of functions satisfying the strict avalanche criterion (Q1342262)

The Strict Avalanche Criterion (SAC) is used for cryptographic functions to guarantee that each ciphertext bit must change with probability one half when a single input bit is changed. Evidently an \(n\)-bit function is SAC if it is \(50\%\)-dependent in all \(n\) variables. Let \(S(n,k)\) be the number of \(n\)-bit functions that are \(50\%\)-dependent in any subset of \(k\) variables. Then the number of functions which are not SAC is bounded from below by the number of functions that are not \(50\%\)-dependent in any variable. The paper gives explicit expressions for \(S(n,1)\) and \(S(n,2)\). Furthermore, a lower bound for the probability that an \(n\)-bit function is not SAC is given.