Gröbnerbasismetoden i kryptografi

Eit polynomsystem er eit likningssett som er satt saman av polynom i fleire variablar. Slike system er særleg viktige for fleire områder innan rein og anvend matematikk, då dei kan brukast til å modellera mange problem. Til dømes kan ei løysning gje svar på kva som er optimale konfigurasjonar innan robotikk. Eit forskingsfelt der å løysa polynomsystem er særs relevant, er kryptologi. I mange tilfelle er det nemleg mogleg å konstruera polynomsystem der løysninga svarar til ein hemmeleg nøkkel som er kritisk for at utveksling av informasjon er konfidensiell.

Denne avhandlinga utforskar Gröbnerbasismetoden, ein etablert berekningsmetode for å finna eksakte løysningar til polynomsystem. Metoden går ut på å finna eit nytt polynomsystem som har same løysningar som originalsystemet, men som er lettare å løysa (til dømes fordi det er lineært, eller inneheld likningar i berre ein variabel). Det er ikkje lett å føresjå kor lang tid denne metoden brukar for å finna løysninga til eit gjeve polynomsystem. Ein nøkkelparameter for å stadfesta kor mange grunnleggjande operasjonar som krevst av ein datamaskin er regularitetsgraden til polynomsystemet. Hovudresultatet i avhandlinga er eit prov på at viss polynomsystemet er tilstrekkeleg overbestemd (fleire likningar enn variable), då vil det høgst sannsynleg ha minst mogleg regularitetsgrad. Ein viktig konsekvens av dette resultatet er at viss eit polynomsystem har nok likningar, sett opp mot variable, kan dette løysast raskt. Kryptografiske protokollar basert på slike modellar kan dermed ikkje sjåast på som sikre.

Personalia

Andrea Tenti var fødd i Bolzano i 1992. Han har bodd i Noreg siden 2014 og byrja doktorgradsstudiane i 2016 ved Informatisk institutt.