mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

and

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, a balanced Boolean function is a

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...

whose output yields as many 0s as 1s over its input set. This means that for a uniformly random input string of bits, the probability of getting a 1 is 1/2.

Examples

Examples of balanced Boolean functions are the

majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of t ...

, the "dictatorship function" that copies the first bit of its input to the output, and the

parity check A parity bit, or check bit, is a bit added to a string of binary code. Parity bits are a simple form of error detecting code. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit octets (bytes) ...

function that produces the

exclusive or Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (on ...

of the input bits. If

f

is a bent function on

n

bits, and

\alpha

is any nonzero vector of

n

bits, then the function that maps

x

f(x)\oplus f(x\oplus\alpha)

is balanced. The bent functions are exactly the functions for which this is true, for all nonzero choices of

\alpha

. 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 In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected ...

with the property that a randomized

Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives Correctness (computer science), correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas alg ...

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.

Application

Balanced Boolean functions are used in

cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...

, where being balanced is one of "the most important criteria for cryptographically strong Boolean functions". If a function is not balanced, it will have a

statistical bias In the field of statistics, bias is a systematic tendency in which the methods used to gather data and estimate a sample statistic present an inaccurate, skewed or distorted (''biased'') depiction of reality. Statistical bias exists in numerou ...

, making it subject to

cryptanalysis Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic se ...

such as the

correlation attack Correlation attacks are a class of cryptographic known-plaintext attacks for breaking stream ciphers whose keystreams are generated by combining the output of several linear-feedback shift registers (LFSRs) using a Boolean function. Correlation a ...

References

{{reflist, refs= {{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 {{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 = 7 December 2024 {{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 Boolean algebra