Balanced Boolean function: Difference between revisions

Revision as of 01:04, 25 April 2012

Latest revision as of 20:30, 11 July 2025

(19 intermediate revisions by 11 users not shown)

Line 1:

In [[mathematics]] and [[computer science]], a '''balanced booleanBoolean function''' is a [[booleanBoolean function]] whose output yields as many '''0'''s as '''1'''s over its [[Domain of a function|input set]]. This means that for a uniformly random input string of bits, the probability of getting a '''1''' is 1/2.{{r|bsw}}

==Examples==

An example of a balanced boolean function is the function that assigns a '''1''' to every [[even number]] and '''0''' to all odd numbers (likewise the other way around). The same applies for functions assigning '''1''' to all positive numbers and '''0''' otherwise.

Examples of balanced Boolean functions are the [[majority function]],{{r|bsw}} the "dictatorship function" that copies the first bit of its input to the output,{{r|bsw}} and the [[parity check]] function that produces the [[exclusive or]] of the input bits.{{r|ch}}

If <math>f</math> is a [[bent function]] on <math>n</math> bits, and <math>\alpha</math> is any nonzero vector of <math>n</math> bits, then the function that maps <math>x</math> to <math>f(x)\oplus f(x\oplus\alpha)</math> is balanced. The bent functions are exactly the functions for which this is true, for all nonzero choices of <math>\alpha</math>.{{r|szz}}

A Boolean function of n bits is balanced if it takes the value 1 with probability 1⁄2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a mistake) so that on uniformly random inputs, no input bit is read with probability more than Θ(n-1/2√ log n). We construct a balanced monotone Boolean function and a randomized algorithm computing it for which each bit is read with probability Θ(n-1⁄3 log n). We then show that for any randomized algorithm for evaluating a balanced Boolean function, when the input bits are uniformly random, there is some input bit that is read with probability at least Θ(n-1𔊪). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Θ(n-1𔊫).

The dictatorship function can be evaluated after examining only a single bit of the input, but that bit must always be examined. Benjamini, Schramm, and Wilson describe a more complex example based on [[percolation theory]] with the property that a randomized [[Las Vegas algorithm]] can compute the function exactly while ensuring that the probability of reading any particular input bit is small, roughly inversely proportional to the square root of the number of bits.{{r|bsw}}

== Usage Application==

Balanced Boolean functions are used in [[cryptography]], where being balanced is one of "the most important criteria for cryptographically strong Boolean functions".{{r|szz}} If a function is not balanced, it will have a [[statistical bias]], making it subject to [[cryptanalysis]] such as the [[correlation attack]].

Balanced boolean functions are primarily used in [[cryptography]].

== See also ==

* [[Bent function]]

== References ==

{{reflist|refs=

* [http://portal.acm.org/citation.cfm?id=1060627 Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read], Annual ACM Symposium on Theory of Computing

<ref name=bsw>{{citation

[[Category:Boolean algebra]]

| last1 = Benjamini | first1 = Itai | author1-link = Itai Benjamini

| last2 = Schramm | first2 = Oded | author2-link = Oded Schramm

| last3 = Wilson | first3 = David Bruce

| editor1-last = Gabow | editor1-first = Harold N.

| editor2-last = Fagin | editor2-first = Ronald

| arxiv = math.PR/0410282

* | contribution [http://portal.acm.org/citation.cfm?id=1060627 Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read], Annual ACM Symposium on Theory of Computing

| doi = 10.1145/1060590.1060627

| pages = 244–250

| publisher = Association for Computing Machinery

| title = Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22–24, 2005

| year = 2005| isbn = 1-58113-960-8 }}</ref>

<ref name=ch>{{citation

{{comp-sci-theory-stub}}

| last1 = Chakrabarty | first1 = K.

{{crypto-stub}}

| last2 = Hayes | first2 = J.P.

| doi = 10.1049/ip-cdt:19981769

| issue = 1

| journal = IEE Proceedings - Computers and Digital Techniques

| page = 52

| title = Balanced Boolean functions

| volume = 145

| year = 1998| doi-broken-date = 11 July 2025

}}</ref>

<ref name=szz>{{citation

| last1 = Seberry | first1 = Jennifer | author1-link = Jennifer Seberry

| last2 = Zhang | first2 = Xian-Mo

| last3 = Zheng | first3 = Yuliang

| editor-last = Stinson | editor-first = Douglas R.

| contribution = Nonlinearly balanced Boolean functions and their propagation characteristics

| doi = 10.1007/3-540-48329-2_5

| pages = 49–60

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Advances in Cryptology – CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22–26, 1993, Proceedings

| volume = 773

| year = 1993| isbn = 978-3-540-57766-9 }}</ref>

}}

[[Category:Boolean algebra]]