Two results on the bit extraction problem

Katalin Friedl*, Shi-Chun Tsai

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


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 [5,2,3] 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=2 s colors is such that in every k-dimensional subcube each color appears 2 k /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 [5]: (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 [8]. 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 [5,p.318] 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.

Original languageEnglish
Pages (from-to)443-454
Number of pages12
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - 1 Feb 2000
EventProceedings of the 1997 5th Twente Workshop on Graphs and Combinatorial Optimization - Enschede, Netherlands
Duration: 20 May 199722 May 1997

Fingerprint Dive into the research topics of 'Two results on the bit extraction problem'. Together they form a unique fingerprint.

Cite this