J1-1694
printTemeljni projekt J1-1694
Načrtovanje določenih popolnih diskretnih kombinatoričnih objektov v spektralni domeni
Naslov projekta: Načrtovanje določenih popolnih diskretnih kombinatoričnih objektov v spektralni domeni
Vodja projekta: Enes Pasalic
Šifra projekta: J1-1694.
Tip projekta: temeljni projekt
Financer: Javna agencija RS za raziskovalno dejavnost (ARRS).
Raziskovalno področje (ARRS): 1.01.00 - Naravoslovno-matematične vede / Matematika.
Trajanje projekta: 1. 7. 2019 - 30. 6. 2022.
Cenovna kategorija projekta: B.
Letni obseg projekta: 0.41 FTE.
Sicris profil projekta je dostopen tukaj.
Raziskovalne organizacije, v okviru katere se izvaja projekt:
Univerza na Primorskem, Inštitut Andrej Marušič
Univerza v Ljubljani, Pedagoška fakulteta.
Člani raziskovalnega projekta:
|
Pasalic Enis (vodja) (ARRS šifra: 27777) |
Povzetek projekta:
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) v polje GF(2) , so karakterizirane z lastnostjo, da imajo njihovi odvodi, torej enačba F(x+a)+F(x)=b nad poljem GF(2) , ali 0, ali 2 rešitvi za katerikoli neničelni element a in katerikoli element b iz polja GF(2) . 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 x za primeren d. To implicira, da je v primeru AB funkcij delo z eksponentnimi vsotami, ki odgovarjajo računanju WalshHadamarjevega 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= (f , ..., f ) 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.