Balanced Boolean function

<h2 id="examples">Examples</h2>
Examples of balanced Boolean functions are the <a href="/facts/Majority_function/Ntpb4wDr">majority function</a>,<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> the "dictatorship function" that copies the first bit of its input to the output,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> and the <a href="/facts/Parity_check/peFp3Wau">parity check</a> function that produces the <a href="/facts/Exclusive_or/FHyr7hGQ">exclusive or</a> of the input bits.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
If 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is a <a href="/facts/Bent_function/dgR6uAhQ">bent function</a> on 
 
 
 
 n
 
 
 {\displaystyle n}
 
 bits, and 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 is any nonzero vector of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 bits, then the function that maps 
 
 
 
 x
 
 
 {\displaystyle x}
 
 to 
 
 
 
 f
 (
 x
 )
 ⊕
 f
 (
 x
 ⊕
 α
 )
 
 
 {\displaystyle 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 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
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 <a href="/facts/Percolation_theory/Bop4vG7u">percolation theory</a> with the property that a randomized <a href="/facts/Las_Vegas_algorithm/K43MRwQz">Las Vegas algorithm</a> 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.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="application">Application</h2>
Balanced Boolean functions are used in <a href="/facts/Cryptography/e94PEVau">cryptography</a>, where being balanced is one of "the most important criteria for cryptographically strong Boolean functions".<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> If a function is not balanced, it will have a <a href="/facts/Statistical_bias/Pql981K3">statistical bias</a>, making it subject to <a href="/facts/Cryptanalysis/7CPEQlJI">cryptanalysis</a> such as the <a href="/facts/Correlation_attack/QdkFfSPy">correlation attack</a>.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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, ISBN 1-58113-960-8 <a href="1-58113-960-8" target="_blank">1-58113-960-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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, ISBN 1-58113-960-8 <a href="1-58113-960-8" target="_blank">1-58113-960-8</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">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, ISBN 1-58113-960-8 <a href="1-58113-960-8" target="_blank">1-58113-960-8</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Chakrabarty, K.; Hayes, J.P. (1998), "Balanced Boolean functions", IEE Proceedings - Computers and Digital Techniques, 145 (1): 52, doi:10.1049/ip-cdt:19981769 (inactive 7 December 2024){{citation}}: CS1 maint: DOI inactive as of December 2024 (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">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, ISBN 978-3-540-57766-9 <a href="978-3-540-57766-9" target="_blank">978-3-540-57766-9</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">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, ISBN 1-58113-960-8 <a href="1-58113-960-8" target="_blank">1-58113-960-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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, ISBN 978-3-540-57766-9 <a href="978-3-540-57766-9" target="_blank">978-3-540-57766-9</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Balanced Boolean function open-in-new

Balanced Boolean function