Función doblada
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de marzo de 2020; las comprobaciones requieren 2 ediciones .Bent function (del inglés bent - "curvo, inclinado" [1] , [2] ) es una función booleana con un número par de variables , por lo que la distancia de Hamming del conjunto de funciones booleanas afines con el mismo número de variables es máximo. Las funciones dobladas en este sentido tienen el máximo grado de no linealidad entre todas las funciones con un número dado de variables y debido a esto son ampliamente utilizadas en criptografía para crear cifrados que son máximamente resistentes a los métodos de criptoanálisis lineal y diferencial [1] .
En la literatura en idioma ruso, se usa el término " función máximamente no lineal ", que tiene un significado cercano; el número de variables de tales funciones no se limita a números pares. Una función máximamente no lineal con un número par de variables es una función doblada [1] .
Definiciones
La distancia de Hamming para dos funciones booleanas de n variables es el número de diferencias en los valores de estas funciones en el conjunto completo de 2 n conjuntos de variables.
Una función booleana afín (lineal) es una función booleana cuyo polinomio de Zhegalkin no tiene miembros no lineales, es decir, miembros que son una conjunción de varias variables.
El grado de no linealidad de la función booleana grado ( f ) es el número de variables en el término más largo de su polinomio de Zhegalkin.
La no linealidad de la función booleana N ( f ) es la distancia de Hamming desde la función dada hasta el conjunto de todas las funciones afines.
Historia
Las funciones dobladas fueron introducidas en la década de 1960 por Oskar Rothaus (1927-2003), quien en ese momento (de 1960 a 1966) trabajaba en el Instituto de Análisis de Defensa (IDA), donde se dedicaba a la investigación criptográfica. Su primer trabajo sobre funciones dobladas se remonta a 1966 [3] , pero fue clasificado y apareció en la prensa abierta recién en 1976 [4] .
En la década de 1960, V.A. Eliseev y O.P. Stepchenkov se dedicaron al estudio de las funciones dobladas en la URSS, pero su trabajo todavía está clasificado [1] . Se sabe que llamaron a las funciones dobladas "funciones mínimas" y propusieron la construcción de McFarland ya en 1962.
Propiedades
La no linealidad de las funciones dobladas con el número de variables n ( n es par) se define por la relación [1] , [2] :
.
Para funciones máximamente no lineales con un número impar de variables, se desconoce la expresión exacta de la no linealidad [1] .
Ejemplos de funciones dobladas
A continuación se muestran ejemplos de funciones dobladas de cuatro, seis y ocho variables [5] .
Monografía
El libro [1] proporciona un estudio detallado de los resultados en el campo de las funciones dobladas. Se considera la historia del descubrimiento de las funciones dobladas, se describen sus aplicaciones en criptografía y matemáticas discretas . Se investigan las principales propiedades y representaciones equivalentes de las funciones dobladas, las clasificaciones de las funciones dobladas en un pequeño número de variables, las construcciones combinatorias y algebraicas de las funciones dobladas, la conexión de las funciones dobladas con otras propiedades criptográficas. Se estudian las distancias entre las funciones dobladas y el grupo de automorfismos de las funciones dobladas. Se consideran los límites superior e inferior para el número de funciones dobladas y las hipótesis sobre su valor asintótico. Se proporciona una revisión sistemática detallada de 25 generalizaciones diferentes de funciones dobladas y se consideran preguntas abiertas en esta área. El libro de 2015 [1] contiene más de 125 teoremas de funciones dobladas y amplía significativamente el libro [2] publicado en 2011.
Notas
- ↑ 1 2 3 4 5 6 7 8 N. Tokareva. Bent functions: resultados y aplicaciones a la criptografía (inglés) // Acad. Prensa. Elsevier, 2015. 220 páginas. : diario.
- ↑ 1 2 3 Tokareva N. N. Funciones booleanas no lineales: funciones dobladas y sus generalizaciones Archivado el 14 de julio de 2012 en Wayback Machine // LAP LAMBERT Academic Publishing (Saarbrucken, Alemania), 2011. ISBN 978-3-8433-0904-2 . 180 s.
- ↑ Rothaus O. Sobre las funciones dobladas // IDA CRD WP No. 169. 1966.
- ↑ OS Rothaus. Sobre funciones "dobladas" (inglés) // Revista de teoría combinatoria, serie A : revista. - 1976. - mayo ( vol. 20 , n. 3 ). - Pág. 300-305 . — ISSN 0097-3165 . - doi : 10.1016/0097-3165(76)90024-8 .
- ↑ Moldovyan A.A. Criptografía. Cifrados de velocidad // BHV-Petersburg, 2002. ISBN 594157214X , ISBN 9785941572144 . 496 c.