Función doblada - Bent function

Las cuatro funciones booleanas bidireccionales con peso de Hamming 1 están dobladas; es decir, su no linealidad es 1 (estas matrices de Walsh 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 se dobla 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 Walsh) .${\ Displaystyle x_ {1} x_ {2} \ oplus x_ {3} x_ {4}}$

La siguiente fórmula muestra que una función 4-aria se dobla 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 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 funciones booleanas balanceadas , por lo que para cualquier cambio en las variables de entrada hay un 50 por ciento de probabilidad 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. 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 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. 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 ).

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ⁿ
₂. Alternativamente, sea S ₀ ( a ) = { x ∈ Zⁿ
₂ : f ( x ) = a · x } y S ₁ ( a ) = { x ∈ Zⁿ
₂ : f ( x ) ≠ a · x } . Entonces | S ₀ ( a ) | + | S ₁ ( a ) | = 2 ⁿ y por 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ⁿ
₂ 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}.}$

Así, para cada a ∈ Zⁿ
₂el valor de caracteriza donde la función f ( x ) se encuentra en el rango de f ₀ ( x ) af ₁ ( x ). ${\ Displaystyle {\ hat {f}} (a)}$

Definición y propiedades

Rothaus definió una función doblada como una función booleana cuya transformación 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 algebraica normal , 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. La secuencia de valores (−1) ^{f ( x )} , con x ∈ Z${\ Displaystyle \ mathbb {Z} _ {2} ^ {n} \ to \ mathbb {Z} _ {2}}$ⁿ
₂tomado 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

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

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

Rothaus demostró que las funciones dobladas existen solo para n pares , y que para una función doblada f , para todo a ∈ Z${\ Displaystyle \ left | {\ hat {f}} (a) \ right | = 2 ^ {\ frac {n} {2}}}$ⁿ
₂. De hecho, donde g también se dobla. En este caso, , por lo que f y g se consideran duales funciones. ${\ Displaystyle {\ hat {f}} (a) = 2 ^ {\ frac {n} {2}} (- 1) ^ {g (a)}}$${\ Displaystyle {\ hat {g}} (a) = 2 ^ {\ frac {n} {2}} (- 1) ^ {f (a)}}$

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} - 2 ^{n / 2 -1} , el máximo posible. A la inversa, cualquier función booleana con no linealidad 2 ^{n -1} - 2 ^{n / 2 -1} está doblada. El grado de f en forma algebraica normal (llamado orden no lineal de f ) es como máximo n ⁄ 2 (para n > 2 ).

Aunque las funciones dobladas son extremadamente raras entre las funciones booleanas de muchas variables, vienen en muchos tipos diferentes. Ha habido una investigación detallada sobre clases especiales de funciones dobladas, como las homogéneas o las que surgen de un monomio sobre un campo finito , pero hasta ahora las funciones dobladas han desafiado todos los intentos de una enumeración o clasificación completa.

Construcciones

Hay varios tipos de construcciones para funciones dobladas.

• 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 . 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 . De hecho, las funciones que satisfacen el SAC en el orden más alto posible siempre están dobladas. 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 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 .

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 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 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. 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. Varios criptógrafos han trabajado en técnicas para generar funciones equilibradas que preservan la mayor cantidad posible de buenas cualidades criptográficas de las funciones dobladas.

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. 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. 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.

Generalizaciones

En la monografía de Tokareva de 2015 se describen más de 25 generalizaciones diferentes de funciones dobladas. Hay generalizaciones algebraicas ( funciones dobladas valoradas en 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 el círculo unitario, dobladas funciones de un grupo abeliano finito en 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, funciones dobladas simétricas de rotación, funciones dobladas normales, funciones auto-dobladas y anti-auto-dual dobladas, funciones dobladas parcialmente definidas, funciones estancadas, funciones dobladas en Z y funciones dobladas cuánticas) y generalizaciones criptográficas (funciones semi-dobladas, funciones dobladas balanceadas, funciones dobladas parcialmente, 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} . Funciones no lineales perfectos , aquellos tales que para todo distinto de cero a , f ( x + a ) - f ( a ) lleva en cada valor de m ^{n - 1} veces, se generalizan 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. ${\ Displaystyle f: \ mathbb {Z} _ {m} ^ {n} \ to \ mathbb {Z} _ {m}}$

Las funciones semi-dobladas son una contraparte de orden impar de las funciones dobladas. Una función semi-doblada es con n impar, tal que toma 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. ${\ 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 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 .

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 ⁿ ), 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. ${\ Displaystyle f: \ mathbb {Z} _ {2} ^ {n} \ to \ mathbb {Z} _ {2} ^ {n}}$

Ver también

• Inmunidad de correlación

Referencias

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.