Introduction - eprint.iacr.org.pdfVIP

STRICT AVALANCHE CRITERION OVER FINITE FIELDS YUAN LI AND T.W.CUSICK Abstract. Boolean functions on GF (2) which satisfy the Strict Avalanche Criterion (SAC) play an important role in the art of information security. In this paper, we extend the conception SAC to finite fields GF (p). A necessary and sufficient condition is given by using spectral analysis. Also, based on an interesting permutation polynomial theorem, we prove various facts about (n − 1)-th order SAC functions on GF (p). We also construct many such functions. 1. Introduction Resilient functions, bent functions and functions which satisfy SAC have im- portant cryptographic applications. SAC was introduced by Webster and Tavares [16] in connection with a study of the design of S-boxes. A Boolean function in n variables is said to satisfy SAC if complementing any one of the n input bits results in changing the output bit with probability exactly one half. Forr´e [5] extended this conception by defining the higher order SAC . A Boolean function of n variables satisfies the SAC of order k (SAC (k)), 0 ≤ k ≤ n − 2, if whenever k input bits are fixed arbitrarily, the resulting function of n − k variables satisfies SAC . The properties of SAC functions have been well studied (see [1], [2], [3], [8], [9], [17]). Recently, Cusick and Yuan [4] described a method to find k-th order symmetric SAC functions for any k, k ≤ n − 2. On the other hand, it’s natural to extend the various cryptographic conceptions from GF (2) to GF (p ) or GF (p )n . For example, [14] and [19] studied the resilient functions on GF (p ). Also, [7], [11], [12] investi- gated the generalized bent functions on GF (p )n .