An (n,s,t)-resilient function is a function f: {1,–1}n ÷ {1,–1}s, such that every element in {1,–1}s has the same probability to occur when t arbitrary input variables are fixed by an adversary and the remaining n – t variables are assigned – 1 or 1 uniformly and independently. A basic problem is to find the largest possible t given n and s such that an (n,s,t)-resilient function exists. As mentioned in earlier papers resilient functions have been involving in some interesting cryptographic applications, such as amplifying privacy and generating shared random strings in the presence of faulty processors. The following coloring problem is closely related to resilient functions. A good coloring of the n-dimensional Boolean cube with c=2s colors is such that in every k-dimensional subcube each color appears 2k/c times. Here we are interested in the smallest k for which such a coloring exists. A coloring is locally symmetric if each vertex in the n-cube has the same number of neighbors from each color other than its own. An XOR-type coloring is one obtained by a linear map GF(2)n ÷ GF(2)s. We answer the following problems proposed by Friedman: (1) If c – 1|n, are all optimal colorings necessarily locally symmetric? (2) Are there optimal colorings not obtainable as XOR type colorings? We provide positive answers to both questions. For (2), we show that there are infinitely many non-XOR-type optimal solutions, which is also proved by Stinson et al. with a different method. Our main tool is an expression of the eigenvalues of the distance-i adjacency matrix of the n-cube via the Krawtchouk polynomials. With the technique, we are able to make the background of some claims in these earlier papers clearer. Along the way we prove some identities involving the distance distribution of color classes, in order to gain a better understanding of the structure of color classes.
