Algunas preguntas sobre la construcción de permutaciones a partir de funciones booleanas
He visto varios ejemplos de funciones booleanas que se utilizan como permutación.
Por ejemplo, la función Keccak Chi: 2.3.1 :
dehttps://keccak.team/figures.html
O como una fórmula: para$i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$con índices calculados módulo 5
La primera pregunta sería, ¿cuál es la justificación (o prueba) de por qué esto es una permutación?
La segunda, relacionada: ¿Cuáles son las propiedades que debe satisfacer la función booleana para que resulte en una permutación?
Y ahora con respecto a la inversa de tal permutación.
¿Existen métodos/algoritmos genéricos para encontrar el inverso de tal construcción?
Además, ¿cuáles son los principales factores que contribuyen a la complejidad de la inversa (número de variables, grado algebraico, etc.)?
Y si dicho método se aplica a una entrada más grande, digamos$i=\{0..127\}$, ¿es la inversa más difícil de calcular, si la función tiene solo unas pocas (como el 3 para Chi) o muchas, digamos 128, variables de entrada?
Cualquier respuesta/indicaciones son apreciadas.
Respuestas
La pregunta algebraica general es multifacética y puede ser bastante complicada. Algunos dependen del espacio vectorial, algunos de las propiedades del campo de extensión.
Como se menciona en los comentarios, verificar la propiedad puede ser más simple.
Respondí una pregunta relacionada Ejemplos de funciones booleanas balanceadas de bit de salida múltiple
Los artículos de Nyberg mencionan que hay
K. Nyberg, Mapeos diferencialmente uniformes para criptografía , 1993 y
K Nyberg, Cajas S no lineales perfectas , 1992
ambos fácilmente localizables en Google Scholar.
Editar : El keccak$\chi$mapas$\{0,1\}^5$a sí mismo.
usaré$a_i$como entrada y$A_i$como variables de salida como en la pregunta editada.
Índices de conteo módulo 5, si no hay$i$tal que$(a_i,a_{i+2})=(0,1)$después$\chi$tiene un punto fijo para esa entrada. Dejar$W=\{i: (a_i,a_{i+2})=(0,1)\},$entonces el mapeo general solo invierte los bits que pertenecen a$i.$
Tenga en cuenta que los conjuntos$J_i,J_j$dónde$J_i=\{i,i+2\}$son disjuntos excepto cuando$j=i+2$o$i=j+2.$Entonces, no hay ambigüedad para determinar el inverso a menos que estemos en este caso especial, por lo tanto, el inverso existe excepto en este caso especial. Pero incluso en este caso los patrones$(a_i,a_{i+2},a_{i+4})$que dan como resultado cambios de bits no son ambiguos.
Si$(a_i,a_{i+2},a_{i+4})=(1,0,0)$después$a_{i+1}$se volteará pero no$a_{i+3}$. Asi que$A_{i+1}=1\oplus a_{i+1},$y$A_{i+3}=a_{i+3}.$
Si$(a_i,a_{i+2},a_{i+4})=(1,0,1)$después$a_{i+1}$se volteará pero no necesariamente$a_{i+3}$, eso dependerá del valor de$a_{i+6}=a_{i+1}$. Pero ese bit no se ve afectado por el argumento anterior ya que$J_i$y$J_j$son disjuntos si$i=j+1\pmod 2.$
Entonces existe un mapeo inverso único.
Observación : En general, cambiar entre formulaciones de campo de extensión "independientes de la base" de permutaciones y permutaciones de vectores de bits "dependientes de la base" no es sencillo. No veo una formulación de campo de extensión independiente de base inmediata para esta permutación, y como se señaló en los comentarios a la pregunta, tales formulaciones obtenidas (digamos) por interpolación de Lagrange, pueden ser bastante complicadas y de alto grado.
los$\chi$La función se define y analiza en Joan Daemen Ph.D. Tesis
- Estrategias de diseño de funciones de cifrado y hash basadas en criptoanálisis lineal y diferencial, 1995
Capítulo 6: Transformaciones invariantes por desplazamiento (SIT) es donde se menciona la teoría. Daré un vistazo (muchas definiciones y resultados).
Las propiedades de SIT que las hacen útiles;
- En hardware, estas transformaciones se pueden implementar como una matriz interconectada de "procesadores" de salida idénticos de 1 bit.
- La invariancia de cambio asegura que la carga computacional se distribuya de manera óptima.
- En software, su regularidad permite implementaciones eficientes empleando operaciones lógicas bit a bit.
- Además, las transformaciones binarias invariantes por desplazamiento se pueden especificar mediante una sola función booleana.
Los SIT están muy relacionados con los autómatas celulares finitos que se centran en la estructura a largo plazo y el patrón a lo largo del tiempo. Este trabajo se concentra en los aspectos a corto plazo de la invertibilidad y la propagación local y las propiedades de correlación.
Definición 6.1: Una transformación$\phi: \mathcal{A} \to \mathcal{A}$es invariante al desplazamiento si
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$dónde$\mathcal{A}$son todos los estados posibles.
Luego definió los mapas locales donde la imagen solo depende de algunas de las entradas.
Teorema 6.1 (D. Richardson) Si una transformación$\phi$con finito$\nu$es invertible, entonces su inversa$\phi^{−1}$es una transformación invariante por corrimiento con finito$\nu$.
Dónde$\nu$define el vecindario, consulte 6.3 Mapas locales . Este teorema no proporciona una construcción de la inversa explícitamente.
Sección 6.6 Transformaciones no lineales con finito$\nu$es donde se inicia la acción.
Aquí, el mapa local se especifica mediante un conjunto de patrones, llamados paisajes complementarios (CL). El valor de un componente se complementa si su vecindario adopta uno de estos patrones. Un paisaje es un patrón que consta de símbolos.$1, 0$, y$\textbf{-}$que denota "no me importa", posicionado en relación con un origen, denotado por$∗$. En este contexto, el estado todo cero se denotará por$0^*$y el estado todo-uno por$1^*$.
el inverso de$\chi$se habla en secciones de invertibilidad local y global que requieren una profundización en la teoría. Una buena lectura para aprender si quieres.
Entonces, como dije en los comentarios, uno puede buscar todas las permutaciones posibles para ver la propiedad deseada, o buscar en la teoría como lo hizo Daemen. Usaron esta teoría años más tarde en la construcción de Sponge donde$\chi$es la única parte no lineal del SHA-3.
Como mi primera pregunta ha sido respondida en detalle en las respuestas de kodlu y kelalaka, quería compartir los resultados que obtuve en mi segunda pregunta desde la publicación:
¿Cuáles son las propiedades que la función booleana tiene que satisfacer para que resulte en una permutación?
Durante muchas lecturas adicionales, descubrí que esta parece ser una propiedad bien conocida (pero no ampliamente). Por ejemplo, establecido y probado en Funciones booleanas vectoriales para criptografía , capítulo 2.3.1 como Proposición 2:
Una función (n, m) está balanceada si y solo si sus funciones componentes están balanceadas, es decir, si y solo si, para todo v ∈ distinto de cero$F^2_m$, la función booleana v · F está balanceada.
con el hecho adicional del capítulo 2.3:
Las funciones balanceadas (n, n) son las permutaciones en$F^2_n$
Entonces, una función (n, n) es una permutación, si y solo si está balanceada de acuerdo con la definición anterior.
En otras palabras, cada función componente debe equilibrarse, así como cualquier combinación posible de funciones componentes, incl. todas las funciones a la vez, tienen que estar equilibradas.
Por cierto, esta propiedad también se establece, de forma menos obvia, en Cipher and Hash Function Design Strategies based on linear and different cryptanalysis, 1995 Theorem 5.1
Esto también significa que verificar esta propiedad para el caso general de funciones más grandes, por ejemplo, 64 bits de ancho (n = 64), no es factible ya que requeriría verificar el equilibrio para 2 ^ 64 - 1 combinaciones diferentes (para 2 ^ 64 entradas posibles cada una) . Por lo tanto, es probable que se requieran algunos trucos o atajos.