Loading...
Projekti / Programi vir: ARRS

Načrtovanje določenih popolnih diskretnih kombinatoričnih objektov v spektralni domeni

Raziskovalna dejavnost

Koda Veda Področje Podpodročje
1.01.00  Naravoslovje  Matematika   

Koda Veda Področje
P001  Naravoslovno-matematične vede  Matematika 
Ključne besede
šifrirni algoritmi, substitucijske škatle, bločne šifre, ukrivljene funkcije
Vrednotenje (pravilnik)
vir: COBISS
Raziskovalci (9)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacij
1.  37552  dr. Nastja Cepak  Matematika  Raziskovalec  2019 - 2020  15 
2.  32518  dr. Ademir Hujdurović  Matematika  Raziskovalec  2019 - 2020  92 
3.  51980  Sadmir Kudin  Matematika  Mladi raziskovalec  2019 - 2020 
4.  23501  dr. Boštjan Kuzman  Matematika  Raziskovalec  2019 - 2022  234 
5.  02507  dr. Aleksander Malnič  Matematika  Raziskovalec  2019 - 2022  243 
6.  02887  dr. Dragan Marušič  Matematika  Raziskovalec  2019 - 2022  585 
7.  27777  dr. Enes Pasalic  Matematika  Vodja projekta/programa  2019 - 2022  124 
8.  32026  dr. Rok Požar  Matematika  Raziskovalec  2019 - 2022  37 
9.  23341  dr. Primož Šparl  Matematika  Raziskovalec  2019 - 2022  175 
Organizacije (2)
št. Evidenčna št. Razisk. organizacija Kraj Matična številka Štev. publikacij
1.  0588  Univerza v Ljubljani, Pedagoška fakulteta  Ljubljana  1627082  31.288 
2.  1669  Univerza na Primorskem, Inštitut Andrej Marušič  Koper  1810014007  9.997 
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
Zgodovina ogledov
Priljubljeno