Kvanttiturvalliset salausmenetelmät ja HQC

Abstract

Tutkielmassa haetaan kryptografian, koodausteorian ja kvanttilaskennan kautta näkemystä kvanttiturvallisiin kryptografisiin järjestelmiin, erityisesti julkisen avaimen salausmenetelmään HQC.

Jokainen tänä päivänä käytetty IP-verkkojen välisen tietoliikenteen salausprotokollan TLS 1.3 määräämä avaimenvaihtoprotokolla perustuu diskreettien logaritmien ongelmaan, joka tulee murtumaan kvanttitietokoneiden realisoituessa. Vaihtoehtoisia avaimenvaihtomenetelmiä on ollut jo pitkään olemassa, mutta niiden käyttäminen on jäänyt taka-alalle sekä perinteisten menetelmien tehokkaan ja yksinkertaisen toteuttamisen, että pienen avainkoon vuoksi.

Aluksi tutkielmassa esitellään kvanttialgoritmilla murrettava RSA sekä kvanttiturvalliseksi oletettu AES. RSA on määritelty vanhenevaksi, eikä se ole mukana TLS 1.3 protokollassa. Sen esittely on silti mielekästä, sillä tekijöihin jako-ongelma, johon se perustuu, kuuluu samaan yleistettyyn ja kvanttialgoritmilla murrettuun ongelma-joukkoon kuin diskreettien logaritmien ongelma. RSA:n avulla saadaan myöhemmin tutkielmassa vertailtua klassisten algoritmien ja kvanttialgoritmien välisiä eroja.

Tutkielmassa esitellään myös koodausteorian peruskäsitteet ja kaikki HQC-salausmenetelmän kannalta oleelliset koodit. Näitä ovat sykliset koodit, Reed-Mullerin koodit, Reed-Solomonin koodit ja määriteltävät yhdistetyt RM-RS-koodit. Näiden määritelmien kautta nähdään, miten RM-koodeilla voidaan korjata hajanaisia virheitä tai “kohinaa”, kun taas RS-koodit korjaavat paremmin virherykelmiä.

Pohjatietojen viimeistelemiseksi tutkielmassa käydään läpi klassisia logiikkapiirejä ja -portteja, joiden pohjalta voidaan rakentaa vastaavia toimintoja toteuttavia kvanttilogiikkapiirejä. Tämän jälkeen esitellään kvanttitietokoneella toteutettavia menetelmiä, joilla saadaan aikaiseksi tiettyjä etuja verrattuna klassisiin tietokoneisiin, ja muokataan rakennettuja kvanttilogiikkapiirejä hyödyntämään esiteltyjä menetelmiä.

Kun on käsitelty riittävän kattavasti vaadittavat pohjatiedot, tutkielmassa siirrytään tarkastelemaan millaisten ongelmien uskotaan olevan kvanttiturvallisia. Hyvänä lähtökohtana on ongelma, jonka avulla voidaan simuloida kaikki muut ongelmat suhteellisen pienillä muunnoksilla. Jos tällainen ongelma olisi murrettavissa, niin silloin myös kaikki sillä simuloitavat ongelmat olisivat murrettavissa. Tämä antaa syyn uskoa tällaisten ongelmien olevan kvanttiturvallisia.

Tutkielman viimeisessä osiossa esitellään kvanttiturvalliseksi, standardisoiduksi avaimensalausprotokollaksi valittu HQC, havainnollistetaan esimerkein kuinka se toimii ja määritellään vaikeat ongelmat joiden perusteella sen uskotaan olevan kvanttiturvallinen. Lopuksi esitellään vielä näihin ongelmiin liittyvä avoin kysymys ja tämän kysymyksen eri vastausten seuraukset järjestelmän turvallisuudelle.