Jump to content

Balanced Boolean function

From Wikipedia, the free encyclopedia

In mathematics and computer science, a balanced Boolean function is a Boolean function 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.[1]

Examples

[edit]

Examples of balanced Boolean functions are the majority function,[1] the "dictatorship function" that copies the first bit of its input to the output,[1] and the parity check function that produces the exclusive or of the input bits.[2]

If is a bent function on bits, and is any nonzero vector of bits, then the function that maps to is balanced. The bent functions are exactly the functions for which this is true, for all nonzero choices of .[3]

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.[1]

Application

[edit]

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

References

[edit]
  1. ^ a b c d Benjamini, Itai; Schramm, Oded; Wilson, David Bruce (2005), "Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read", in Gabow, Harold N.; Fagin, Ronald (eds.), Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22–24, 2005, Association for Computing Machinery, pp. 244–250, arXiv:math.PR/0410282, doi:10.1145/1060590.1060627
  2. ^ Chakrabarty, K.; Hayes, J.P. (1998), "Balanced Boolean functions", IEE Proceedings – Computers and Digital Techniques, 145 (1): 52, doi:10.1049/ip-cdt:19981769
  3. ^ a b Seberry, Jennifer; Zhang, Xian-Mo; Zheng, Yuliang (1993), "Nonlinearly balanced Boolean functions and their propagation characteristics", in Stinson, Douglas R. (ed.), Advances in Cryptology – CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22–26, 1993, Proceedings, Lecture Notes in Computer Science, vol. 773, Springer, pp. 49–60, doi:10.1007/3-540-48329-2_5