Projekti / Programi
Načrtovanje določenih popolnih diskretnih kombinatoričnih objektov v spektralni domeni
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.00 |
Naravoslovje |
Matematika |
|
| Koda |
Veda |
Področje |
| P001 |
Naravoslovno-matematične vede |
Matematika |
| Koda |
Veda |
Področje |
| 1.01 |
Naravoslovne vede |
Matematika |
šifrirni algoritmi, substitucijske škatle, bločne šifre, ukrivljene funkcije
Raziskovalci (9)
Organizacije (2)
Povzetek
Glavni cilj projekta je proučiti obstoj, tehnike načrtovanja in klasifikacijo določenih diskretnih kombinatoričnih objektov, ki odgovarjajo določenim razredom polinomov nad končnimi polji, ki igrajo pomembno vlogo v kriptografiji. Natančneje, nelinearna preslikava bloka n-bitov v blok m-bitov (tako imenovana substitucijska škatla oz. S-škatla (S-box)) je kriptografski primitiv bistvenega pomena pri načrtovanju družine simetričnih kriptografskih algoritmov, običajno imenovanih bločne šifre. Še posebej dva razreda teh nelinearnih preslikav sta izjemno pomembna glede na dobro uveljavljeni kriptoanalitični metodi diferencialne in linearne kriptoanaliz. To sta razreda APN funkcij (almost perfect nonlinear) in AB funkcij (almost bent). Prvi razred funkcij predstavimo kot preslikave iz polja GF(2)n v polje GF(2)n, so karakterizirane z lastnostjo, da imajo njihovi odvodi, torej enačba F(x+a)+F(x)=b nad poljem GF(2)n, ali 0, ali 2 rešitvi za katerikoli neničelni element a in katerikoli element b iz polja GF(2)n. Preprosta dodatna zahteva, da naj bo APN funkcija F tudi permutacija za sod n vodi do izjemno težkega problema (običajno imenovanega Veliki APN problem, ki ostaja odprt že zadnjih 40 let) iskanja takšnih preslikav za sod n ) 6. Drugi razred AB funkcij, ki obstaja samo za lihe n in je vsebovan v APN razredu, dosega maksimalno odpornost na linearno kriptoanalizo. Poleg uporabe v kriptografiji so te funkcije tesno povezane z teorijo načrtov in relativnih diferenčnih množic, kot je izpostavil A. Pott v pregledu [18].
Naš glavni namen je predstaviti učinkovito klasifikacijo in postopek načrtovanja teh dveh razredov funkcij, saj se izkaže, da so vsi poznani razredi pridobljeni z uporabo zelo specifičnih in neučinkovitih metod. Vzrok, da za oba tipa funkcij poznamo le nekaj neskončnih razredov (torej razredov funkcij, ki so APN oz. AB za neskončno dimenzij n), je v veliki meri težavnost na to vezanih matematičnih problemov, vendar tudi pomanjkanje naprednih načrtovalskih tehnik. Najpogostejši pristop zaradi pomanjkanja alternativ namreč temelji na proučevanju posebnih vrst polinomov nad končnimi polji, običajno monomov oblike xd za primeren d. To implicira, da je v primeru AB funkcij delo z eksponentnimi vsotami, ki odgovarjajo računanju Walsh-Hadamarjevega spektra, poenostavljeno. Delo celo z zelo dobrimi približki teh vsot (naj bodo Gaussove, Klostermanove, ali drugih tipov) je zelo težak problem, kar pojasni počasen napredek iskanja učinkovitejše klasifikacije in načrtovalskih metod teh funkcij. Za APN funkcije je položaj zelo podoben in večina načrtovalskih rezultatov je ponovno vezana na monome.
Na pristop, ki ga bomo uporabljali in razvijali v sklopu projekta, lahko gledamo kot na neke vrste inverzni inženiring. Natančneje, namesto da bi poskušali rešiti določene fundamentalno težke probleme, vezane na eksponentne vsote (kar ne izgleda realističen cilj), bomo delali na razširitvi tako imenovane spektralne metode, ki je bila nedavno uporabljena v [12,13,15] za učinkovito specifikacijo določenih zanimivih družin Boolovih funkcij, ki so tesno vezane na APN in AB funkcije (še posebno na slednje). Ker je bilo to teoretično ogrodje že razvito za Boolove funkcije in nam omogočilo načrtovanje funkcij z željenim spektralnim profilom neposredno preko spektralne domene, nam zdaj ostaja še, da bolje razumemo kakšne vrste simetrija spektralne domene omogoča pravilno izbiro n primerno sestavljenih Boolovih funkcij, ki implicirajo, da je funkcija F= (f1, ..., fn ) APN oziroma AB. Poleg teh rezultatov obstajajo v sklopu tega konteksta še druge regularnosti (glej Poglavje 14). Trdno verjamemo, da je naše pred kratkim razvito ogrodje primerno orodje za proučevanje opisanih funkcij na nov način, ki nam bo omogočil delno ali popolno rešitev zgoraj opisanih problemov, morda celo napredek pri obravnavi Velikega APN problema.
Pomen za razvoj znanosti
Problem klasificiranja in načrtovanja APN in AB funkcij je odprt že zadnja štiri desetletja in trenutno je fondamentalna struktura teh objektov večinoma neznana. Zaradi številnih praktičnih aplikacij omenjenih funkcij v kriptografiji in njihovih povezav z ostalimi kombinatoričnimi področji, bi nov vpogled v njihovo strukturo in izpeljava učinkovite načrtovalske metode zagotovo pritegnila pozornost celotne raziskovalne skupnosti na Slovenijo in še posebej na Koper.
To je še posebej res kar se tiče APN permutacij za sode n)6. Ali dokaz njihovega neobstoja, ali dokaz obstoja in najden način za njihovo načrtovanje je izjemno težka naloga in kakršenkoli teoretični napredek v tej smeri je neizmernega pomena in pomemben doprinos s področja. Še ena pomembna stran projekta je dejstvo, da je naša tehnika uporabe spektralne domene uporabna tudi pri reševanju drugih povezanih problemov. To je preprosta posledica tega, da nam lahko, vsaj kar se tiče kriptografskih primitivov, spektralne povezave šifriranih podatkov dajo nove vpoglede, vezane na načrtovanje in varnost.
Pomen za razvoj Slovenije
The problem of classifying and designing APN and AB functions has been actual for the last four decades and currently there is no much understanding related to the essential structure of these objects. Due to practical applications of these functions in cryptography and their connection to other fields in combinatorics, explaining their structure and deriving some efficient construction methods will certainly draw the attention of entire research community in this field to Slovenia and Koper in particular.
This is particularly true when APN permutations for even n ) 6 are considered. Either proving their non-existence or alternatively providing the existence and design of such functions, is an exceptionally hard task and any theoretical progress in this direction can be considered as a tremendous achievement and important contribution to the field.
Another contribution of this project is that our spectral domain design framework can also be useful to handle other related problems in the field. This is a simple consequence of the fact that , at least when cryptographic primitives are concerned, the spectral connection of the encrypted data might give other useful insights related to the design and security.
Najpomembnejši znanstveni rezultati
Vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Vmesno poročilo
