A Short Proof of the Non-Existence of Certain Cryptographic Functions

Abstract

Several criteria have been proposed as desirable for binary cryptographic functions. Three important ones are balance, correlation-immunity, and higher order strict avalanche criterion. Lloyd [7] has shown that there are no balanced, uncorrelated functions which satisfy the strict avalanche criterion of order $n-2$. In this note, we give a short proof of this result using elementary combinatorial arguments. The proof relies on the solution of a recurrence relation that seems to be of interest in its own right.