Bounds for Resilient Functions and Orthogonal Arrays

Orthogonal arrays (OAs) are basic combinatorial structures, which appear 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 algorithms, and perfect local randomizers. In this paper, we give new bounds on the size of orthogonal arrays using Delsarte’s linear programming method. Then we derive bounds on resilient functions and discuss when these bounds can be met.