Funkcja krzywej
Funkcja boolowska z parzystą liczbą zmiennych nazywana jest funkcją krzywej - w terminologii angielskiej wygiętą - jeśli jej nieliniowość jest maksymalna. Odpowiada to znajdowaniu się w maksymalnej odległości - dla odległości Hamminga - zbioru liniowych funkcji boolowskich, zwanych także kodem Reeda i Müllera rzędu 1. Mamy ogólne ograniczenie nieliniowości funkcji boolowskich, ale to ograniczenie może można osiągnąć tylko wtedy, gdy liczba zmiennych jest parzysta. Ponadto w tym przypadku wiemy, jak konstruować funkcje osiągające ten limit, na przykład funkcję
jest zakrzywiony. Zbiór funkcji afinicznych tworzących przestrzeń wektorową na polu dwuelementowym, łatwo zauważyć, że jeśli jest zakrzywiona, to każda funkcja z funkcją afiniczną jest również zakrzywiona, ponieważ w tym przypadku i są w tej samej odległości od zbioru l funkcji afinicznych.
Ten obiekt matematyczny został wprowadzony przez O. Rothausa w 1976 roku (znał go już w latach 60. XX wieku).
Wysoce nieliniowe właściwości funkcji zakrzywionych są wykorzystywane w kryptologii do tworzenia S-Boxów (tablic podstawień), podobnie jak w szyfrze CAST-128. Zasada ta była rozważana już w 1992 roku przez C. kryptoanaliza różnicowa ”.
Funkcja zakrzywiona ma tę zaletę, że ma płaskie widmo (patrz transformata Fouriera lub transformata Hadamarda-Walsha ), co oznacza, że nie ma „dobrego” przybliżenia liniowego. Biorąc pod uwagę definicję tych funkcji, wydaje się to naturalne. Ta cecha umożliwia przeciwdziałanie kryptoanalizie liniowej .
Istotną wadą tych funkcji jest to, że nie są one zbalansowane: nie mogą przyjmować wartości 0 tyle razy, co wartość 1. Dlatego niektóre aplikacje należy wykluczyć, ponieważ odchylenie wprowadzone przez zakrzywioną funkcję uczyniłoby system szyfrowania podatnym na ataki na ataki inne niż liniowa kryptoanaliza . W pewnym sensie jest to powracający problem w projektowaniu szyfrów symetrycznych: nie możemy jednocześnie mieć najlepszej odporności na wszystkie znane ataki. Zakrzywione funkcje są optymalne do liniowej kryptoanalizy, ale nie na przykład do ataków korelacyjnych.