Določeni kombinatorični objekti v spektralni domeni - križiščna analiza

Glavni cilj tega projekta je zagotoviti nadaljnjo analizo nekaterih kombinatornih objektov, ki so ključnega pomena v kriptografiji in ki izhajajo iz nekaterih težkih problemov v diskretni matematiki, ki vključujejo diskretne eksponentne vsote. Natančneje, obstajajo posebni razredi polinomov nad končnimi polji, ki imajo izjemne (optimalne) lastnosti glede na dve dobro uveljavljeni kriptoanalitični metodi, diferencialno in linearno kriptoanalizo. Ti razredi funkcij (oz. polinomov) se imenujejo APN funkcije (skoraj popolnoma nelinearne – almost perfect nonlinear) in AB funkcije (skoraj ukrivljene – almost bent), katerih splošne metode načrtovanja še niso bile razvite. Te funkcije so tudi zelo tesno povezane s teorijo načrtovanja in relativnimi diferenčnimi množicami. Naj opišemo, APN funkcije so preslikave iz GF(2)^n v GF(2)^n, za katere je značilna lastnost, da ima enačba oblike F(x⊕a)⊕F(x)=b nad GF(2)^n natanko 0 ali 2 rešitvi za katerakoli elementa a in b v GF(2)^n. Preprosta zahteva, da je APN preslikava F tudi permutacija za sodo vrednost n, vodi do izjemno težkega problema (običajno imenovanega VELIKI APN problem, ki je odprt zadnjih 40 let) kako najti takšno preiskavo za sode n > 6. Po drugi strani pa AB funkcije nad GF(2)^n, ki obstajajo samo za lihe vrednosti n in so nujno vedno tudi APN, dosegajo največjo možno odpornost proti linearni kriptoanalizi. Naš glavni namen je poglobiti naše dosedanje poskuse iskanja splošnih rešitev, vezanih na načrtovanje in klasifikacijo teh funkcij. Medtem ko so tradicionalne metode večinoma osredotočene na analizo enostavnih polinomskih oblik nad končnimi polji (monomi in binomi), je prijavitelj tega projekta (skupaj z drugimi člani kripto skupine na UP FAMNIT) že začel raziskave v spektralni domeni, ki z uporabo Fourier/Walsheve transformacije prevede ta problem na problem določanja primernih spektralnih vrednosti za koordinatne funkcije (ki predstavljajo končno polje kot vektorski prostor). V kontekstu AB funkcij je mogoče koordinatne funkcije v spektralni domeni enostavno določiti z uporabo obstoječih tehnik načrtovanja (zlasti tistih, ki so bile nedavno predlagane v [16, 18, 19, 20]), vendar je glavni izziv zagotoviti, da njihove linearne kombinacije ohranijo želene spektralne porazdelitve. Začetna analiza, opravljena pred kratkim v [1] kaže na regularno obnašanje neničelnih spektralnih vrednosti koordinatnih funkcij. Natančneje, te vrednosti v bistvu definirajo podprostore določene dimenzije in zdi se, da je njihovo primerno presečišče (skupaj z dodelitvijo predznaka) odločilno za izpeljavo popolnih kombinatornih objektov, kot so AB funkcije. Danes ni o obnašanju teh presečišč skupaj z ustreznim predznakom spektralnih vrednosti znanega skoraj nič. Edini rezultati v tej smeri so bili pred kratkim pridobljeni v [1] z uporabo sofisticiranega računalniškega iskanja, kjer so bili določeni razredi AB funkcij skonstruirani za relativno majhne lihe vrednosti n < 9. Zato je potrebna nadaljnja analiza in boljše razumevanje rezultatov, pridobljenih z računalniškimi simulacijami. Položaj je precej podoben v primeru APN funkcij, kjer je večina teoretičnih rezultatov spet vezanih na monome ali binome. Še posebej v primeru, ko je vrednost n soda, vsebujejo poznane družine APN številne tako imenovane ukrivljene funkcije. Običajno so preostale komponente komponent bodisi pol-ukrivljene (semi-bent) ali funkcije spektra 5ih vrednosti, pri čemer mora biti njihova medsebojna interakcija ponovno popolna za izgradnjo APN funkcij. Trdno verjamemo, da nam bodo različni razredi ukrivljenih funkcij, vgrajenih v APN funkcije, podali strukturno različne objekte, kar je razumna hipoteza in izhodiščna pobuda za predlagani projekt. Naš končni cilj je raziskati obnašanje komponentnih funkcij v spektralni domeni in razviti nekaj teoretičnih rezultatov, vezanih na načrtovanje AB in APN funkcij.