Kilka pytań dotyczących budowania permutacji z funkcji boolowskich
Widziałem wiele przykładów funkcji boolowskich używanych jako permutacja.
Na przykład funkcja Keccak Chi: 2.3.1 :
z https://keccak.team/figures.html
Lub jako wzór: dla $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ z indeksami obliczonymi modulo 5
Pierwszym pytaniem byłoby: jakie jest uzasadnienie (lub dowód), dlaczego jest to permutacja?
Drugi, pokrewny: jakie są właściwości, funkcja boolowska musi spełniać, że skutkuje permutacją?
A teraz co do odwrotności takiej permutacji.
Czy istnieją jakieś ogólne metody / algorytmy do znalezienia odwrotności takiej konstrukcji?
Jakie są również główne czynniki wpływające na złożoność odwrotności (liczba zmiennych, stopień algebraiczny itp.)?
A jeśli taka metoda zostanie zastosowana do większego wkładu - powiedzmy $i=\{0..127\}$, czy odwrotność jest trudniejsza do obliczenia, jeśli funkcja ma tylko kilka (jak 3 dla Chi), czy też wiele, powiedzmy 128, zmiennych wejściowych?
Wszelkie odpowiedzi / wskazówki są mile widziane.
Odpowiedzi
Ogólne pytanie algebraiczne jest wieloaspektowe i może być dość skomplikowane. Niektóre zależą od przestrzeni wektorowej, inne od właściwości pola rozszerzenia.
Jak wspomniano w komentarzach, sprawdzenie właściwości może być prostsze.
Odpowiedziałem na pokrewne pytanie Przykłady zbalansowanych bitowo funkcji boolowskich z wieloma wyjściami
Wspomniane tam artykuły Nyberga są
K. Nyberg, Różnicowo jednolite mapowania dla kryptografii , 1993 i
K Nyberg, Perfect nonlinear S-box , 1992
oba są łatwo zlokalizowane w Google Scholar.
Edycja : keccak$\chi$ mapy $\{0,1\}^5$ Do siebie.
Użyję $a_i$ jako dane wejściowe i $A_i$ jako zmienne wyjściowe, jak w edytowanym pytaniu.
Liczenie indeksów modulo 5, jeśli nie ma $i$ takie że $(a_i,a_{i+2})=(0,1)$ następnie $\chi$ma stały punkt dla tego wejścia. Pozwolić$W=\{i: (a_i,a_{i+2})=(0,1)\},$ wtedy ogólne odwzorowanie po prostu odwraca należące do niego bity $i.$
Zwróć uwagę, że zestawy $J_i,J_j$ gdzie $J_i=\{i,i+2\}$ są rozłączne, chyba że kiedy $j=i+2$ lub $i=j+2.$Nie ma więc dwuznaczności przy określaniu odwrotności, chyba że jesteśmy w tym szczególnym przypadku, a zatem odwrotność istnieje z wyjątkiem tego specjalnego przypadku. Ale nawet w tym przypadku wzory$(a_i,a_{i+2},a_{i+4})$ które skutkują bitflipami, są jednoznaczne.
Gdyby $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ następnie $a_{i+1}$ zostanie odwrócony, ale nie $a_{i+3}$. Więc$A_{i+1}=1\oplus a_{i+1},$ i $A_{i+3}=a_{i+3}.$
Gdyby $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ następnie $a_{i+1}$ zostanie odwrócona, ale niekoniecznie $a_{i+3}$, to będzie zależeć od wartości $a_{i+6}=a_{i+1}$. Ale na ten bit nie ma wpływu poprzedni argument od tego czasu$J_i$ i $J_j$ są rozłączne, jeśli $i=j+1\pmod 2.$
Tak więc istnieje unikalne odwrotne odwzorowanie.
Uwaga : Generalnie przechodzenie pomiędzy "niezależnymi od bazy" formułami pól rozszerzających permutacji a "zależnymi od bazy" permutacjami wektorów bitowych nie jest proste. Nie widzę natychmiastowego sformułowania niezależnego pola rozszerzającego dla tej permutacji, a jak wskazano w komentarzach do pytania, takie sformułowania otrzymane (powiedzmy) przez interpolację Lagrange'a mogą być dość skomplikowane i mają wysoki stopień.
Plik $\chi$funkcja została zdefiniowana i przeanalizowana przez dr Joan Daemen. Praca dyplomowa
- Strategie projektowania funkcji szyfru i skrótu oparte na kryptoanalizie liniowej i różnicowej, 1995
Rozdział 6: Transformacje niezmiennicze z przesunięciem (SIT) to miejsce, w którym wspomniano o teorii. Przedstawię to w skrócie (wiele definicji i wyników).
Właściwości SIT, które czynią je użytecznymi;
- W przypadku sprzętu te transformacje mogą być implementowane jako połączona tablica identycznych 1-bitowych „procesorów” wyjściowych.
- Niezmienność przesunięcia zapewnia optymalny rozkład obciążenia obliczeniowego.
- W oprogramowaniu ich regularność pozwala na wydajne implementacje dzięki zastosowaniu bitowych operacji logicznych.
- Co więcej, binarne transformacje niezmienne z przesunięciem mogą być określone przez pojedynczą funkcję boolowską.
SIT są bardzo powiązane ze skończonymi automatami komórkowymi, które koncentrują się na długoterminowej strukturze i wzorcu w czasie. Praca ta koncentruje się na krótkoterminowych aspektach odwracalności oraz lokalnych właściwościach propagacji i korelacji.
Definicja 6.1: Transformacja$\phi: \mathcal{A} \to \mathcal{A}$jest niezmienna dla przesunięcia, jeśli
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ gdzie $\mathcal{A}$ to wszystkie możliwe stany.
Następnie zdefiniował mapy lokalne, w których obraz zależy tylko od niektórych danych wejściowych.
Twierdzenie 6.1 (D. Richardson) Jeśli transformacja$\phi$ ze skończonym $\nu$ jest odwracalna, to jest odwrotna $\phi^{−1}$ jest niezmienną zmianą transformacji ze skończonym $\nu$.
Gdzie $\nu$definiuje otoczenie, patrz 6.3 Mapy lokalne . To twierdzenie nie dostarcza jawnie konstrukcji odwrotności.
Sekcja 6.6 Nieliniowe transformacje o skończonej $\nu$ to miejsce, w którym rozpoczyna się akcja.
Tutaj lokalną mapę określa zestaw wzorców, zwanych krajobrazami uzupełniającymi (CL). Wartość składnika jest uzupełniana, jeśli jego otoczenie przybiera jeden z tych wzorców. Krajobraz to wzór składający się z symboli$1, 0$, i $\textbf{-}$ oznaczający „nie obchodzi mnie to”, umieszczony w stosunku do pochodzenia, oznaczony przez $∗$. W tym kontekście stan zerowy będzie oznaczony przez$0^*$ i stan „wszystko jedno” wg $1^*$.
Odwrotność $\chi$jest omawiana w lokalnych i globalnych sekcjach odwracalności, które wymagają głębszej teorii. Przyjemna lektura do nauczenia się, jeśli chcesz.
Tak więc, jak powiedziałem w komentarzach, albo można poszukać wszystkich możliwych permutacji, aby zobaczyć pożądaną właściwość, albo spojrzeć w teorii tak, jak zrobił to Daemen. Wykorzystali tę teorię wiele lat później w konstrukcji Gąbki, gdzie$\chi$ jest jedyną nieliniową częścią SHA-3.
Ponieważ szczegółowe odpowiedzi na moje pierwsze pytanie znalazły się w odpowiedziach kodlu i kelalaka, chciałem podzielić się wynikami, które zebrałem przy drugim pytaniu od czasu opublikowania:
Jakie są właściwości, które funkcja boolowska musi spełnić, że skutkuje permutacją?
Podczas wielu dodatkowych lektur odkryłem, że wydaje się, że jest to dobrze (ale nie szeroko) znana właściwość. Na przykład stwierdzone i sprawdzone w Vectorial Boolean Functions for Cryptography rozdział 2.3.1 jako Propozycja 2:
Funkcja (n, m) jest równoważona wtedy i tylko wtedy, gdy jej funkcje składowe są zrównoważone, to znaczy wtedy i tylko wtedy, gdy dla każdego niezerowego v ∈ $F^2_m$, funkcja boolowska v · F jest zrównoważona.
z dodatkowym faktem z rozdziału 2.3:
zrównoważone (n, n) -funkcje są permutacjami na $F^2_n$
Zatem funkcja (n, n) jest permutacją, wtedy i tylko wtedy, gdy jest zrównoważona zgodnie z powyższą definicją.
Innymi słowy, należy zbilansować każdą funkcję składową, a także każdą możliwą kombinację funkcji składowych, w tym. wszystkie funkcje muszą być zrównoważone.
Nawiasem mówiąc, ta właściwość jest również stwierdzona, mniej oczywiste, w Strategiach projektowania funkcji szyfru i funkcji skrótu opartych na kryptoanalizie liniowej i różnicowej, 1995 Twierdzenie 5.1
Oznacza to również, że sprawdzenie tej właściwości dla ogólnego przypadku dla większych funkcji, np. Szerokość 64-bitowa (n = 64), nie jest wykonalne, ponieważ wymagałoby sprawdzenia zrównoważenia dla 2 ^ 64 - 1 różnych kombinacji (dla 2 ^ 64 możliwych wejść każda) . Dlatego prawdopodobnie potrzebne będą pewne sztuczki lub skróty.