En matemáticas , una función booleana es una función cuyos argumentos y resultado asumen valores de un conjunto de dos elementos (normalmente {verdadero, falso}, {0,1} o {-1,1}). [1] [2] Los nombres alternativos son función de conmutación , utilizada especialmente en la literatura informática más antigua , [3] [4] y función de verdad (o función lógica) , utilizada en lógica . Las funciones booleanas son el tema del álgebra booleana y la teoría de conmutación . [5]
Una función booleana toma la forma , donde se conoce como dominio booleano y es un número entero no negativo llamado aridad de la función. En el caso de que , la función sea un elemento constante de . Una función booleana con múltiples salidas, que es una función booleana vectorial o con valores vectoriales (una caja S en criptografía simétrica ). [6]
Existen diferentes funciones booleanas con argumentos; igual al número de tablas de verdad diferentes con entradas.
Cada función booleana -aria se puede expresar como una fórmula proposicional en variables , y dos fórmulas proposicionales son lógicamente equivalentes si y sólo si expresan la misma función booleana.
Una función booleana puede tener una variedad de propiedades: [7]
Constante : siempre es verdadera o siempre falsa independientemente de sus argumentos.
Monótono : para cada combinación de valores de argumentos, cambiar un argumento de falso a verdadero solo puede hacer que la salida cambie de falso a verdadero y no de verdadero a falso. Se dice que una función es única en una determinada variable si es monótona con respecto a los cambios en esa variable.
Lineal : para cada variable, invertir el valor de la variable siempre hace una diferencia en el valor de verdad o nunca hace una diferencia (una función de paridad ).
Simétrico : el valor no depende del orden de sus argumentos.
Doblada : todas sus derivadas están equilibradas (el espectro de autocorrelación es cero)
Correlación inmune al orden m : si la salida no está correlacionada con todas las combinaciones (lineales) de como máximo m argumentos
Evasivo : si la evaluación de la función siempre requiere el valor de todos los argumentos
Una función booleana es una función de Sheffer si puede usarse para crear (por composición) cualquier función booleana arbitraria (ver integridad funcional ).
El grado algebraico de una función es el orden del monomio de mayor orden en su forma algebraica normal.
La complejidad de los circuitos intenta clasificar las funciones booleanas con respecto al tamaño o la profundidad de los circuitos que pueden calcularlas.
Funciones derivadas
Una función booleana se puede descomponer utilizando el teorema de expansión de Boole en cofactores de Shannon positivos y negativos ( expansión de Shannon ), que son las funciones (k-1)-arias resultantes de fijar uno de los argumentos (en cero o uno). Las funciones generales (k-arias) obtenidas imponiendo una restricción lineal a un conjunto de entradas (un subespacio lineal) se conocen como subfunciones . [8]
La derivada booleana de la función para uno de los argumentos es una función (k-1)-aria que es verdadera cuando la salida de la función es sensible a la variable de entrada elegida; es el XOR de los dos cofactores correspondientes. En una expansión de Reed-Muller se utilizan una derivada y un cofactor . El concepto se puede generalizar como una derivada k-aria en la dirección dx, obtenida como la diferencia (XOR) de la función en x y x + dx. [8]
La transformada de Möbius (o transformada de Boole-Möbius ) de una función booleana es el conjunto de coeficientes de su polinomio ( forma normal algebraica ), en función de los vectores exponentes monomios. Es una transformación autoinversa . Se puede calcular de manera eficiente utilizando un algoritmo de mariposa (" Transformada rápida de Möbius "), análogo a la Transformada rápida de Fourier . [9] Las funciones booleanas coincidentes son iguales a su transformada de Möbius, es decir, los valores de su tabla de verdad (minterm) son iguales a sus coeficientes algebraicos (monomio). [10] Hay 2^2^( k −1) funciones coincidentes de k argumentos. [11]
Análisis criptográfico
La transformada de Walsh de una función booleana es una función k-aria con valores enteros que proporciona los coeficientes de una descomposición en funciones lineales ( funciones de Walsh ), análoga a la descomposición de funciones con valores reales en armónicos mediante la transformada de Fourier . Su cuadrado es el espectro de potencia o espectro de Walsh . El coeficiente de Walsh de un vector de un solo bit es una medida de la correlación de ese bit con la salida de la función booleana. El coeficiente de Walsh máximo (en valor absoluto) se conoce como linealidad de la función. [8] El número más alto de bits (orden) para el cual todos los coeficientes de Walsh son 0 (es decir, las subfunciones están equilibradas) se conoce como resiliencia , y se dice que la función es correlacionada e inmune a ese orden. [8] Los coeficientes de Walsh juegan un papel clave en el criptoanálisis lineal .
La autocorrelación de una función booleana es una función k-aria de valor entero que proporciona la correlación entre un cierto conjunto de cambios en las entradas y la salida de la función. Para un vector de bits dado, está relacionado con el peso de Hamming de la derivada en esa dirección. El coeficiente de autocorrelación máximo (en valor absoluto) se conoce como indicador absoluto . [7] [8] Si todos los coeficientes de autocorrelación son 0 (es decir, las derivadas están equilibradas) para un cierto número de bits, entonces se dice que la función satisface el criterio de propagación en ese orden; Si todos son cero, entonces la función es una función doblada . [12] Los coeficientes de autocorrelación juegan un papel clave en el criptoanálisis diferencial .
Los coeficientes de Walsh de una función booleana y sus coeficientes de autocorrelación están relacionados por el equivalente del teorema de Wiener-Khinchin , que establece que la autocorrelación y el espectro de potencia son un par de transformada de Walsh. [8]
Tabla de aproximación lineal
Estos conceptos pueden extenderse naturalmente a funciones booleanas vectoriales considerando sus bits de salida ( coordenadas ) individualmente, o más detalladamente, observando el conjunto de todas las funciones lineales de bits de salida, conocidas como sus componentes . [6] El conjunto de transformadas de Walsh de los componentes se conoce como Tabla de Aproximación Lineal (LAT) [13] [14] o matriz de correlación ; [15] [16] describe la correlación entre diferentes combinaciones lineales de bits de entrada y salida. El conjunto de coeficientes de autocorrelación de los componentes es la tabla de autocorrelación , [14] relacionada mediante una transformada de Walsh de los componentes [17] con la tabla de distribución de diferencias (DDT) más utilizada [13] [14] que enumera las correlaciones entre diferencias. en bits de entrada y salida (ver también: S-box ).
Forma polinómica real
En el hipercubo unitario
Cualquier función booleana se puede extender (interpolar) de forma única al dominio real mediante un polinomio multilineal en , construido sumando los valores de la tabla de verdad multiplicados por polinomios indicadores :
Cuando el dominio está restringido al hipercubo de n dimensiones , el polinomio da la probabilidad de un resultado positivo cuando la función booleana f se aplica a n variables aleatorias independientes ( Bernoulli ), con probabilidades individuales x . Un caso especial de este hecho es el lema de acumulación para funciones de paridad . La forma polinomial de una función booleana también se puede utilizar como su extensión natural a la lógica difusa .
En el hipercubo simétrico
A menudo, el dominio booleano se toma como , con falso ("0") asignado a 1 y verdadero ("1") a -1 (consulte Análisis de funciones booleanas ). El polinomio correspondiente a viene dado por:
^ "Función booleana - Enciclopedia de Matemáticas". encyclopediaofmath.org . Consultado el 3 de mayo de 2021 .
^ Weisstein, Eric W. "Función booleana". mathworld.wolfram.com . Consultado el 3 de mayo de 2021 .
^ "función de conmutación". TheFreeDictionary.com . Consultado el 3 de mayo de 2021 .
^ Davies, DW (diciembre de 1957). "Funciones de conmutación de tres variables". Transacciones IRE en Computadoras Electrónicas . CE-6 (4): 265–275. doi :10.1109/TEC.1957.5222038. ISSN 0367-9950.
^ McCluskey, Edward J. (1 de enero de 2003), "Teoría de la conmutación", Enciclopedia de Ciencias de la Computación , GBR: John Wiley and Sons Ltd., págs. 1727-1731, ISBN978-0-470-86412-8, consultado el 3 de mayo de 2021
^ ab Carlet, Claude. "Funciones booleanas vectoriales para criptografía" (PDF) . Universidad de París . Archivado (PDF) desde el original el 17 de enero de 2016.
^ ab "Funciones booleanas - Manual de referencia de Sage 9.2: Criptografía". doc.sagemath.org . Consultado el 1 de mayo de 2021 .
^ abcdef Tarannikov, Yuriy; Korolev, Peter; Botev, Antón (2001). "Coeficientes de autocorrelación e inmunidad de correlación de funciones booleanas". En Boyd, Colin (ed.). Avances en criptología - ASIACRYPT 2001 . Apuntes de conferencias sobre informática. vol. 2248. Berlín, Heidelberg: Springer. págs. 460–479. doi : 10.1007/3-540-45682-1_27 . ISBN978-3-540-45682-7.
^ Carlet, Claude (2010), "Funciones booleanas para criptografía y códigos de corrección de errores" (PDF) , Modelos y métodos booleanos en matemáticas, informática e ingeniería , Enciclopedia de matemáticas y sus aplicaciones, Cambridge: Cambridge University Press, págs. .257–397, ISBN978-0-521-84752-0, recuperado el 17 de mayo de 2021
^ Pieprzyk, Josef; Wang, Huaxiong; Zhang, Xian-Mo (1 de mayo de 2011). "Transformadas de Mobius, funciones booleanas coincidentes y propiedad de no coincidencia de funciones booleanas". Revista Internacional de Matemáticas Informáticas . 88 (7): 1398-1416. doi :10.1080/00207160.2010.509428. ISSN 0020-7160. S2CID 9580510.
^ Nitaj, Abderrahmane; Susilo, Willy; Tonien, José (1 de octubre de 2017). "Producto de Dirichlet para funciones booleanas". Revista de Matemáticas Aplicadas y Computación . 55 (1): 293–312. doi :10.1007/s12190-016-1037-4. ISSN 1865-2085. S2CID 16760125.
^ Canteau, Anne; Carlet, Claude; Charpin, Pascale; Fontaine, Carolina (14 de mayo de 2000). "Características de propagación e inmunidad a la correlación de funciones booleanas altamente no lineales". Actas de la XIX Conferencia Internacional sobre Teoría y Aplicación de Técnicas Criptográficas . EUROCRIPT'00. Brujas, Bélgica: Springer-Verlag: 507–522. ISBN978-3-540-67517-4.
^ ab Heys, Howard M. "Un tutorial sobre criptoanálisis lineal y diferencial" (PDF) . Archivado (PDF) desde el original el 17 de mayo de 2017.
^ abc "S-Boxes y sus representaciones algebraicas - Manual de referencia de Sage 9.2: criptografía". doc.sagemath.org . Consultado el 4 de mayo de 2021 .
^ Daemen, Juana; Govaerts, René; Vandewalle, Joos (1994). "Matrices de correlación". En Preneel, Bart (ed.). Cifrado rápido de software: segundo taller internacional. Lovaina, Bélgica, 14 a 16 de diciembre de 1994, Actas . Apuntes de conferencias sobre informática. vol. 1008. Saltador. págs. 275–285. doi : 10.1007/3-540-60590-8_21 .
^ Daemen, Joan (10 de junio de 1998). "Capítulo 5: Propagación y correlación - Anexo a la propuesta AES Rijndael" (PDF) . NIST . Archivado (PDF) desde el original el 23 de julio de 2018.
^ Nyberg, Kaisa (1 de diciembre de 2019). "Las tablas de autocorrelación extendida y boomerang y los vínculos entre las propiedades de no linealidad de las funciones booleanas vectoriales" (PDF) . Archivado (PDF) desde el original el 2 de noviembre de 2020.
Otras lecturas
Crama, Yves; Hammer, Peter L. (2011), Funciones booleanas: teoría, algoritmos y aplicaciones , Cambridge University Press, doi :10.1017/CBO9780511852008, ISBN 9780511852008
Janković, Dragan; Stanković, Radomir S.; Moraga, Claudio (noviembre de 2003). "Optimización de expresiones aritméticas mediante la propiedad de doble polaridad". Revista Serbia de Ingeniería Eléctrica . 1 (71–80, número 1): 71–80. doi : 10.2298/SJEE0301071J .
Arnold, Bradford Henry (1 de enero de 2011). Lógica y Álgebra de Boole. Corporación de mensajería. ISBN 978-0-486-48385-6.
Mano, MM; Ciletti, MD (2013), Diseño digital , Pearson