Función doblada

Tipo especial de función booleana

Las cuatro funciones booleanas 2-arias con peso de Hamming 1 están dobladas; es decir, su no linealidad es 1 (estas matrices de Hadamard muestran la distancia de Hamming a cada una de las ocho funciones lineales y afines) .

La siguiente fórmula muestra que una función 2-aria está doblada cuando su no linealidad es 1:

${\displaystyle 2^{2-1}-2^{{\frac {2}{2}}-1}=2-1=1}$

La función booleana está doblada, es decir, su no linealidad es 6 (que es lo que muestran estas matrices de Hadamard) . ${\displaystyle x_{1}x_{2}\oplus x_{3}x_{4}}$

La siguiente fórmula muestra que una función 4-aria está doblada cuando su no linealidad es 6:

${\displaystyle 2^{4-1}-2^{{\frac {4}{2}}-1}=8-2=6}$

En el campo matemático de la combinatoria , una función doblada es una 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 por 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 funciones booleanas balanceadas , por lo que para cualquier cambio en las variables de entrada hay un 50 por ciento de posibilidades de que el valor de salida cambie.

La no linealidad máxima significa que es difícil aproximar una función doblada mediante una función afín (lineal), una propiedad útil en la defensa contra el criptoanálisis lineal . Además, detectar un cambio en la salida de la función no brinda 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 que no se publicó hasta 1976. ^[1] Se han estudiado ampliamente 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 maneras, lo que da 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, 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, 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 función dada por ${\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}}$ ${\displaystyle {\hat {f}}:\mathbb {Z} _{2}^{n}\to \mathbb {Z} }$

${\displaystyle {\hat {f}}(a)=\sum _{\scriptstyle {x\in \mathbb {Z} _{2}^{n}}}(-1)^{f(x)+a\cdot x},}$

donde a · x = a ₁ x ₁ + a ₂ x ₂ + … + a _n x _n (mod 2) es el producto escalar en Z^número
₂. ^[4] Alternativamente, sea S ₀ ( a ) = { x ∈ Z^número
₂ : f ( x ) = a · x } y S ₁ ( a ) = { x ∈ Z^número
₂ : f ( x ) ≠ a · x } . Entonces | S ₀ ( a ) | + | S ₁ ( a ) | = 2 ⁿ y por lo tanto

${\displaystyle {\hat {f}}(a)=\left|S_{0}(a)\right|-\left|S_{1}(a)\right|=2\left|S_{0}(a)\right|-2^{n}.}$

Para cualquier función booleana f y a ∈ Z^número
₂, la transformación se encuentra en el rango

${\displaystyle -2^{n}\leq {\hat {f}}(a)\leq 2^{n}.}$

Además, la función lineal f ₀ ( x ) = a · x y la función afín f ₁ ( x ) = a · x + 1 corresponden a los dos casos extremos, ya que

${\displaystyle {\hat {f}}_{0}(a)=2^{n},~{\hat {f}}_{1}(a)=-2^{n}.}$

Por lo tanto, para cada a ∈ Z^número
₂El valor de caracteriza dónde la función f ( x ) se encuentra en el rango de f ₀ ( x ) a f ₁ ( x ). ${\displaystyle {\hat {f}}(a)}$

Definición y propiedades

Rothaus definió una función doblada como una función booleana cuya 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. ${\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}}$

Los ejemplos más simples de funciones dobladas, escritas en forma normal algebraica , son F ( x ₁ , x ₂ ) = x ₁ x ₂ y G ( x ₁ , x ₂ , x ₃ , x ₄ ) = x ₁ x ₂ ⊕ x ₃ x ₄ . Este patrón continúa: x ₁ x ₂ ⊕ x ₃ x ₄ ⊕ … ⊕ x _{n −1} x _n es una función doblada para 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 ∈ Z ${\displaystyle \mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}}$^número
₂tomada en orden lexicográfico , se denomina 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

${\displaystyle {\hat {f}}(a)=W\left(2^{n}\right)(-1)^{f(a)},}$

donde W (2 ⁿ ) es la matriz de Walsh ordenada natural y la secuencia se trata como un vector columna . ^[6]

Rothaus demostró que las funciones dobladas existen sólo para n par , y que para una función doblada f , para todo a ∈ Z ${\displaystyle \left|{\hat {f}}(a)\right|=2^{n/2}}$^número
₂. ^[4] De hecho, , donde g también está doblado. En este caso, , por lo que f y g se consideran funciones duales . ^[6] ${\displaystyle {\hat {f}}(a)=2^{n/2}(-1)^{g(a)}}$ ${\displaystyle {\hat {g}}(a)=2^{n/2}(-1)^{f(a)}}$

Toda 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. Por lo tanto, la no linealidad de f (número mínimo de veces que es igual a cualquier función afín) es 2 ^{n −1} − 2 ^{n /2−1} , el máximo posible. Por el contrario, cualquier función booleana con no linealidad 2 ^{n −1} − 2 ^{n /2−1} está doblada. ^[4] El grado de f en forma normal algebraica (llamado orden no lineal de f ) es como máximo ⁠norte/2⁠ (para n > 2 ). ^[5]

