JultikaUniversity of Oulu repository

Tiivistelmä

Tässä tutkielmassa perehdytään Falconiin, joka on yksi NISTin standardisointi prosessin finalisteista. Falcon on hilapohjainen digitaalinen allekirjoitusalgoritmi, jonka turvallisuus perustuu lyhyeen kokonaislukuratkaisuun (SIS). Tämän ongelman ratkaisemiseksi ei tällä hetkellä tunneta tehokasta algoritmia edes kvanttitietokoneiden tapauksessa. Tutkielmassa käydään läpi Falconin pääalgoritmien toimintaa korkealla tasolla ja syvennytään tarkemmin sen avainten luontiprosessiin.

Aluksi esitellään tutkielmassa käytettäviä matemaattisia määritelmiä ja lauseita. Tarkoitus on antaa lukijalle vaadittavat perustiedot tutkielmassa käytettäviin matemaattisiin rakenteisiin ja lainalaisuuksiin, joita hyödynnetään tutkielman myöhemmissä kappaleissa.

Tutkielman Luvussa 2 perehdytään kryptografian käsitteeseen, esitellään digitaalisen allekirjoituksen ja kvanttiturvallisen kryptografian konseptit, jotka ovat tässä tutkielmassa keskeisessä roolissa.

Kolmannessa luvussa määritellään hilat ja selitetään, miten ne liittyvät kryptografiaan. Samalla esitellään keskeisimmät hilaongelmat, joita kryptografiassa hyödynnetään. Lopuksi käsitellään SIS-ongelmaa ja NTRU-hiloja, jotka liittyvät keskeisesti Falconin toimintaan.

Luvussa 4 esitellään digitaalinen allekirjoitusalgoritmi Falcon. Aluksi käydään läpi Falconin rakenteelliset osat, perustiedot ja sen toteutuksessa käytetyt parametrit. Tämän jälkeen avataan korkealla tasolla Falconin pääoperaatioiden toimintaa algoritmitaulujen avustuksella. Näitä esiteltäviä operaatioita ovat avainten generointi, allekirjoitus ja allekirjoituksen todentaminen.

Tutkielman viimeisessä luvussa syvennytään Falconin avainten generointiprosessiin ja todennetaan siihen liittyvät algoritmit. Käytännössä siis jokainen algoritmitaulu käydään läpi siten, että todistetaan miksi algoritmille annetusta syötteestä seuraa välttämättä halutunlainen tuotos. Kappale on rakennettu siten, että algoritmit on käsitelty niin sanotusti käänteisessä järjestyksessä. Tällä saavutetaan tilanne, jossa algoritmia käsiteltäessä tunnetaan jo sen alialgoritmien toiminta ja näin saadaan kattava kuva koko avainten generointiprosessista.