En el campo matemático de la combinatoria , una función doblada es un tipo especial de función booleana que es máximamente no lineal; es lo más diferente posible del conjunto de todas las funciones lineales y afines cuando se mide mediante la distancia de Hamming entre tablas de verdad . Concretamente, esto significa que la correlación máxima entre la salida de la función y una función lineal es mínima. Además, las derivadas de una función doblada son un balance Funciones booleanas, por lo que para cualquier cambio en las variables de entrada hay un 50 por ciento de posibilidades de que cambie el valor de salida.
La no linealidad máxima significa que la aproximación de una función doblada por una función afín (lineal) es difícil, una propiedad útil en la defensa contra el criptoanálisis lineal . Además, la detección de un cambio en la salida de la función no proporciona información sobre qué cambio ocurrió en las entradas, lo que hace que la función sea inmune al criptoanálisis diferencial .
Las funciones dobladas fueron definidas y nombradas en la década de 1960 por Oscar Rothaus en una investigación no publicada hasta 1976. [1] Se han estudiado extensamente por sus aplicaciones en criptografía , pero también se han aplicado al espectro ensanchado , la teoría de codificación y el diseño combinatorio . La definición se puede ampliar de varias formas, dando lugar a diferentes clases de funciones dobladas generalizadas que comparten muchas de las propiedades útiles del original.
Se sabe que VA Eliseev y OP Stepchenkov estudiaron funciones dobladas, a las que llamaron funciones mínimas , en la URSS en 1962. [2] Sin embargo, sus resultados aún no han sido desclasificados.
Las funciones dobladas también se conocen como funciones booleanas perfectamente no lineales ( PN ). Ciertas funciones que están lo más cerca posible de la no linealidad perfecta (por ejemplo, para funciones de un número impar de bits o funciones vectoriales) se conocen como casi perfectamente no lineales ( APN ). [3]
Transformada de Walsh
Las funciones dobladas se definen en términos de la transformada de Walsh . La transformada de Walsh de una función booleana es la funcion dada por
donde a · x = a 1 x 1 + a 2 x 2 +… + a n x n (mod 2) es el producto escalar en Zn
2. [4] Alternativamente, sea S 0 ( a ) = { x ∈ Zn
2 : f ( x ) = a · x } y S 1 ( a ) = { x ∈ Zn
2 : f ( x ) ≠ a · x } . Entonces | S 0 ( a ) | + | S 1 ( a ) | = 2 n y por tanto
Para cualquier función booleana f y a ∈ Zn
2 la transformación se encuentra en el rango
Además, la función lineal f 0 ( x ) = a · x y la función afín f 1 ( x ) = a · x + 1 corresponden a los dos casos extremos, ya que
Así, para cada a ∈ Zn
2 El valor de caracteriza dónde se encuentra la función f ( x ) en el rango de f 0 ( x ) af 1 ( x ).
Definición y propiedades
Rothaus definió una función doblada como una función booleanacuya transformada de Walsh tiene un valor absoluto constante . Las funciones dobladas son, en cierto sentido, equidistantes de todas las funciones afines, por lo que son igualmente difíciles de aproximar con cualquier función afín.
Los ejemplos más simples de funciones dobladas, escritas en forma algebraica normal , son F ( x 1 , x 2 ) = x 1 x 2 y G ( x 1 , x 2 , x 3 , x 4 ) = x 1 x 2 ⊕ x 3 x 4 . Este patrón continúa: x 1 x 2 ⊕ x 3 x 4 ⊕… ⊕ x n −1 x n es una función dobladapara cada n par , pero hay una amplia variedad de otras funciones dobladas a medida que n aumenta. [5] La secuencia de valores (−1) f ( x ) , con x ∈ Zn
2tomado en orden lexicográfico , se llama secuencia doblada ; las funciones dobladas y las secuencias dobladas tienen propiedades equivalentes. En esta forma ± 1, la transformada de Walsh se calcula fácilmente como
donde W (2 n ) es la matriz de Walsh ordenada de forma natural y la secuencia se trata como un vector de columna . [6]
Rothaus demostró que las funciones dobladas existen solo para n pares , y que para una función doblada f ,para todo a ∈ Zn
2. [4] De hecho,, donde g también se dobla. En este caso,, Por lo que f y g se consideran duales funciones. [6]
Cada función doblada tiene un peso de Hamming (número de veces que toma el valor 1) de 2 n −1 ± 2 n ⁄ 2 −1 , y de hecho concuerda con cualquier función afín en uno de esos dos números de puntos. Así que la no linealidad de f (número mínimo de veces que es igual a cualquier función afín) es 2 n -1 - 2n ⁄ 2 −1, el máximo posible. A la inversa, cualquier función booleana con no linealidad2n-1- 2n ⁄ 2 −1está doblado. [4]Elgradodefen forma algebraica normal (llamadoorden no linealdef) es como máximo n ⁄ 2 (para n > 2). [5]
Aunque las funciones dobladas son extremadamente raras entre las funciones booleanas de muchas variables, vienen en muchos tipos diferentes. Se han realizado investigaciones detalladas en clases especiales de funciones dobladas, como los homogéneos los [7] o las derivadas de un monomio sobre un campo finito , [8] pero hasta ahora las funciones dobladas han desafiado todos los intentos de una enumeración completa o clasificación .
Construcciones
Hay varios tipos de construcciones para funciones dobladas. [2]
- Construcciones combinatorias: construcciones iterativas, construcción de Maiorana-McFarland, spreads parciales, funciones dobladas de Dillon y Dobbertin, funciones dobladas de minitérmino, funciones iterativas dobladas
- Construcciones algebraicas: funciones monomiales dobladas con exponentes de Gold, Dillon, Kasami, Canteaut-Leander y Canteaut-Charpin-Kuyreghyan; Funciones dobladas Niho, etc.
Aplicaciones
Ya en 1982 se descubrió que las secuencias de longitud máxima basadas en funciones dobladas tienen propiedades de correlación cruzada y autocorrelación que rivalizan con las de los códigos Gold y Kasami para su uso en CDMA . [9] Estas secuencias tienen varias aplicaciones en técnicas de espectro ensanchado .
Las propiedades de las funciones dobladas son naturalmente de interés en la criptografía digital moderna , que busca oscurecer las relaciones entre entrada y salida. En 1988, Forré reconoció que la transformada de Walsh de una función puede usarse para demostrar que satisface el estricto criterio de avalancha (SAC) y generalizaciones de orden superior, y recomendó esta herramienta para seleccionar candidatos para buenas cajas S que logran una difusión casi perfecta . [10] De hecho, las funciones que satisfacen el SAC en el orden más alto posible siempre están dobladas. [11] Además, las funciones dobladas están lo más lejos posible de tener lo que se llaman estructuras lineales , vectores distintos de cero a tales que f ( x + a ) + f ( x ) es una constante. En el lenguaje de criptoanálisis diferencial (introducido después de esta propiedad se descubrió) el derivado de una función de doblado f en cada distinto de cero señalar una (es decir, f una ( x ) = f ( x + a ) + f ( x )) es una función booleana equilibrada , tomando cada valor exactamente la mitad del tiempo. Esta propiedad se llama no linealidad perfecta . [5]
Dadas estas buenas propiedades de difusión, una resistencia aparentemente perfecta al criptoanálisis diferencial y, por definición, la resistencia al criptoanálisis lineal , las funciones dobladas pueden parecer al principio la opción ideal para funciones criptográficas seguras como las cajas S. Su defecto fatal es que no logran equilibrarse. En particular, una caja S invertible no se puede construir directamente a partir de funciones dobladas, y un cifrado de flujo que usa una función de combinación doblada es vulnerable a un ataque de correlación . En su lugar, se puede comenzar con una función doblada y complementar aleatoriamente los valores apropiados hasta que el resultado sea equilibrado. La función modificada todavía tiene una alta no linealidad y, como tales funciones son muy raras, el proceso debería ser mucho más rápido que una búsqueda de fuerza bruta. [5] Pero las funciones producidas de esta manera pueden perder otras propiedades deseables, incluso sin satisfacer el SAC, por lo que es necesario realizar pruebas cuidadosas. [11] Varios criptógrafos han trabajado en técnicas para generar funciones equilibradas que preservan la mayor cantidad posible de las buenas cualidades criptográficas de las funciones dobladas. [12] [13] [14]
Parte de esta investigación teórica se ha incorporado a algoritmos criptográficos reales. El procedimiento de diseño CAST , utilizado por Carlisle Adams y Stafford Tavares para construir las cajas S para los cifrados en bloque CAST-128 y CAST-256 , utiliza funciones dobladas. [14] La función hash criptográfica HAVAL utiliza funciones booleanas creadas a partir de representantes de las cuatro clases de equivalencia de funciones dobladas en seis variables. [15] El cifrado de flujo Grain usa un NLFSR cuyo polinomio de retroalimentación no lineal es, por diseño, la suma de una función doblada y una función lineal. [dieciséis]
Generalizaciones
En la monografía de Tokareva de 2015 se describen más de 25 generalizaciones diferentes de funciones dobladas. [2] Hay generalizaciones algebraicas ( funciones dobladas con valor q , funciones dobladas p -ary, funciones dobladas sobre un campo finito, funciones dobladas booleanas generalizadas de Schmidt, funciones dobladas de un grupo abeliano finito al conjunto de números complejos en la unidad círculo, funciones dobladas de un grupo abeliano finito a un grupo abeliano finito, funciones dobladas no abelianas, funciones vectoriales dobladas en G, funciones dobladas multidimensionales en un grupo abeliano finito), generalizaciones combinatorias (funciones dobladas simétricas, funciones dobladas homogéneas, rotación simétrica funciones dobladas, funciones dobladas normales, funciones auto-dobladas y anti-auto-dual dobladas, funciones dobladas parcialmente definidas, funciones estabilizadas, funciones dobladas en Z y funciones dobladas cuánticas) y generalizaciones criptográficas (funciones semi-dobladas, funciones dobladas balanceadas, parcialmente funciones dobladas, funciones hiper-dobladas, funciones dobladas de orden superior, funciones k- dobladas).
La clase más común de funciones dobladas generalizadas es el tipo mod m , tal que
tiene valor absoluto constante m n / 2 . Funciones no lineales perfectas, Aquellos tales que para todo distinto de cero a , f ( x + a ) - f ( a ) lleva en cada valor de m n - 1 veces, son generalizadas doblada. Si m es primo , lo contrario es cierto. En la mayoría de los casos, solo se consideran los primos m . Para m primo impar , hay funciones dobladas generalizadas para cada n positivo , par e impar. Tienen muchas de las mismas buenas propiedades criptográficas que las funciones binarias dobladas. [17] [18]
Las funciones semi-dobladas son una contraparte de orden impar de las funciones dobladas. Una función semi-doblada escon n impar, tal quetoma solo los valores 0 y m ( n +1) / 2 . También tienen buenas características criptográficas, y algunas de ellas están equilibradas, adoptando todos los valores posibles con la misma frecuencia. [19]
Las funciones parcialmente dobladas forman una clase grande definida por una condición en las funciones de autocorrelación y transformación de Walsh. Todas las funciones afines y dobladas están parcialmente dobladas. Esta es, a su vez, una subclase adecuada de las funciones estancadas . [20]
La idea detrás de las funciones hiper-dobladas es maximizar la distancia mínima a todas las funciones booleanas provenientes de monomios biyectivos en el campo finito GF (2 n ), no solo las funciones afines. Para estas funciones esta distancia es constante, lo que puede hacerlas resistentes a un ataque de interpolación .
Se han dado otros nombres relacionados a clases de funciones criptográficamente importantes , como funciones casi dobladas y funciones torcidas . Si bien no son funciones dobladas en sí mismas (ni siquiera son funciones booleanas), están estrechamente relacionadas con las funciones dobladas y tienen buenas propiedades de no linealidad.
Ver también
- Inmunidad de correlación
Referencias
- ^ OS Rothaus (mayo de 1976). "Sobre las funciones" dobladas "". Revista de Teoría Combinatoria, serie A . 20 (3): 300-305. doi : 10.1016 / 0097-3165 (76) 90024-8 . ISSN 0097-3165 .
- ^ a b c N. Tokareva (2015). Funciones dobladas: resultados y aplicaciones a la criptografía . Prensa académica. ISBN 9780128023181.
- ^ Blondeau; Nyberg (1 de marzo de 2015). "Perfectas funciones no lineales y criptografía" . Campos finitos y sus aplicaciones . 32 : 120-147. doi : 10.1016 / j.ffa.2014.10.007 . ISSN 1071-5797 .
- ^ a b c C. Qu; J. Seberry ; T. Xia (29 de diciembre de 2001). "Funciones booleanas en criptografía" . Consultado el 14 de septiembre de 2009 . Cite journal requiere
|journal=
( ayuda ) - ^ a b c d W. Meier; O. Staffelbach (abril de 1989). Criterios de no linealidad para funciones criptográficas . Eurocrypt '89. págs. 549–562.
- ^ a b C. Carlet; LE Danielsen; MG Parker; P. Solé (19 de mayo de 2008). Funciones de auto doble doblado (PDF) . Cuarto Taller Internacional de Funciones Booleanas: Criptografía y Aplicaciones (BFCA '08) . Consultado el 21 de septiembre de 2009 .
- ^ T. Xia; J. Seberry; J. Pieprzyk ; C. Charnes (junio de 2004). "Las funciones dobladas homogéneas de grado n en 2n variables no existen para n> 3" . Matemáticas aplicadas discretas . 142 (1-3): 127-132. doi : 10.1016 / j.dam.2004.02.006 . ISSN 0166-218X . Consultado el 21 de septiembre de 2009 .
- ^ A. Canteaut ; P. Charpin; G. Kyureghyan (enero de 2008). "Una nueva clase de funciones dobladas monomiales" (PDF) . Campos finitos y sus aplicaciones . 14 (1): 221–241. doi : 10.1016 / j.ffa.2007.02.004 . ISSN 1071-5797 . Archivado desde el original (PDF) el 21 de julio de 2011 . Consultado el 21 de septiembre de 2009 .
- ^ J. Olsen; R. Scholtz; L. Welch (noviembre de 1982). "Secuencias de función doblada" . Transacciones IEEE sobre teoría de la información . IT-28 (6): 858–864. doi : 10.1109 / tit.1982.1056589 . ISSN 0018-9448 . Archivado desde el original el 22 de julio de 2011 . Consultado el 24 de septiembre de 2009 .
- ^ R. Forré (agosto de 1988). El estricto criterio de avalancha: propiedades espectrales de funciones booleanas y una definición extendida . CRYPTO '88. págs. 450–468.
- ^ a b C. Adams ; S. Tavares (enero de 1990). "El uso de secuencias dobladas para lograr un criterio de avalancha estricto de orden superior en el diseño de caja S". Informe técnico TR 90-013. Universidad de Queen . CiteSeerX 10.1.1.41.8374 . Cite journal requiere
|journal=
( ayuda ) - ^ K. Nyberg (abril de 1991). Cajas S perfectas no lineales . Eurocrypt '91. págs. 378–386.
- ^ J. Seberry; X. Zhang (diciembre de 1992). Funciones booleanas equilibradas 0-1 altamente no lineales que satisfacen el estricto criterio de avalancha . AUSCRYPT '92. págs. 143-155. CiteSeerX 10.1.1.57.4992 .
- ^ a b C. Adams (noviembre de 1997). "Construcción de cifrados simétricos mediante el procedimiento de diseño CAST" . Diseños, Códigos y Criptografía . 12 (3): 283–316. doi : 10.1023 / A: 1008229029587 . ISSN 0925-1022 . Archivado desde el original el 26 de octubre de 2008 . Consultado el 20 de septiembre de 2009 .
- ^ Y. Zheng ; J. Pieprzyk; J. Seberry (diciembre de 1992). HAVAL: un algoritmo hash unidireccional con longitud variable de salida . AUSCRYPT '92. págs. 83-104 . Consultado el 20 de junio de 2015 .
- ^ M. Hell; T. Johansson; A. Maximov; W. Meier. "Una propuesta de cifrado de flujo: Grano-128" (PDF) . Consultado el 24 de septiembre de 2009 . Cite journal requiere
|journal=
( ayuda ) - ^ K. Nyberg (mayo de 1990). Construcciones de funciones dobladas y conjuntos de diferencias . Eurocrypt '90. págs. 151–160.
- ^ Shashi Kant Pandey; BK Dass (septiembre de 2017). "Sobre el espectro de Walsh de la función criptográfica booleana". Revista de Ciencias de la Defensa . 67 (5): 536–541. doi : 10.14429 / dsj.67.10638 . ISSN 0011-748X .
- ^ K. Khoo; G. Gong; D. Stinson (febrero de 2006). "Una nueva caracterización de funciones semi-dobladas y dobladas en campos finitos" ( PostScript ) . Diseños, Códigos y Criptografía . 38 (2): 279–295. CiteSeerX 10.1.1.10.6303 . doi : 10.1007 / s10623-005-6345-x . ISSN 0925-1022 . Consultado el 24 de septiembre de 2009 .
- ^ Y. Zheng; X. Zhang (noviembre de 1999). Funciones estancadas . Segunda Conferencia Internacional sobre Seguridad de la Información y las Comunicaciones (ICICS '99). págs. 284–300 . Consultado el 24 de septiembre de 2009 .
Otras lecturas
- C. Carlet (mayo de 1993). Dos nuevas clases de funciones dobladas . Eurocrypt '93. págs. 77-101.
- J. Seberry; X. Zhang (marzo de 1994). "Construcciones de funciones dobladas a partir de dos funciones dobladas conocidas". Revista Australasia de Combinatoria . 9 : 21–35. CiteSeerX 10.1.1.55.531 . ISSN 1034-4942 .
- T. Neumann (mayo de 2006). "Funciones dobladas". CiteSeerX 10.1.1.85.8731 . Cite journal requiere
|journal=
( ayuda ) - Colbourn, Charles J .; Dinitz, Jeffrey H. (2006). Manual de diseños combinatorios (2ª ed.). Prensa CRC . págs. 337–339 . ISBN 978-1-58488-506-1.
- Cusick, TW; Stanica, P. (2009). Funciones y aplicaciones criptográficas booleanas . Prensa académica. ISBN 9780123748904.