Aunque las funciones dobladas son extremadamente raras entre las funciones booleanas de muchas variables, existen de muchos tipos diferentes. Se han realizado investigaciones detalladas sobre clases especiales de funciones dobladas, como las homogéneas [ ^7] o las que surgen de un monomio sobre un cuerpo finito ^[8] , pero hasta ahora las funciones dobladas han desafiado todos los intentos de enumeración o clasificación completas.

Construcciones

Existen varios tipos de construcciones para funciones dobladas. ^[2]

• Construcciones combinatorias: construcciones iterativas, construcción de Maiorana-McFarland, extensiones parciales, funciones dobladas de Dillon y Dobbertin, funciones dobladas de mintérminos, funciones iterativas dobladas
• Construcciones algebraicas: funciones dobladas monomiales con exponentes de Gold, Dillon, Kasami, Canteaut–Leander y Canteaut–Charpin–Kuyreghyan; funciones dobladas de 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 la entrada y la salida. En 1988, Forré reconoció que la transformada de Walsh de una función se puede utilizar para demostrar que satisface el criterio de avalancha estricta (SAC) y las generalizaciones de orden superior, y recomendó esta herramienta para seleccionar candidatos para buenas cajas S que logren una difusión casi perfecta . ^[10] De hecho, las funciones que satisfacen el SAC al 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 llama estructuras lineales , vectores distintos de cero a tales que f ( x + a ) + f ( x ) es una constante. En el lenguaje del criptoanálisis diferencial (introducido después de que se descubriera esta propiedad), la derivada de una función doblada f en cada punto distinto de cero a (es decir, f _a ( x ) = f ( x + a ) + f ( x )) es una función booleana equilibrada , que toma cada valor exactamente la mitad del tiempo. Esta propiedad se llama no linealidad perfecta . ^[5]

Dadas estas buenas propiedades de difusión, la resistencia aparentemente perfecta al criptoanálisis diferencial y la resistencia por definición al criptoanálisis lineal , las funciones dobladas podrían parecer en un principio la opción ideal para funciones criptográficas seguras como las S-boxes. Su defecto fatal es que no pueden ser balanceadas. En particular, una S-box invertible no puede construirse directamente a partir de funciones dobladas, y un cifrado de flujo que utilice una función de combinación doblada es vulnerable a un ataque de correlación . En cambio, uno podría comenzar con una función doblada y complementar aleatoriamente los valores apropiados hasta que el resultado esté balanceado. La función modificada todavía tiene 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 no satisfacer el SAC, por lo que es necesario realizar pruebas cuidadosas. ^[11] Varios criptógrafos han trabajado en técnicas para generar funciones balanceadas que preserven 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 de bloque CAST-128 y CAST-256 , hace uso de funciones dobladas. ^[14] La función hash criptográfica HAVAL utiliza funciones booleanas construidas a partir de representantes de las cuatro clases de equivalencia de funciones dobladas en seis variables. ^[15] El cifrado de flujo Grain utiliza 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. ^[16]

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 de valor q , funciones dobladas p -arias, funciones dobladas sobre un cuerpo finito, funciones dobladas booleanas generalizadas de Schmidt, funciones dobladas de un grupo abeliano finito en el conjunto de números complejos en el círculo unitario, funciones dobladas de un grupo abeliano finito en un grupo abeliano finito, funciones dobladas no abelianas, funciones dobladas vectoriales G, funciones dobladas multidimensionales en un grupo abeliano finito), generalizaciones combinatorias (funciones dobladas simétricas, funciones dobladas homogéneas, funciones dobladas simétricas de rotación, funciones dobladas normales, funciones dobladas autoduales y antiautoduales, funciones dobladas parcialmente definidas, funciones en meseta, funciones dobladas Z y funciones dobladas cuánticas) y generalizaciones criptográficas (funciones semi-dobladas, funciones dobladas balanceadas, funciones parcialmente 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 ${\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}$

${\displaystyle {\hat {f}}(a)=\sum _{x\in \mathbb {Z} _{m}^{n}}e^{{\frac {2\pi i}{m}}(f(x)-a\cdot x)}}$

tiene valor absoluto constante m ^{n /2} . Las funciones no lineales perfectas , aquellas tales que para todo a distinto de cero , f ( x + a ) − f ( a ) toma cada valor m ^{n −1} veces, son funciones dobladas generalizadas. Si m es primo , lo inverso es cierto. En la mayoría de los casos, solo se consideran los primos m . Para los primos impares m , existen funciones dobladas generalizadas para cada n positivo , par e impar. Tienen muchas de las mismas buenas propiedades criptográficas que las funciones dobladas binarias. ^{[17] [18]} ${\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}$

Las funciones semicurvadas son una contraparte de orden impar de las funciones curvadas. Una función semicurvada es aquella con n impar, de modo que solo toma los valores 0 y m ^{( n +1)/2} . También tienen buenas características criptográficas y algunas de ellas están balanceadas, tomando todos los valores posibles con la misma frecuencia. ^[19] ${\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}$ ${\displaystyle \left|{\hat {f}}\right|}$

Las funciones parcialmente dobladas forman una clase grande definida por una condición en la transformada de Walsh y las funciones de autocorrelación. Todas las funciones afines y dobladas están parcialmente dobladas. Esto es a su vez una subclase propia de las funciones en meseta . ^[20]

La idea detrás de las funciones hipercurvadas es maximizar la distancia mínima a todas las funciones booleanas provenientes de monomios biyectivos en el cuerpo finito GF(2 ⁿ ), no solo a 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. ${\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}^{n}}$

