BIKE : koodipohjainen avaimenkapselointimekanismi

Abstract

Perinteiset salausmenetelmät perustuvat usein lukuteorian laskennallisesti haastaviin ongelmiin, kuten diskreetin logaritmin laskemiseen tai suurten lukujen tekijöihin jakamiseen. Kvanttialgoritmien myötä tarvitaan kuitenkin vahvempia menetelmiä, ja erään kvanttiturvallisten algoritmien osa-alueen muodostaa koodipohjainen kryptografia. Tässä pro gradu -tutkielmassa perehdytään BIKE-skeeman (Bit Flipping Key Encapsulation) matemaattiseen ja algoritmiseen perustaan sekä sen turvallisuusominaisuuksiin. BIKE on kvanttiturvalliseksi suunniteltu kvasisyklisiin koodeihin perustuva avaimenkapselointimekanismi, joka mahdollistaa turvallisen yhteisestä avaimesta sopimisen kahden osapuolen välillä.

Tutkielman alussa tutustutaan aiheen matemaattiseen perustaan. Ensin tarkastellaan polynomirenkaita sekä syklisiä matriiseja ja osoitetaan, että skeemassa käytettävä polynomirengas on isomorfinen erään syklisistä matriiseista muodostetun renkaan kanssa. Toisena kokonaisuutena tarkastellaan koodausteoriaa ja erityisesti kvasisyklisiä koodeja, joihin skeeman toiminta perustuu. Tutkielmassa esitellään koodausteorian perusteet ja kvasisyklisiin koodeihin liittyen osoitetaan, että niistä voidaan muodostaa permutoimalla ekvivalentti koodi, jonka tarkistusmatriisi koostuu syklisistä lohkoista. Näitä ominaisuuksia havainnollistetaan konkreettisin esimerkein ja koodien polynomiesityksiä hyödyntäen.

Käsiteltyyn matemaattiseen perustaan pohjaten tutkielmassa kuvataan BIKE-skeeman toiminta vaihe vaiheelta. Aluksi luodaan yleiskatsaus tiivistefunktioihin, joiden käyttökohteista esitellään eheystarkistukset ja näennäissatunnaislukujen tuottaminen. Tämän jälkeen kuvataan esimerkein skeemassa käytettävät operaatiot, joita ovat avaimen luominen, avaimen kapselointi ja kapseloinnin avaaminen. Esimerkit on toteutettu Python-ohjelmalla, jonka koodi on esitetty tutkielman liitteissä. Erityistä huomiota kiinnitetään kapseloinnin avaamisessa käytettävään iteratiiviseen dekooderiin sekä tarvittavien polynomioperaatioiden tehokkaaseen toteutukseen, millä on oleellinen merkitys skeeman suorituskyvyn kannalta.

Skeeman toiminnan kuvaamisen jälkeen tarkastellaan muodollisesti sen turvallisuusominaisuuksia. Tutkielmassa määritellään kryptografisille järjestelmille keskeinen erottumattomuusominaisuus sekä IND-CPA- ja IND-CCA-turvallisuusmäärittelyt, jotka kuvaavat järjestelmän vastustuskykyä erilaisia hyökkäyksiä vastaan. Tähän nojautuen osoitetaan, että BIKE-skeema on IND-CPA-turvallinen, kun skeemaan liittyvät koodausteorian vaikeat ongelmat oletetaan riittävän haastaviksi. Lisäksi tarkastellaan IND-CCA-turvallisuuden merkitystä sekä sitä, millä ehdoilla skeema täyttää tämän vahvemman turvallisuusmäärittelyn. Lopuksi teoreettiseen turvallisuustarkasteluun tuodaan käytännön näkökulmaa esittelemällä GJS-hyökkäys, joka voi mahdollistaa hyökkääjälle salaisen avaimen selvittämisen tietyissä tilanteissa.