Balanced Boolean function: Difference between revisions

Revision as of 23:11, 21 February 2010

Latest revision as of 20:30, 11 July 2025

(34 intermediate revisions by 24 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 one'''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}}

== Usage ==

Balanced boolean functions are primarily used in cryptography.

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}}

== See also ==

* [[Bent function]]

==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=

* [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

| 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

| 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]]

{{math-stub}}