ORTHOGONAL ARRAYS, RESILIENT FUNCTIONS, ERROR-CORRECTING CODES, AND LINEAR-PROGRAMMING BOUNDS

Orthogonal arrays (OAs) are basic combinatorial structures, which appe ar under various disguises in cryptology and the theory of algorithms. Among their applications are universal hashing, authentication codes, resilient and correlation-immune functions, derandomization of algori thms, and perfect local randomizers. In this paper, we give new explic it bounds on the size of orthogonal arrays using Delsarte's linear pro gramming method. Specifically, we prove that the minimum number of row s in a binary orthogonal array of length n and strength t is at least 2(n) - (n2(n-1)/t+1) and also at least 2(n) - (2(n-2)(n+1)/[t+1/2]). W e also prove that these bounds are as powerful as the linear programmi ng bound itself for many parametric situations. An (n, m, t)-resilient function is a function f : {0, 1}(n) --> {0, 1}(m) such that every po ssible output m-tuple is equally likely to occur when the values of t arbitrary inputs are fixed by an opponent and the remaining n-t input bits are chosen independently at random. A basic problem is to maximiz e t given m and n, i.e., to determine the largest value of t such that an (n, m, t)-resilient function exists. In this paper, we obtain uppe r and lower bounds for the optimal values of t where 1 less than or eq ual to n less than or equal to 25 and 1 less than or equal to m < n. T he upper bounds are derived from Delsarte's linear programming bound, and the lower bounds come from constructions based on error-correcting codes. We also obtain new explicit upper bounds for the optimal value s of t. It was proved by Chor et al. in [Proc. 26th IEEE Symp. on Foun dations of Computer Science, 1985, pp. 396-407] that an (n,2,t)-resili ent function exists if and only if t < [2n/3]. This result was general ized by Friedman [Proc. 33rd IEEE Symp. on Foundations ol Computer Sci ence, 1992, pp. 314-319], who proved a bound for general m. We also pr ove some new bounds, and complete the determination of the optimal res iliency of resilient functions with m = 3 and most of the cases for m = 4. Several other infinite classes of (optimal) resilient functions a re also constructed using the theory of anticodes.