Alcune domande sulla creazione di permutazioni da funzioni booleane
Ho visto più esempi di funzioni booleane utilizzate come permutazione.
Ad esempio la funzione Keccak Chi: 2.3.1 :
dahttps://keccak.team/figures.html
O come formula: per$i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$con indici calcolati modulo 5
La prima domanda sarebbe: qual è la motivazione (o la prova) per cui questa è una permutazione?
Il secondo, correlato: quali sono le proprietà che la funzione booleana deve soddisfare per ottenere una permutazione?
E ora per quanto riguarda l'inverso di tale permutazione.
Esistono metodi/algoritmi generici per trovare l'inverso di tale costruzione?
Inoltre, quali sono i principali fattori che contribuiscono alla complessità dell'inverso (numero di variabili, grado algebrico ecc.)?
E se un tale metodo viene applicato a un input più ampio, diciamo$i=\{0..127\}$, l'inverso è più difficile da calcolare, se la funzione ha solo poche (come il 3 per Chi) o molte, diciamo 128, variabili di input?
Eventuali risposte/indicazioni sono apprezzate.
Risposte
La domanda algebrica generale è multiforme e può essere piuttosto complicata. Alcuni dipendono dallo spazio vettoriale, altri dalle proprietà del campo di estensione.
Come accennato nei commenti, il controllo della proprietà può essere più semplice.
Ho risposto a una domanda correlata Esempi di funzioni booleane bilanciate a bit multipli
Gli articoli di Nyberg citati ci sono
K. Nyberg, mappature differenzialmente uniformi per la crittografia , 1993 e
K Nyberg, S-box perfette non lineari , 1992
entrambi facilmente individuabili su google scholar.
Modifica : il keccak$\chi$mappe$\{0,1\}^5$a se stesso.
userò$a_i$come ingresso e$A_i$come variabili di output come nella domanda modificata.
Conteggio indici modulo 5, se non c'è n$i$tale che$(a_i,a_{i+2})=(0,1)$poi$\chi$ha un punto fisso per quell'input. Permettere$W=\{i: (a_i,a_{i+2})=(0,1)\},$quindi la mappatura generale inverte solo i bit appartenenti a$i.$
Si noti che i set$J_i,J_j$dove$J_i=\{i,i+2\}$sono disgiunti tranne quando$j=i+2$o$i=j+2.$Quindi non c'è ambiguità per determinare l'inverso a meno che non ci troviamo in questo caso speciale, quindi l'inverso esiste tranne in questo caso speciale. Ma anche in questo caso gli schemi$(a_i,a_{i+2},a_{i+4})$che si traducono in bitflip non sono ambigui.
Se$(a_i,a_{i+2},a_{i+4})=(1,0,0)$poi$a_{i+1}$sarà capovolto ma non$a_{i+3}$. Così$A_{i+1}=1\oplus a_{i+1},$e$A_{i+3}=a_{i+3}.$
Se$(a_i,a_{i+2},a_{i+4})=(1,0,1)$poi$a_{i+1}$sarà capovolto ma non necessariamente$a_{i+3}$, che dipenderà dal valore di$a_{i+6}=a_{i+1}$. Ma quel bit non è influenzato dall'argomento precedente da allora$J_i$e$J_j$sono disgiunti se$i=j+1\pmod 2.$
Quindi esiste una mappatura inversa unica.
Nota : in generale, passare tra le formulazioni del campo di estensione "indipendenti dalla base" delle permutazioni rispetto alle permutazioni del vettore di bit "dipendenti dalla base" non è affatto semplice. Non vedo una formulazione del campo di estensione indipendente dalla base immediata per questa permutazione, e come sottolineato nei commenti alla domanda tali formulazioni ottenute (diciamo) dall'interpolazione di Lagrange, possono essere piuttosto complicate e di alto grado.
Il$\chi$la funzione è definita e analizzata in Joan Daemen Ph.D. Tesi
- Strategie di progettazione di funzioni cifrate e hash basate sulla crittoanalisi lineare e differenziale, 1995
Capitolo 6: Shift-Invariant Transformations (SIT) è dove viene menzionata la teoria. Ne fornirò un assaggio (molte definizioni e risultati).
Le proprietà dei SIT che li rendono utili;
- Nell'hardware, queste trasformazioni possono essere implementate come un array interconnesso di "processori" di output a 1 bit identici.
- L'invarianza di spostamento garantisce che il carico computazionale sia distribuito in modo ottimale.
- Nel software, la loro regolarità consente implementazioni efficienti utilizzando operazioni logiche bit a bit.
- Inoltre, le trasformazioni binarie shift-invariant possono essere specificate da una singola funzione booleana.
I SIT sono molto correlati agli automi cellulari finiti che si concentrano sulla struttura e sul modello a lungo termine nel tempo, questo lavoro si concentra sugli aspetti a breve termine dell'invertibilità e sulla propagazione locale e sulle proprietà di correlazione.
Definizione 6.1: Una trasformazione$\phi: \mathcal{A} \to \mathcal{A}$è shift-invariante se
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$dove$\mathcal{A}$è tutti gli stati possibili.
Quindi ha definito le mappe locali in cui l'immagine dipende solo da alcuni degli input.
Teorema 6.1 (D. Richardson ) Se una trasformazione$\phi$con finito$\nu$è invertibile, allora il suo inverso$\phi^{−1}$è una trasformazione invariante allo spostamento con finito$\nu$.
Dove$\nu$definisce il quartiere, vedere 6.3 Mappe locali . Questo teorema non fornisce esplicitamente una costruzione dell'inverso.
Paragrafo 6.6 Trasformazioni non lineari con finito$\nu$è dove inizia l'azione.
Qui la mappa locale è specificata da un insieme di modelli, chiamati paesaggi complementari (CL). Il valore di un componente è complementare se il suo vicinato assume uno di questi modelli. Un paesaggio è un modello costituito da simboli$1, 0$, e$\textbf{-}$che denota "non importa", posizionato rispetto a un'origine, indicato da$∗$. In questo contesto, lo stato tutto zero sarà indicato con$0^*$e lo stato all-one by$1^*$.
L'inverso di$\chi$è discusso nelle sezioni di invertibilità locale e globale che richiedono un approfondimento teorico. Una bella lettura da imparare se vuoi.
Quindi, come ho detto nei commenti, o si può cercare tutte le possibili permutazioni per vedere la proprietà desiderata, oppure guardare nella teoria come ha fatto Daemen. Hanno usato questa teoria anni dopo nella costruzione di Sponge dove$\chi$è l'unica parte non lineare di SHA-3.
Poiché la mia prima domanda ha ricevuto una risposta dettagliata nelle risposte di kodlu e kelalaka, volevo condividere i risultati che ho raccolto sulla mia seconda domanda dopo la pubblicazione:
Quali sono le proprietà che la funzione booleana deve soddisfare per ottenere una permutazione?
Durante molte letture aggiuntive ho scoperto che questa sembra essere una proprietà ben nota (ma non ampiamente). Ad esempio affermato e dimostrato in Funzioni booleane vettoriali per la crittografia capitolo 2.3.1 come Proposizione 2:
Una (n, m)-funzione è bilanciata se e solo se le sue funzioni componenti sono bilanciate, cioè se e solo se, per ogni v ∈ diverso da zero$F^2_m$, la funzione booleana v · F è bilanciata.
con il fatto aggiuntivo del capitolo 2.3:
le funzioni bilanciate (n, n) sono le permutazioni su$F^2_n$
Quindi, una (n, n)-funzione è una permutazione, se e solo se è bilanciata secondo la definizione di cui sopra.
In altre parole, ogni funzione componente deve essere bilanciata, così come ogni possibile combinazione di funzioni componenti, incl. tutte le funzioni contemporaneamente, devono essere bilanciate.
A proposito, questa proprietà è anche affermata, meno ovviamente, in Cipher and Hash Function Design Strategies based on linear and Differential cryptanalysis, 1995 Teorema 5.1
Ciò significa anche che il controllo di questa proprietà per il caso generale per funzioni più grandi, ad esempio 64 bit di larghezza (n=64), non è fattibile in quanto richiederebbe il controllo del bilanciamento per 2 ^ 64 - 1 combinazioni diverse (per 2 ^ 64 possibili input ciascuna) . Quindi probabilmente saranno necessari alcuni trucchi o scorciatoie.