Véase también

• Inmunidad de correlación

Referencias

1. OS Rothaus (mayo de 1976). "Sobre funciones "dobladas". Revista de teoría combinatoria, serie A . 20 (3): 300–305. doi : 10.1016/0097-3165(76)90024-8 . ISSN  0097-3165.
2. N. Tokareva (2015). Funciones dobladas: resultados y aplicaciones a la criptografía . Academic Press. ISBN 9780128023181.
3. Blondeau; Nyberg (1 de marzo de 2015). "Funciones no lineales perfectas y criptografía". Campos finitos y sus aplicaciones . 32 : 120–147. doi : 10.1016/j.ffa.2014.10.007 . ISSN  1071-5797.
4. C. Qu; J. Seberry ; T. Xia (29 de diciembre de 2001). «Funciones booleanas en criptografía» . Consultado el 14 de septiembre de 2009 .
5. W. Meier; O. Staffelbach (abril de 1989). Criterios de no linealidad para funciones criptográficas . Eurocrypt '89. págs. 549–562.
6. C. Carlet; LE Danielsen; MG Parker; P. Solé (19 de mayo de 2008). Funciones de doble curvatura automática (PDF) . Cuarto taller internacional sobre funciones booleanas: criptografía y aplicaciones (BFCA '08) . Consultado el 21 de septiembre de 2009 .
7. T. Xia; J. Seberry; J. Pieprzyk ; C. Charnes (junio de 2004). "No existen funciones homogéneas dobladas de grado n en 2n variables 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 .
8. 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 .
9. J. Olsen; R. Scholtz; L. Welch (noviembre de 1982). "Bent-Function Sequences". IEEE Transactions on Information Theory . 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 .
10. R. Forré (agosto de 1988). El criterio de avalancha estricto: propiedades espectrales de funciones booleanas y una definición extendida . CRYPTO '88. págs. 450–468.
11. 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 cajas S . Informe técnico TR 90-013. Queen's University . CiteSeerX 10.1.1.41.8374 . 
12. K. Nyberg (abril de 1991). Cajas S no lineales perfectas . Eurocrypt '91. págs. 378–386.
13. J. Seberry; X. Zhang (diciembre de 1992). Funciones booleanas balanceadas 0-1 altamente no lineales que satisfacen el criterio de avalancha estricto . AUSCRYPT '92. págs. 143-155. CiteSeerX 10.1.1.57.4992 . 
14. 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. S2CID  14365543. Archivado desde el original el 26 de octubre de 2008. Consultado el 20 de septiembre de 2009 .
15. 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 .
16. Hell, Martin; Johansson, Thomas; Maximov, Alexander; Meier, Willi (2006). "Una propuesta de cifrado de flujo: Grano-128" (PDF) . Actas del Simposio Internacional IEEE 2006 sobre Teoría de la Información, ISIT 2006, The Westin Seattle, Seattle, Washington, EE. UU., 9 al 14 de julio de 2006 . IEEE. págs. 1614–1618. doi :10.1109/ISIT.2006.261549.
17. K. Nyberg (mayo de 1990). Construcciones de funciones dobladas y conjuntos de diferencias . Eurocrypt '90. págs. 151–160.
18. Shashi Kant Pandey; BK Dass (septiembre de 2017). "Sobre el espectro de Walsh de la función booleana criptográfica". Revista de Ciencias de la Defensa . 67 (5): 536–541. doi :10.14429/dsj.67.10638. ISSN  0011-748X.
19. K. Khoo; G. Gong; D. Stinson (febrero de 2006). "Una nueva caracterización de funciones semicurvadas y curvadas en cuerpos 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. S2CID  10572850. Consultado el 24 de septiembre de 2009 . 
20. Y. Zheng; X. Zhang (noviembre de 1999). Funciones estancadas. Segunda Conferencia Internacional sobre Seguridad de la Información y las Comunicaciones (ICICS '99). pp. 284–300 . Consultado el 24 de septiembre de 2009 .

Lectura adicional

• 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". Australasian Journal of Combinatorics . 9 : 21–35. CiteSeerX  10.1.1.55.531 . ISSN  1034-4942.
• Colbourn, Charles J. ; Dinitz, Jeffrey H. (2006). Manual de diseños combinatorios (2.ª ed.). CRC Press . págs. 337–339. ISBN 978-1-58488-506-1.
• Cusick, TW; Stanica, P. (2009). Funciones y aplicaciones criptográficas booleanas . Academic Press. ISBN 9780123748904.