Symmetric Boolean Functions
Palash Sarkar & Subhamoy Maitra
Applied Statistics Unit,
Indian Statistical Institute
203, B.T. Road, Calcutta700 108, INDIA
Abstract
New subsets of symmetric balanced and symmetric correlation immune functions
areidentied.ThemethodinvolvesinterestingrelationsonbinomialcoeÆcientsand
highlightsthecombinatorial richnessofthese classes.Asa consequenceof ourcon-
structivetechniques,weimproveupontheexistinglowerboundsonthecardinality
oftheabove sets.Weconsiderhigherordercorrelation immunefunctionsand show
howto constructn-variable,3rdordercorrelation immunefunctionforeach perfect
squaren9.
Keywords: SymmetricBoolean Function,Balancedness, CorrelationImmunity.
1 Introduction
Aninterestingsubclassof Booleanfunctionsisthesetofsymmetricfunctions.
The study of balanced symmetricfunctions andcorrelation immune symmet-
ricfunctions was made by Bruer [1], Mitchell[5] and later by Yang and Guo
[11]. Independently Chor et al [2] and later Gopalakrishnan et al [4] studied
symmetricfunctionspossessingboththepropertiesofbalancedness andcorre-
lation immunity.FollowingMitchell[5], we providedenitions of the relevant
Booleanfunction properties. We willuse to denoteadditionmodulo2.
Denition 1.1 Let f(X
n
;:::;X
1
) be a Boolean function.
C1.Balancedness. The functionf is balanced ifthe number of ones in its out-
put column is equal to the number of zeros.
C2.NonaÆnity.Thefunctionf isaÆneifitcanbewritten asf(X
n
;:::;X
1 )=
i=n
i=1 a
i X
i
b,where a
i
;b2f0;1g.If b=0, thefunctionf iscalledlinear.The
function f is nonaÆne if it is not aÆne.
?
The fullversionof thepapercan befoundat [6].
Email address: fpalash, subhog@isical.ac.in(PalashSarkar&Subhamoy
Maitra).
i n
X
i+1
;X
i
= 0;X
i 1
;:::;X
1
) = f(X
n
;:::;X
i+1
;X
i
= 1;X
i 1
;:::;X
1
): The
function f is nondegenerate if it is notdegenerate on any variable.
C4.CorrelationImmunity.Thefunctionf iscorrelationimmune(CI)ifProb(f =
X
i )=
1
2
for all1in.
C5. Symmetry. The function f is symmetric if f(X
n
;:::;X
1
) is the same for
all the vectors (X
n
;:::;X
1
) of sameweight.
A
n (i
1
;:::;i
t
)isthesetofalln-variableBooleanfunctionshavingtheproperties
Ci
1
;:::;Ci
t .
In Sections 2 and 3 we provide construction of new functions in the sets
A
n
(1;2;3;5)and A
n
(2;3;4;5)respectively. These are used to improve known
lower bounds on the sizes of such sets. Our constructions explain the \spo-
radic" examples in A
n
(1;2;3;5) reported by Bruer [1] and Mitchell [5]. In
Section 4 we present a method to construct 3rd order correlation immune
functions and compute the algebraicdegree of some of these functions.
Let wt(s) denote the Hamming weight of a binary string s. For a symmetric
Booleanfunctionallinputvectorswiththe sameweighthavethesameoutput
value.Basedonthisobservation,wedeneWTS(f)forasymmetricfunctionf
as WTS(f)=fi:wt(X
n :::X
1
)=i impliesf(X
n
;:::;X
1
)=1g: The weight
of aBoolean function f is wt(f)=jf(X
n
;:::;X
1
):f(X
n
;:::;X
1
)=1gj. Iff
is symmetricthen wt(f)= P
i2WTS(f)
n
i
.
We rst state some binomial coeÆcient identities. These will be interpreted
in terms of symmetric functions in later sections to provide constructions of
balanced and correlation immune symmetricfunctions.
Proposition 1.1 Let n > 0 and 1 r n be positive integers. Then (1)
3r = n +1 if and only if 2
n
r 1
=
n
r
; (2) (n 2r) 2
= n + 2 if and
only if 2
n
r
=
n
r+1
+
n
r 1
[4]; (3) (n 2r 1) 2
= n+3 if and only if
n
r 1
+
n
r+2
=
n
r
+
n
r+1
.
2 Balancedness
In[1;5],theproblemofenumeratingA
n
(1;5)isdiscussed,wherealowerbound
onthe numberof balanced symmetric functionsis obtained. A simple way to
obtainbalanced symmetricfunctionsis provided in [5].Let f;g besymmetric
functions such that WTS(f)=fi:i even gand WTS(g)=fi:i oddg. From
properties of binomial coeÆcients both f and g are balanced. Also these are
the two nondegenerate n-variable aÆnefunctions.
Further,ifnisodd,onecanformadditionalbalancedfunctionsinthefollowing
is even. LetP
i
=fi;n ig. We forma set S by choosing exactly one element
fromeachP
i
.Clearly P
i2S
n
i
= P
i62S
n
n i
=2 n 1
:Thusthefunctionf such
that WTS(f) = S is balanced. From the construction it is clear that there
are 2 n+1
2
such possible functions which also includes the two nondegenerate
aÆne functions. We will call these ways of partitioning to be trivial. These
partitioningsimmediatelygive rise tothe lowerboundjA
n
(1;5)j2 n+1
2
if n
is odd, and 2 if n is even.
The inequality is strict when some nontrivial partitioning is found. Bruer [1]
tabulatesjA
n
(1;5)jforoddn 17andobtainsjA
n
(1;5)j=2 n+1
2
except for
jA
13
(1;5)j=144.Mitchell[5]hasalsoshown thatjA
8
(1;5)j>2andtermed
these as\sporadic"examples.Weshow thatthese are not sporadic and there
existinnitely many integer values of n for which weget strict inequality.
Theorem 2.1 1. Let n 2mod6. Then it is possible to construct f 2
A
n
(1;2;3;5). Consequently, jA
n
(1;5)j>2.
2. Let n14bean even integersuchthat n+2 isa perfect square. Thenit is
possible to construct functions in A
n
(1;2;3;5). Consequently, jA
n
(1;5)j>2.
3. Let n 13 be odd and (n + 3) a perfect square. Then jA
n
(1;5)j
2 n+1
2
+2 n+1
2 3
:
Theorem2.1explainsthesporadicexamplesobtainedbyMitchell[5]forn=8.
For n=13,Theorem 2.1provides jA
13
(1;5)j 144. In fact, jA
13
(1;5)j=144
asobserved by Bruer [1].
3 Correlation Immunity
Hereweconsidertheconstructionproblemforthesetofsymmetriccorrelation
immunefunctions.The followingisacharacterizationofcorrelationimmunity
for symmetricfunctions.
Theorem 3.1 Let f 2 A
n
(5) with WTS(f) = fi
1
;:::;i
r
g. Then f is CI i
n 1
i1
+:::+
n 1
ir
=
n 1
i1 1
+:::+
n 1
ir 1
.
A consequence ofTheorem 3.1is the following fact:Let f and f 0
be such that
k;n k 62 WTS(f) and WTS(f 0
) = WTS(f)[fk;n kg. Then f is CI if
andonly iff 0
isCI.ABooleanfunctionf issaid tobepalindromicif foreach
n-bit vector (b
n
;:::;b
n
), we have f(b
n
;:::;b
1
)=f(1b
n
;:::;1b
1 ).
Proposition 3.1 A symmetric function f is palindromic if and only if for
each i, WTS(f) contains either both i and n i or none of them.
function is CI [5]. The numberof symmetric palindromic functions is clearly
2 b
n
2 c+1
(see Theorem 8 of [11]). Thus it is of interest to nd nonpalindromic
CI functions.We provide such constructionsin this section.
Theorem 3.2 1. Take n;r;i suchthat 2
n 1
r
=
n 1
r i
+
n 1
r+i
, i1. Then
one can construct nonpalindromicf 2A
n (4;5).
2. Let n+1 be a perfect square and n 8. Then jA
n
(2;3;4;5)j 2 b
n
2 c+1
+
2 d
n 1
2 e
2.
3. Let n+2 be a perfect square and n 14. Then jA
n
(2;3;4;5)j2 b
n
2 c+1
+
2 d
n 1
2 e
2.
4. Let n+3 be a perfect square and n 13. Then jA
n
(2;3;4;5)j2 b
n
2 c+1
+
2 d
n 5
2 e
2.
5. Take n;r;i such that 2
n 1
r
=
n 1
r i 1
+
n 1
r+i
, i 1. Then there exists
nonpalindromic f 2A
n (4;5).
It is interesting to note that jA
n
(4;5)j = 2 b
n
2 c+1
+ 2(nmod2) for n =
4;5;10;11;17;28. However, n does not appear to follow any obvious pattern
for this exact equality condition.
4 Higher Order Correlation Immunity
The class of correlation immune functions was introduced by Siegenthaler
[8]. In the introduction we mentioned only the special case of rst order CI
functionsas consideredinMitchell[5]. In this sectionwe consider the general
class ofCIfunctions and presentnew constructionsof3rd order CIfunctions.
Denition 4.1 A Boolean function f(X
n
;:::;X
1
) is said to be correlation
immune of order m (m-CI for short), if
Prob(f(X
n
;:::;X
1
) = 1 j Y
t
= c
t
;:::;Y
1
= c
1
) = Prob(f(X
n
;:::;X
1
) = 1);
wherethevariablesY
t
;:::;Y
1
arechosenfromfX
n
;:::;X
1 g,c
t
;:::;c
1
2f0;1g
and 1tm. A balanced m-CI function iscalled m-resilient.
Constructionof1-resilientand2-resilientsymmetric functionswere presented
in [4]. In section 3, we presented new constructions of 1-CI symmetric func-
tions. Here we present a new constructionof 3-CI functions.
A consequence of [7,Theorem 3.1] isthe following result.
Theorem 4.1 A symmetric function f(X
n
;:::;X
1
) is m-CI if and only if
for each t, 1 t m, wt(f
0
) = ::: = wt(f
2 t
1
) where for 0 k 2 t
1,
f
k (X
n t
;:::;X
1
)=f(X
n
=k
t
;:::;X
n t+1
=k
1
;X
n t
;:::;X
1
)and k
t :::k
1 is
the t-bit binary representation of k.
For 0 k 2 1, by wt(k) we will denote the weight of the t-bit binary
representation of k.
Lemma 4.1 Let f be an n-variable symmetric function and 1 t n 1.
Dene f
k (X
n t
;:::;X
1
) as in Theorem 4.1. Then WTS(f
k
) = fi wt(k) :
i2WTS(f);0i wt(k)n tg:
Lemma 4.2 Let f(X
n
;:::;X
1
) be a symmetric function with WTS(f) =
fr;n rg.For0k 2 t
1,denef
k
asinTheorem4.1.For0i;j 2 t
1,
if wt(i)+wt(j)=t, then wt(f
i
)=wt(f
j ).
Above proof follows fromLemma4.1. Weuse Theorem 4.1andLemma4.2to
obtain the following result on3-CI functions.
Theorem 4.2 Letn andr besuchthat(n 2r) 2
=n.Thenf 2A
n
(5)having
WTS(f)=fr;n rg is 3-CI.
Siegenthaler [8] showed that the maximum possible degree of an n-variable,
m-resilient function is n m. Next we compute the degrees of the functions
described in Theorem 4.2. We present them in the form (n;deg) which are
(9;6);(16;11);(25;14);(36;29);(49;30);(64;55);(81;62);(100;61);(121;118).
The maximum degreeisobtained only forn =9;121. In fact,we were unable
to nd any other n, such that the function of Theorem 4.2 has degree n 3.
Alsoitisinteresting tonotethatthe degreeofthe functionforn =100 isless
thanthedegreeofthefunctionforn =81.Thoughthisisararephenomenon,
this also happens for other values of n. A good explanation of the behaviour
of the degree seems elusive.
If afunction f is m-CI, then a function g obtained by setting any input of f
toconstant is(m 1)-CI. ThusTheorem 4.2 alsoshows the existenceof 2-CI
functions. Earlier existence of 2-resilient functions were shown in [4]. In our
computer experiments wedid not nd any 4-CIfunction for6n20.Fur-
therallthe 3-CIfunctionsobtainedwere palindromic.Wegiveafewexamples
of 3-CI functions not covered by Theorem 4.2. These are written in the form
(n;WTS(f))as(8;f2;3;5;6g),(10;f1;3;4;6;7;9g),(14;f2;3;5;6;8;9;11;12g),
(15;f5;6;9;10g),(15;f3;6;9;12g),(16;f1;3;5;6;7;8;9;10;11;13;14g),
(16;f1;3;4;7;9;12;13;15g),and(16;f1;3;4;6;7;9;10;12;13;15g).Someofthe
examplescanperhapsbeexplainedalongthelinesofTheorem4.2.Theseform
tasks of future research problems.
References
[1] J.O.Bruer. Onpseudorandomsequences ascryptogenerators.InInterna-
tional Zurich Seminar on Digital Communications, pages 157{161.IEEE,
[2] B. Chor,O.Goldreich,J.Hastad,J.Friedman,S.Rudich,andR.Smolen-
sky. The bit extraction problem or t-resilient functions. In 26th IEEE
Symposium on Foundations of Computer Science,pages 396{407,1985.
[3] C. Ding,G. Xiao,and W. Shan. The Stability Theory of Stream Ciphers.
Number561inLectureNotesinComputer Science.Springer-Verlag,1991.
[4] K. Gopalakrisnan, D. G. Homan, and D. R. Stinson. A note on a con-
jecture concerning symmetric resilient functions. Information Processing
Letters, 47(3):139{143,1993.
[5] C. J. Mitchell. Enumerating Boolean functions of cryptographic signi-
cance. Journal of Cryptology, 2(3):155{170,1990.
[6] P. Sarkar and S. Maitra. Balancedness and correlation immunity of sym-
metric Boolean functions. http://www.isical.ac.in/~crg, Technical Report
No. CRG/2002/009.
[7] P. Sarkar. A note on the spectral characterization of correlation immune
Boolean functions. Information Processing Letters, 74:191{195, 2000.
[8] T. Siegenthaler. Correlation-immunity of nonlinear combining functions
forcryptographicapplications.IEEETransactionsonInformationTheory,
IT-30(5):776{780, September 1984.
[9] D. R. Stinson. Resilient functions and large sets of orthogonal arrays.
Congressus Numerantium,92(1993), 105-110.
[10] S. Wolfram. The Mathematica Book, Mathematica Version 3. Wolfram
Media/CambridgeUniversity Press, 1996.
[11] Y.X. Yang andB. Guo. Furtherenumerating Boolean functionsofcryp-
tographic signicance. Journal of Cryptology, 8(3):115{122,1995.
