[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

371.0. "1-bit resilient functions" by RANI::LEICHTERJ () Wed Nov 06 1985 00:21

The following problem arises from some questions in cryptography.  It was all
the rage at the last FOCS (Foundations of Compuer Science) conference a couple
of weeks back.  It is deceptively simple-looking, and currently open.  Be
warned:  A number of very good people have played with it!

Let f be a function from {0,1}^n to {0,1}, i.e., an n-ary boolean function.
We consider a game against an adversary who has unlimited computer power.
We first choose f, and reveal it to the adversary.  The adversary chooses
t arguments for f, and specifies them as either 0 or 1.  We flip fair coins
to fill in the rest of the arguments, and compute f.  We win if the value of
f "is a fair coin"; the adversary wins otherwise.  f is said to be "t-bit
resilient" if we win.

It's clear that choosing f to be the XOR of all its n arguments, or the comple-
ment of the XOR, gives us an (n-1)-bit resilient function.  These functions
have an additional strong property:  They are symmetric; i.e., permuting the
arguments does not change the result.

Problem:  Show that the ONLY symmetric, 1-bit resilient functions are XOR and
not-XOR.

Note:  This is known to be true for "small" n; I think the current threshold
value is something like 9.
							-- Jerry
T.RTitleUserPersonal
Name		DateLines
371.1GOLLY::GILBERTWed Nov 06 1985 18:5750
First, note that the value of a symmetric boolean function is simply a
function of the sum of its arguments -- that is, the number of bits set.
Thus, we can describe the symmetric function f: {0,1}^n -> {0,1} by the
boolean vector b[0..n], of n+1 elements, which gives the value of f when
indexed by the count of the non-zero arguments to f.

For the function to be 1-resilient, we can consider all possible outcomes
of the (remaining) random flips, and verify that just half of these produce
a zero.  Letting c(n,k) be the number of combinations of {0,1}^n that have
exactly k bits set, the function is 1-resilient if and only if:

	n-1			  n-1
	Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i), and
	i=0			  i=0

	 n			   n
	Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i).
	i=1                       i=1

Note that c(n,k) is simply a binomial coefficient (n choose k), so the above
equations are:

	n-1	       	     n-1
	Sum b[i]*c(n-1,i) = 2   , and
	i=0

	 n		     n-1
	Sum b[i]*c(n-1,i) = 2   .
	i=1

This gives us a convenient way to test a function for 1-resiliency.

[ The corresponding set of equations required for t-resiliency are:

	n-t+k		       n-t
  	 Sum  b[i]*c(n-t,i) = 2   , 0 <= k <= t. ]
	 i=k

The question is whether there are any solutions (the vector b) to the
equations for 1-resiliency, besides: b[i] = odd(i), and b[i] = not odd(i).


[ Posed another way, the question of 1-resiliency is similar to asking whether
the multi-set of binomial coefficients {c(n,0), c(n,1), ..., c(n,n)} can be
divided into two subsets having equal sums, in two different ways. ]


If n-1 is a prime, it's simple to show that b[n] = not b[0], since the binomial
coefficients for all the other terms are multiples of n-1, and these two terms
must 'cancel' for the sums to work out right.
371.2BEING::POSTPISCHILThu Nov 07 1985 08:2631
Re .1:

It's early in the morning, so I may be missing something, but:

> 	 n			   n
> 	Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i).
> 	i=1                       i=1

When i=n, I take it c(n-1,n) should be zero?  But then the expression on
the right is equal to 1/2 (2^(n-1)-1).

> 	n-1			  n-1
> 	Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i), and
> 	i=0			  i=0

Note that the expression on the right here is 1/2 (2^(n-1)) or 2^(n-2).

> 	n-1	       	     n-1
> 	Sum b[i]*c(n-1,i) = 2   , and
> 	i=0

So this is wrong; it should be 2^(n-2).

> 	 n		     n-1
> 	Sum b[i]*c(n-1,i) = 2   .
> 	i=1

And this should be 1/2 (2^(n-1)-1).


				-- edp
371.3R2ME2::GILBERTThu Nov 07 1985 16:2754
[ The following corrects some minor errors that were in 371.2 ]

First, note that the value of a symmetric boolean function is simply a
function of the sum of its arguments -- that is, the number of bits set.
Thus, we can describe the symmetric function f: {0,1}^n -> {0,1} by the
boolean vector b[0..n], of n+1 elements, which gives the value of f when
indexed by the count of the non-zero arguments to f.

For the function to be 1-resilient, we can consider all possible outcomes
of the (remaining) random flips, and verify that just half of these produce
a zero.  Letting c(n,k) be the number of combinations of {0,1}^n that have
exactly k bits set, the function is 1-resilient if and only if:

	n-1			  n-1
	Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i), and
	i=0			  i=0

	 n			     n
	Sum b[i]*c(n-1,i-1) = (1/2) Sum c(n-1,i-1).
	i=1			    i=1

Note that c(n,k) is simply a binomial coefficient (n choose k), so the above
equations are:

	n-1	       	     n-2
	Sum b[i]*c(n-1,i) = 2   , and
	i=0

	 n		       n-2
	Sum b[i]*c(n-1,i-1) = 2   .
	i=1

This gives us a convenient way to test a function for 1-resiliency.

[ The corresponding set of equations required for t-resiliency are:

	n-t			n-1-t
  	Sum  b[i+k]*c(n-t,i) = 2     , 0 <= k <= t. ]
	i=0

The question is whether there are any solutions (the vector b) to the
equations for 1-resiliency, besides: b[i] = odd(i), and b[i] = not odd(i).


[ Posed another way, the question of 1-resiliency is similar to asking whether
the multi-set of binomial coefficients {c(n,0), c(n,1), ..., c(n,n)} can be
divided into two subsets having equal sums, in two different ways. ]


If n-1 is prime, it's simple to show that b[n-1] = not b[0], since the binomial
coefficients for all the other terms are multiples of n-1, and these two terms
must 'cancel' for the sums to work out right.

					- Gilbert
371.4R2ME2::GILBERTMon Nov 11 1985 02:5724
I've found two counter-examples.

Let f be a function from {0,1}^14 to {0,1}, such that f is 1 iff the number
of 1s in its arguments is in the set {1,3,4,7,8,11,13}.  The relevant line
from Pascal's triangle is:

	1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
	  13   +286+715          +1716+1287        +78   +1 = 2^12
	1   +78+286         +1716+1716         +286   +13   = 2^12

Let f be a function from {0,1}^15 to {0,1}, such that f is 1 iff the number
of 1s in its arguments is in the set {0,2,3,6,7,10,12,14}.  The relevant line
from Pascal's triangle is:

	1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
	1   +91    +1001+2002          +3003+2002         +91   +1 = 2^13
	  14   +364+1001          +3432+3003          +364   +14   = 2^13

These solutions (and their reflections) are the only non-XOR 1-resilient
symmetric functions of 28 or fewer variables.

I haven't checked whether either of these can be used to get 2-resiliency.

					- Gilbert