Función booleana equilibrada

En matemáticas e informática , una función booleana balanceada es una función booleana cuya salida produce tantos 0 como 1 en su conjunto de entrada . Esto significa que, para una cadena de bits de entrada aleatoria uniforme, la probabilidad de obtener un 1 es 1/2. ^{[ 1 ]}

Ejemplos de funciones booleanas balanceadas son la función de mayoría , ^{[ 1 ]} la "función de dictadura" que copia el primer bit de su entrada a la salida, ^{[ 1 ]} y la función de verificación de paridad que produce la OR exclusiva de los bits de entrada. ^{[ 2 ]}

Si es una función bent sobre bits, y es cualquier vector de bits distinto de cero, entonces la función que mapea a es balanceada. Las funciones bent son precisamente las funciones para las cuales esto es cierto, para todas las elecciones distintas de cero de . ^{[ 3 ]}${\displaystyle f}$${\displaystyle n}$${\displaystyle \alpha }$${\displaystyle n}$${\displaystyle x}$${\displaystyle f(x)\oplus f(x\oplus \alpha )}$${\displaystyle \alpha }$

La función de dictadura puede evaluarse tras examinar un único bit de la entrada, pero ese bit siempre debe examinarse. Benjamini, Schramm y Wilson describen un ejemplo más complejo basado en la teoría de la percolación, con la propiedad de que un algoritmo aleatorio de Las Vegas puede calcular la función con exactitud, asegurando que la probabilidad de leer cualquier bit de entrada sea pequeña, aproximadamente inversamente proporcional a la raíz cuadrada del número de bits. ^{[ 1 ]}

Las funciones booleanas balanceadas se utilizan en criptografía , donde el balance es uno de los criterios más importantes para las funciones booleanas criptográficamente robustas. ^{[ 3 ]} Si una función no está balanceada, tendrá un sesgo estadístico , lo que la hace vulnerable al criptoanálisis, como el ataque de correlación .