An upper bound on the number of functions satisfying the strict avalanche criterion
type: Item
instance of: scholarly article
title: An upper bound on the number of functions satisfying the strict avalanche criterion
zbMATH Open document ID: 0836.94020
DOI: 10.1016/0020-0190(94)00161-8
author: Luke O'Connor
published in: Information Processing Letters
publication date: 1996-05-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68P25
Mathematics Subject Classification ID: 06E30
zbMATH DE Number: 710251
zbMATH Keywords: Boolean functions
zbMATH Keywords: strict avalanche criterion
zbMATH Keywords: \(n\)-bit function
zbMATH Keywords: cryptographic functions
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00161-8
OpenAlex ID: W2133044087
cites work: On the Application of the Borel-Cantelli Lemma
cites work: Q3202955
cites work: Q5592263
cites work: Structured Design of Substitution-Permutation Encryption Networks
cites work: Higher-dimensional Hadamard matrices
description: scientific article; zbMATH DE number 710251