Homomorfiset salausjärjestelmät

Abstract

Tämä tutkielma käsittelee homomorfisia salausjärjestelmiä. Tutkielmassa annetaan yleiskuva siitä, mitä tarkoittaa homomorfinen salaus ja miten homomorfiset salausjärjestelmät jaotellaan sekä esitellään muutama tällainen salausjärjestelmä esimerkkeineen. Tärkeä osa tutkielmaa on erään täysin homomorfisen salausjärjestelmän yksityiskohtainen esittely. Lisäksi käsitellään lyhyesti homomorfisten salausjärjestelmien historiaa sekä niiden sovelluskohteita.

Kun kerätään suuria määriä tietoa, sen säilyttäminen ja sille suoritettava laskenta vaatii paljon resursseja. Jos käyttäjällä ei itsellään ole resursseja suorittaa tarvitsemaansa laskentaa, voi laskennan ulkoistaminen olla tarpeen. Mikäli laskentaa tehdään arkaluontoiselle tiedolle sen alkuperäisessä muodossa ja laskennan tekevä taho ei olekaan tietoturvallinen, voi tieto hyvinkin päätyä vääriin käsiin. Siispä olisi hyödyllistä, jos laskentaa voitaisiin suorittaa tiedolle niin, että se voidaan salata ennen sille suoritettavaa laskentaa ja pitää salatussa muodossa koko laskentaprosessin ajan. Homomorfiset salausjärjestelmät ovatkin juuri sellaisia järjestelmiä, joille yllä kuvailtu on mahdollista. Ne sallivat laskentaoperaatioiden suorittamisen tiedolle sen salatussa muodossa.

Homomorfisissa salausjärjestelmissä salausalgoritmi on homomorfismi, eli sellainen kuvaus, joka säilyttää ryhmän rakenteen, eli sen alkioiden väliset suhteet, lähtöjoukolta kuvajoukolle. Salausalgoritmin lähtöjoukko on selväkielisten viestien joukko ja kuvajoukko salattujen viestien joukko. Koska viestien väliset suhteet säilyvät, ei ole väliä suoritetaanko niille laskutoimituksia ennen homomorfista kuvausta lähtöjoukossa, vai vasta kuvajoukossa homomorfisen kuvauksen jälkeen. Tämä uniikki ominaisuus mahdollistaa laskentaoperaatioiden suorittamisen selväkielisille viesteille niin, että laskennan suorittaja käsittelee vain salattuja viestejä. Siispä arkaluontoiselle tiedolle tehtävän laskennan voi turvallisesti ulkoistaa esimerkiksi sellaisessa tilanteessa, jossa laskennan suorittavan tahon tietoturvan tasosta ei voida olla varmoja.

Homomorfiset salausjärjestelmät jaotellaan osittain ja täysin homomorfisiin sen mukaan, mitä laskentaoperaatioita ne sallivat tehtävän homomorfisesti viesteille salatussa muodossa. Osittain homomorfiset salausjärjestelmät sallivat homomorfisesti vain yhden laskutoimituksen, viestien summan tai tulon, kun taas täysin homomorfiset salausjärjestelmät sallivat homomorfisesti molemmat. Sekä osittain, että täysin homomorfisissa salausjärjestelmissä tärkeä ominaisuus on se, että homomorfisesti voidaan suorittaa rajoittamaton määrä näitä sallittuja laskutoimituksia. Kun homomorfisten laskutoimitusten määrää ei ole rajoitettu, voidaan viestien summaa ja tuloa yhdistelemällä muodostaa käytännössä kaikki viesteille laskettavissa olevat funktiot. Siispä täysin homomorfinen salausjärjestelmä sallii kaikkien mahdollisten funktioiden suorittamisen tiedolle sen ollessa salatussa muodossa.

Osittainen homomorfisuus on täyttä homomorfisuutta helpompi ominaisuus sisällyttää salausjärjestelmiin ja useat tunnetut salausjärjestelmät ovatkin osittain homomorfisia. Tunnettuja osittain homomorfisia salausjärjestelmiä ovat esimerkiksi RSA, ElGamal ja Paillier, joista kaksi viimeistä esitellään tässä tutkielmassa.

Täysin homomorfisen salausjärjestelmän rakentaminen on huomattavasti vaikeampaa. Tällaisen salausjärjestelmän käsite esiteltiin jo vuonna 1978, mutta sen muodostaminen säilyi avoimena ongelmana vuoteen 2009 asti, jolloin ensimmäinen toimiva täysin homomorfinen salausjärjestelmä julkaistiin. Tässä tutkielmassa käydään yksityiskohtaisesti läpi täysin homomorfinen salausjärjestelmä kokonaisluvuille, joka rakentuu samalla tavalla kuin ensimmäinen täysin homomorfinen salausjärjestelmä. Järjestelmän rakentaminen alkaa rajoitetusti täysin homomorfisesta salausjärjestelmästä, joka sallii sekä viestien summan, että tulon homomorfisesti, mutta vain rajoitetun määrän kertoja. Homomorfiset laskutoimitukset lisäävät salattuihin viesteihin virhettä, jonka koko kasvaa liian monen laskutoimituksen jälkeen niin suureksi, etteivät viestit enää aukea oikein. Rajoitetusti täysin homomorfista salausjärjestelmää muokataan niin, että sen avausalgoritmin laskenta kevenee sen verran, että järjestelmä sallii oman avausalgoritminsa suorittamisen homomorfisesti. Tämä ominaisuus mahdollistaa salattujen viestien päivittämisen, eli muokkaamisen niin, että ne sisältävät vähemmän virhettä. Päivitysprosessia kutsutaan bootstrapiksi ja sen avulla järjestelmästä voidaan lopulta tehdä täysin homomorfinen.