Einige Fragen zum Erstellen von Permutationen aus booleschen Funktionen
Ich habe mehrere Beispiele für boolesche Funktionen gesehen, die als Permutation verwendet werden.
Zum Beispiel die Funktion Keccak Chi : 2.3.1 :
aushttps://keccak.team/figures.html
Oder als Formel: für$i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$mit Modulo 5 berechneten Indizes
Die erste Frage wäre, was ist die Begründung (oder der Beweis), warum dies eine Permutation ist?
Die zweite, verwandte: Welche Eigenschaften muss die boolesche Funktion erfüllen, damit sie zu einer Permutation führt?
Und nun zur Umkehrung einer solchen Permutation.
Gibt es generische Methoden/Algorithmen, um die Umkehrung einer solchen Konstruktion zu finden?
Was sind die Hauptfaktoren für die Komplexität der Inversen (Anzahl der Variablen, algebraischer Grad usw.)?
Und wenn eine solche Methode auf eine größere Eingabe angewendet wird - sagen wir$i=\{0..127\}$, ist die Umkehrung schwieriger zu berechnen, wenn die Funktion nur wenige (wie die 3 für Chi) oder viele, sagen wir 128, Eingangsvariablen hat?
Alle Antworten/Hinweise sind willkommen.
Antworten
Die allgemeine algebraische Frage ist vielschichtig und kann ziemlich kompliziert sein. Einige hängen vom Vektorraum ab, andere von den Eigenschaften von Erweiterungsfeldern.
Wie in den Kommentaren erwähnt, kann die Überprüfung der Unterkunft einfacher sein.
Ich habe eine verwandte Frage beantwortet. Beispiele für Bit-ausgeglichene boolesche Funktionen mit mehreren Ausgängen
Die dort erwähnten Artikel von Nyberg sind
K. Nyberg, Differentiell einheitliche Abbildungen für die Kryptographie , 1993 und
K. Nyberg, Perfekte nichtlineare S-Boxen , 1992
beide leicht auf Google Scholar zu finden.
Edit : Der Keccak$\chi$Karten$\{0,1\}^5$zu sich selbst.
ich werde benützen$a_i$als Eingang u$A_i$als Ausgabevariablen wie in der bearbeiteten Frage.
Zählindizes modulo 5, falls es keine gibt$i$so dass$(a_i,a_{i+2})=(0,1)$dann$\chi$hat einen festen Punkt für diese Eingabe. Lassen$W=\{i: (a_i,a_{i+2})=(0,1)\},$dann invertiert die allgemeine Abbildung nur die zugehörigen Bits$i.$
Beachten Sie, dass die Sets$J_i,J_j$wo$J_i=\{i,i+2\}$sind disjunkt, außer wenn$j=i+2$oder$i=j+2.$Es gibt also keine Mehrdeutigkeit für die Bestimmung der Umkehrung, es sei denn, wir befinden uns in diesem Spezialfall, daher existiert die Umkehrung außer in diesem Spezialfall. Aber auch in diesem Fall die Muster$(a_i,a_{i+2},a_{i+4})$die zu Bitflips führen, sind eindeutig.
Wenn$(a_i,a_{i+2},a_{i+4})=(1,0,0)$dann$a_{i+1}$Gespiegelt wird aber nicht$a_{i+3}$. So$A_{i+1}=1\oplus a_{i+1},$und$A_{i+3}=a_{i+3}.$
Wenn$(a_i,a_{i+2},a_{i+4})=(1,0,1)$dann$a_{i+1}$wird umgedreht, muss aber nicht$a_{i+3}$, das hängt vom Wert von ab$a_{i+6}=a_{i+1}$. Aber dieses Bit wird seitdem nicht durch das vorherige Argument beeinflusst$J_i$und$J_j$sind disjunkt, wenn$i=j+1\pmod 2.$
Es existiert also eine eindeutige inverse Abbildung.
Anmerkung : Im Allgemeinen ist es kaum einfach, zwischen "basisunabhängigen" Erweiterungsfeldformulierungen von Permutationen und "basisabhängigen" Bitvektorpermutationen zu wechseln. Ich sehe keine unmittelbar basisunabhängige Erweiterungsfeldformulierung für diese Permutation, und wie in den Kommentaren zu der Frage ausgeführt, können solche Formulierungen, die (sagen wir) durch Lagrange-Interpolation erhalten werden, ziemlich kompliziert und hochgradig sein.
Das$\chi$Funktion wird in Joan Daemen Ph.D. definiert und analysiert. These
- Cipher and Hash Function Design Strategies based on linear and differentielle cryptanalysis, 1995
In Kapitel 6: Shift-Invariante Transformations (SIT) wird die Theorie erwähnt. Ich werde einen kleinen Einblick geben (viele Definitionen und Ergebnisse).
Die Eigenschaften von SIT, die sie nützlich machen;
- In der Hardware können diese Transformationen als ein miteinander verbundenes Array identischer 1-Bit-Ausgangs-„Prozessoren“ implementiert werden.
- Die Shift-Invarianz sorgt dafür, dass die Rechenlast optimal verteilt wird.
- In der Software ermöglicht ihre Regelmäßigkeit effiziente Implementierungen durch Verwendung bitweiser logischer Operationen.
- Darüber hinaus können binäre verschiebungsinvariante Transformationen durch eine einzige boolesche Funktion spezifiziert werden.
SITs sind sehr verwandt mit endlichen zellulären Automaten, die sich auf langfristige Strukturen und Muster im Laufe der Zeit konzentrieren. Diese Arbeit konzentriert sich auf die kurzfristigen Aspekte der Invertierbarkeit und der lokalen Ausbreitungs- und Korrelationseigenschaften.
Definition 6.1: Eine Transformation$\phi: \mathcal{A} \to \mathcal{A}$ist verschiebungsinvariant, falls
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$wo$\mathcal{A}$sind alle möglichen Zustände.
Dann wurden die lokalen Karten definiert, bei denen das Bild nur von einigen Eingaben abhängt.
Satz 6.1 (D. Richardson) Wenn eine Transformation$\phi$mit endlich$\nu$invertierbar ist, dann ist es invers$\phi^{−1}$ist eine verschiebungsinvariante Transformation mit endlich$\nu$.
Wo$\nu$definiert die Nachbarschaft, siehe 6.3 Lokale Karten . Dieser Satz liefert keine explizite Konstruktion der Inversen.
Abschnitt 6.6 Nichtlineare Transformationen mit endlich$\nu$Hier wird die Aktion gestartet.
Hier wird die lokale Karte durch eine Reihe von Mustern spezifiziert, die als Komplementärlandschaften (CL) bezeichnet werden. Der Wert einer Komponente wird ergänzt, wenn ihre Nachbarschaft eines dieser Muster annimmt. Eine Landschaft ist ein Muster, das aus Symbolen besteht$1, 0$, und$\textbf{-}$bezeichnet „egal“, positioniert relativ zu einem Ursprung, bezeichnet durch$∗$. In diesem Zusammenhang wird der Nur-Null-Zustand mit bezeichnet$0^*$und der All-One-Zustand durch$1^*$.
Das Gegenteil von$\chi$wird in Abschnitten über lokale und globale Invertierbarkeit gesprochen, die eine tiefere Theorie erfordern. Eine schöne Lektüre zum Lernen, wenn Sie möchten.
Wie ich in den Kommentaren sagte, kann man entweder nach allen möglichen Permutationen suchen, um die gewünschte Eigenschaft zu sehen, oder in der Theorie nachsehen, wie es Daemen getan hat. Sie verwendeten diese Theorie Jahre später bei der Schwammkonstruktion, wo$\chi$ist der einzige nichtlineare Teil des SHA-3.
Da meine erste Frage in den Antworten von kodlu und kelalaka ausführlich beantwortet wurde, wollte ich die Ergebnisse teilen, die ich seit dem Posten zu meiner zweiten Frage gesammelt habe:
Welche Eigenschaften muss die boolesche Funktion erfüllen, damit sie zu einer Permutation führt?
Durch viel zusätzliches Lesen entdeckte ich, dass dies eine gut (aber nicht weithin) bekannte Eigenschaft zu sein scheint. Zum Beispiel in Vectorial Boolean Functions for Cryptography Kapitel 2.3.1 als Proposition 2 angegeben und bewiesen:
Eine (n, m)-Funktion ist genau dann balanciert, wenn ihre Teilfunktionen balanciert sind, also genau dann, wenn für jedes von Null verschiedene v ∈ gilt$F^2_m$, ist die boolesche Funktion v · F ausgeglichen.
mit dem Zusatzfakt aus Kapitel 2.3:
balancierte (n, n)-Funktionen sind die Permutationen auf$F^2_n$
Eine (n, n)-Funktion ist also genau dann eine Permutation, wenn sie nach obiger Definition ausgeglichen ist.
Mit anderen Worten, jede Komponentenfunktion muss ausbalanciert werden, sowie jede mögliche Kombination von Komponentenfunktionen, inkl. alle Funktionen auf einmal, müssen ausbalanciert werden.
Übrigens wird diese Eigenschaft auch, weniger offensichtlich, in Cipher and Hash Function Design Strategies based on linear and differentielle cryptanalysis, 1995 Theorem 5.1 , angegeben
Dies bedeutet auch, dass die Überprüfung dieser Eigenschaft für den allgemeinen Fall für größere Funktionen, z. B. 64 Bit breit (n = 64), nicht möglich ist, da dies eine Überprüfung der Ausgewogenheit für 2 ^ 64 - 1 verschiedene Kombinationen (für jeweils 2 ^ 64 mögliche Eingaben) erfordern würde. . Daher sind wahrscheinlich einige Tricks oder Abkürzungen erforderlich.