Content deleted Content added
Fetchcomms (talk | contribs) m Added {{unreferenced}} tag to article. using Friendly |
Citation bot (talk | contribs) Altered doi-broken-date. | Use this bot. Report bugs. | #UCB_CommandLine |
||
| (35 intermediate revisions by 24 users not shown) | |||
Line 1:
In [[mathematics]] and [[computer science]], a '''balanced Boolean function''' is a [[Boolean 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==
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}}
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}}
==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]].
== References ==
{{reflist|refs=
<ref name=bsw>{{citation
| 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 = Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read
| 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
| last1 = Chakrabarty | first1 = K.
| 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]]
| |||