Univerza na Primorskem
Fakulteta za matematiko, naravoslovje in informacijske tehnologije
Več informacij o projektu / More info about the project
Opis / Description
SLO:
Glavni cilj tega projekta je izboljšati naše razumevanje določenih kombinatoričnih objektov. Glavni med njimi so določeni specifični razredi (vektorskih) Boolovih funkcij in linearnih kod, ki nosijo dodatne lastnosti, ki so se izkazale za uporabne v določenih kriptografskih aplikacijah. Če naštejemo nekaj teh aplikacij, so sheme za deljenje skrivnosti (z uporabo minimalnih linearnih kod) ali kod za popravljanje napak v kontekstu postkvantne kriptografije (preko samo-pravokotnih kod).
Linearna koda (n, k, d) z abecedo iz končnega polja GF(q) je podprostor dimenzije k polja GF(q)ⁿ, katerega minimalna razdalja d mora biti maksimirana. Dobre linearne kode nad poljem GF(2) (ki so včasih optimalne) je mogoče izpeljati z uporabo nekaterih posebnih razredov vektorskih Boolovih funkcij, kot so APN (skoraj popolnoma nelinearne) in AB (skoraj ukrivljene) funkcije, ki so preprosto preslikave iz polja GF(2)ⁿ v polje GF(2)ⁿ.
Kot je že opozoril Cunsheng Ding leta 2020, vse projektivne binarne linearne kode izhajajo iz specifične Boolove funkcije, ko se tako imenovana metoda definirajoče množice uporabi za ustrezno podmnožico D polja GF(2)ⁿ. Vendar pa izbira množice D ni enostavna in ni natančnih pravil ali meril, ki bi jih lahko uporabili za njegovo optimalno izbiro. Iz znanih pristopov načrtovanja je razvidno, da je določena kombinatorna struktura nujno vsiljena za definirajoče nize (npr. podpora ukrivljeni funkciji) tako zaradi lažje analize, kot zaradi boljše kontrole parametrov kode. Zato se zdi, da ima osnovna kombinatorna struktura določenih razredov (vektorskih) Boolovih funkcij (kot so APN, AB, ukrivljene in platojske funkcije) v tem kontekstu ključno vlogo.
Naš glavni namen je poglobiti naše razumevanje povezave med projektivnimi linearnimi kodami, ki so optimalne, in posebnimi razredi Boolovih funkcij, ki generirajo takšne kode, s čimer poskušamo odgovoriti na pomembne odprte probleme, ki jih je postavil Cunsheng Ding (»The construction and weight distributions of all projective binary linear codes«). Kljub temu pa niso vse optimalne linearne kode projektivne, kar implicira, da je definirajoča množica multimnožica in problem določanja takšnih kod je sam po sebi težak. V tem kontekstu obstaja nekaj začetnih opazovanj (tekoče delo) na multimnožici D, ki ustvarja optimalne kode (kot modifikacija ukrivljene podpore), vendar ni ustreznega razumevanja tega procesa.
Čeprav je ta raziskovalna smer precej obsežna, je naš cilj tudi vzpostaviti ustrezen okvir za določanje (potencialno novih) funkcij APN z uporabo rezultatov teorije kodiranja. Najpomembneje je, da je lastnost APN mogoče navesti tudi v smislu njegove povezane dualne kode, zato obstaja tesna povezava med dvema na videz nepovezanima objektoma. Natančneje, funkcijo APN nad GF(2)ⁿ je mogoče alternativno podati prek paritetne matrike H velikosti (2ⁿ − 1) × 2ⁿ, katere ustrezna linearna koda ima najmanjšo razdaljo d = 5. Kar je samo po sebi precej zanimivo, čeprav te matrike postanejo velike, ker so njihove velikosti eksponentne glede na n. Ker so stolpci matrike H podani kot veriženje vhodnih in izhodnih vrednosti funkcije F, lahko analiziramo strukturo teh specifičnih matrik za znane razrede funkcij APN in poskušamo zagotoviti splošne rešitve za njihove konstrukcije.
Končni cilj predlaganega projekta je iskanje nadaljnjih povezav med določenimi pomembnimi diskretnimi strukturami, ki lahko povečajo naše znanje o njihovem strukturnem obnašanju.
EN:
The main goal of this project is to refine our understanding of certain combinatorial objects (mainly some specific classes of (vectorial) Boolean functions) and the design of linear codes that are characterized with some additional properties that are proved useful in certain cryptographic applications.
To name a few, these applications may concern implementation of secret sharing schemes (using minimal linear codes) or error-correcting codes in the context of postquantum cryptography (via self-orthogonal codes).
An (n, k, d) linear code with alphabet in a finite field GF(q) is simply a subspace of dimension k of GF(q)ⁿ, whose minimum distance d needs to be maximized.
Good linear codes over GF(2) (that are sometimes optimal) can be derived using some special classes of vectorial Boolean functions such as APN (almost perfect nonlinear) and AB (almost bent) functions, which are simply mappings from to .
As already noted by Cunsheng Ding in 2020, all projective binary linear codes stem from a certain Boolean function when the so-called defining set method is applied to a suitable subset D of . However, the choice of D is not straightforward and there are no exact rules or criteria that can be applied for its optimal selection.
From the known design approaches, it is apparent that a certain combinatorial structure is necessarily imposed for the defining sets (e.g. support of a bent function) both for the purpose of easier analysis and better control of the code parameters.
Therefore, the underlying combinatorial structure of certain classes of (vectorial) Boolean functions (such as APN, AB, bent and plateaued functions) seems to play a crucial role in this context.
Our main intention is to deepen our understanding of the connection between projective linear codes that are optimal and the particular classes of Boolean functions that give rise to such codes, thus trying to answer the important open problems raised by Cunsheng Ding (“The construction and weight distributions of all projective binary linear codes’’).
Nevertheless, not all optimal linear codes are projective which implies that the defining set is then a multiset and the problem of specifying such codes is intrinsically hard.
In this context, there are some initial observations (ongoing work) on the multiset D that generate optimal codes (as a modification of the bent support) but there is no proper understanding of this process.
Even though this research direction is quite plentiful, our goal is also to establish a proper framework of specifying (potentially new) APN functions using coding theory results.
Most notably, the property of being APN can also be stated in terms of its associated dual code and hence there exists a close connection between two seemingly unrelated objects.
More precisely, an APN function over GF(2)ⁿ can be alternatively specified through the parity check matrix H of size 2ⁿ – 1 x 2ⁿ whose corresponding linear code has minimum distance d = 5, which is quite interesting even though these matrices become large since their sizes are exponential in n.
Since the columns of H are given as concatenation of the input and output values of F, one can analyze the structure of these specific matrices for the known classes of APN functions and try to provide generic solutions towards their constructions.
Concludingly, the proposed project aims at finding further connections between certain important discrete structures which may increase our knowledge about their structural behaviour.