Quelques questions sur la construction de permutations à partir de fonctions booléennes
J'ai vu plusieurs exemples de fonctions booléennes utilisées comme permutation.
Par exemple la fonction Keccak Chi : 2.3.1 :
dehttps://keccak.team/figures.html
Ou sous forme de formule : pour$i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$avec des indices calculés modulo 5
La première question serait de savoir quelle est la raison (ou la preuve) pour laquelle il s'agit d'une permutation ?
La seconde, liée : quelles sont les propriétés que la fonction booléenne doit satisfaire pour qu'elle aboutisse à une permutation ?
Et maintenant concernant l'inverse d'une telle permutation.
Existe-t-il des méthodes/algorithmes génériques pour trouver l'inverse d'une telle construction ?
De plus, quels sont les principaux facteurs contribuant à la complexité de l'inverse (nombre de variables, degré algébrique, etc.) ?
Et si une telle méthode est appliquée à une entrée plus grande - disons$i=\{0..127\}$, l'inverse est-il plus difficile à calculer si la fonction n'a que quelques variables d'entrée (comme le 3 pour Chi) ou beaucoup, disons 128 ?
Toutes les réponses / pointeurs sont appréciés.
Réponses
La question algébrique générale est multiforme et peut être assez compliquée. Certains dépendent de l'espace vectoriel, d'autres des propriétés du champ d'extension.
Comme mentionné dans les commentaires, vérifier la propriété peut être plus simple.
J'ai répondu à une question connexe Exemples de fonctions booléennes à sorties multiples symétriques
Les articles de Nyberg qui y sont mentionnés sont
K. Nyberg, Cartographies différentiellement uniformes pour la cryptographie , 1993 et
K Nyberg, S-boxes non linéaires parfaites , 1992
tous deux facilement repérables sur Google Scholar.
Edit : Le keccak$\chi$Plans$\{0,1\}^5$à lui-même.
j'utiliserai$a_i$comme entrée et$A_i$comme variables de sortie comme dans la question éditée.
Comptage des indices modulo 5, s'il n'y a pas$i$tel que$(a_i,a_{i+2})=(0,1)$alors$\chi$a un point fixe pour cette entrée. Laisser$W=\{i: (a_i,a_{i+2})=(0,1)\},$alors le mappage général inverse juste les bits appartenant à$i.$
A noter que les ensembles$J_i,J_j$où$J_i=\{i,i+2\}$sont disjoints sauf lorsque$j=i+2$ou$i=j+2.$Il n'y a donc pas d'ambiguïté pour déterminer l'inverse sauf si l'on est dans ce cas particulier, donc l'inverse existe sauf dans ce cas particulier. Mais même dans ce cas, les modèles$(a_i,a_{i+2},a_{i+4})$qui entraînent des retournements de bits sont sans ambiguïté.
Si$(a_i,a_{i+2},a_{i+4})=(1,0,0)$alors$a_{i+1}$sera retourné mais pas$a_{i+3}$. Alors$A_{i+1}=1\oplus a_{i+1},$et$A_{i+3}=a_{i+3}.$
Si$(a_i,a_{i+2},a_{i+4})=(1,0,1)$alors$a_{i+1}$sera retourné mais pas nécessairement$a_{i+3}$, cela dépendra de la valeur de$a_{i+6}=a_{i+1}$. Mais ce bit n'est pas impacté par l'argument précédent puisque$J_i$et$J_j$sont disjoints si$i=j+1\pmod 2.$
Il existe donc une application inverse unique.
Remarque : En général, aller entre les formulations de champ d'extension "indépendantes de la base" des permutations et les permutations de vecteurs de bits "dépendantes de la base" n'est pas simple. Je ne vois pas de formulation de champ d'extension indépendante de base immédiate pour cette permutation, et comme indiqué dans les commentaires à la question, de telles formulations obtenues (disons) par interpolation de Lagrange peuvent être assez compliquées et de haut degré.
La$\chi$fonction est définie et analysée dans Joan Daemen Ph.D. Thèse
- Stratégies de conception de fonctions de chiffrement et de hachage basées sur la cryptanalyse linéaire et différentielle, 1995
Le chapitre 6: Shift-Invariant Transformations (SIT) est l'endroit où la théorie est mentionnée. Je vais en donner un aperçu (beaucoup de définitions et de résultats).
Les propriétés des SIT qui les rendent utiles ;
- Dans le matériel, ces transformations peuvent être implémentées sous la forme d'un réseau interconnecté de "processeurs" de sortie 1 bit identiques.
- L'invariance de décalage garantit que la charge de calcul est répartie de manière optimale.
- Dans les logiciels, leur régularité permet des implémentations efficaces en employant des opérations logiques au niveau du bit.
- De plus, les transformations binaires invariantes par décalage peuvent être spécifiées par une seule fonction booléenne.
Les SIT sont très liés aux automates cellulaires finis qui se concentrent sur la structure et le modèle à long terme au fil du temps. Ce travail se concentre sur les aspects à court terme de l'inversibilité et des propriétés de propagation et de corrélation locales.
Définition 6.1 : Une transformation$\phi: \mathcal{A} \to \mathcal{A}$est invariant par décalage si
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$où$\mathcal{A}$est tous les états possibles.
Ensuite, il a défini les cartes locales où l'image ne dépend que de certaines des entrées.
Théorème 6.1 (D. Richardson ) Si une transformation$\phi$avec fini$\nu$est inversible, alors son inverse$\phi^{−1}$est une transformation invariante par décalage avec fini$\nu$.
Où$\nu$définit le voisinage, voir 6.3 Cartes locales . Ce théorème ne fournit pas explicitement une construction de l'inverse.
Section 6.6 Transformations non linéaires avec fini$\nu$est l'endroit où l'action commence.
Ici, la carte locale est spécifiée par un ensemble de motifs, appelés paysages complémentaires (CL). La valeur d'un composant est complétée si son voisinage prend l'un de ces motifs. Un paysage est un motif composé de symboles$1, 0$, et$\textbf{-}$dénotant "ne s'en soucie pas", positionné par rapport à une origine, notée par$∗$. Dans ce contexte, l'état tout à zéro sera désigné par$0^*$et l'état tout-un par$1^*$.
L'inverse de$\chi$est abordé dans les sections d'inversibilité locale et globale qui nécessitent une théorie plus approfondie. Une belle lecture à apprendre si vous le souhaitez.
Donc, comme je l'ai dit dans les commentaires, soit on peut chercher toutes les permutations possibles pour voir la propriété désirée, soit on regarde dans la théorie comme l'a fait Daemen. Ils ont utilisé cette théorie des années plus tard dans la construction de l'éponge où$\chi$est la seule partie non linéaire du SHA-3.
Comme ma première question a été répondue en détail dans les réponses de kodlu et kelalaka, je voulais partager les résultats que j'ai recueillis sur ma deuxième question depuis la publication :
Quelles sont les propriétés que la fonction booléenne doit satisfaire pour qu'elle aboutisse à une permutation ?
Au cours de nombreuses lectures supplémentaires, j'ai découvert que cela semblait être une propriété bien (mais pas largement) connue. Par exemple indiqué et prouvé dans le chapitre 2.3.1 des fonctions booléennes vectorielles pour la cryptographie comme proposition 2 :
Une fonction (n, m) est équilibrée si et seulement si ses fonctions composantes sont équilibrées, c'est-à-dire si et seulement si, pour tout v ∈ non nul$F^2_m$, la fonction booléenne v · F est équilibrée.
avec le fait supplémentaire du chapitre 2.3 :
les fonctions (n, n) équilibrées sont les permutations sur$F^2_n$
Ainsi, une fonction (n, n) est une permutation, si et seulement si elle est équilibrée selon la définition ci-dessus.
En d'autres termes, chaque fonction de composant doit être équilibrée, ainsi que toute combinaison possible de fonctions de composant, incl. toutes les fonctions à la fois, doivent être équilibrées.
Soit dit en passant, cette propriété est également énoncée, de manière moins évidente, dans Cipher and Hash Function Design Strategies based on linear and differentielle cryptanalysis, 1995 Theorem 5.1
Cela signifie également que la vérification de cette propriété pour le cas général des fonctions plus grandes, par exemple 64 bits de large (n = 64), n'est pas réalisable car cela nécessiterait de vérifier l'équilibre pour 2 ^ 64 - 1 combinaisons différentes (pour 2 ^ 64 entrées possibles chacune) . Certaines astuces ou raccourcis seront donc probablement nécessaires.