Hjem

Nye doktorgrader

Ny doktorgrad

Krypteringer som ligningssystemer og hvordan løse dem

Bjørn Møller Greve disputerer 07.12.18 for ph.d.-graden ved Universitetet i Bergen med avhandlingen Systems of Boolean equations, elimination theory, and applications to cryptography.

Kryptologi er et fagfelt som beskriver hvordan informasjon kan skjules ved hjelp av kryptering med en hemmelig nøkkel. Det å finne metoder for hvordan man kan knekke krypteringen kalles kryptoanalyse, og alle moderne krypteringsalgoritmer må gjennom kryptoanalyse for å bygge tillit til at krypteringen som brukes er sikker. En slik metode går ut på å beskrive sammenhengen mellom informasjon og kryptert tekst som et system av ikke-lineære ligninger, der alle variabler kan ta verdiene enten 0 eller 1. Slike systemer kalles Boolske ligningssystemer. Dersom det korresponderende systemet av ligninger løses, betyr det at man kan hente ut den hemmelige nøkkelen som er brukt i krypteringen. Den fundamentale sikkerheten til krypteringsalgoritmene er basert på nettopp vanskeligheten av å løse slike ligningssystemer.

Blokk-chiffer er de mest brukte algoritmene for å kryptere større mengder data, og har den egenskapen at de kan beskrives som store systemer av ikke-lineære Boolske ligninger av grad 2, med svært mange variabler. Gode blokk-chiffer er konstruert på en slik måte at graden til disse ligningene vokser eksponensielt dersom man prøver å begrense antall variable.Målet for avhandlingen er å studere hvordan slike ligningssystemer kan løses. Fokuset i avhandlingen er på eliminasjon av variabler, og er motivert av at mange variabler introdusert i et blokk-chiffer kan elimineres.

Avhandlingen består av fire artikler som analyserer de algebraiske egenskapene til Boolske ligningssystemer. I artiklene utvikles nye effektive algoritmer for eliminasjon av variabler og for å løse Boolske ligningssystemer. Spesielt er dette brukt til å analysere blokk-chiffer og til å avdekke egenskaper ved disse som tidligere ikke har vært kjent. Andre kryptografiske algoritmer har lignende beskrivelser. Arbeidet og verktøyene utviklet i denne avhandlingen er anvendbare også på mange andre områder innen informatikk.

Personalia

Bjørn Møller Greve er fødd i 1988 og oppvokst på Lindås i Nordhordaland utenfor Bergen. Han tok bachelorgrad i matematikk (2011) og mastergrad i ren matematikk (2013) ved Universitetet i Bergen. Han har jobbet med doktorgraden ved Simula UiB siden 2015 i samarbeid med Forsvarets Forsknings Institutt.