Hilakantojen Gram-Schmidt -ortogonalisaatio ja LDL*-hajotelma

Abstract

Hilasalausten käyttö on yleistynyt suuresti kvanttitietokoneiden kehityksen myötä. Hiloja hyödyntävää salausta kutsutaan "kvanttiturvalliseksi" sen murtamisen vaikeuden vuoksi, mutta niissä tehtävät laskut ovat myös vaativia. Moniulotteiset hilat, vaikkakin ovat turvallisia, vaativat tehokkuutta laskutoimituksissa. Tämän takia yleinen ongelma hilasalausten käytössä on laskutoimitusten keventäminen.

Hilat ovat vektoriavaruuksien kantavektoreiden kokonaislukukertoimista muodostuvia pisteverkkoja. Tästä syystä erikantaisten hilavektoreiden yhteen- ja kertolaskut voivat aiheuttaa tilanteita, joissa lasku tuottaa hilapisteistä eroavia tuloksia. Hilasalaus perustuu siihen, kuinka näitä laskettuja vektoreita voidaan tulkita eri hilapisteiksi erilaisten kantojen avulla. Niin sanottua lähimmän vektorin ongelmaa hyödyntää muun muassa NTRU-hilasalaus, jossa julkinen avain perustuu siihen, että kanta on "hyvin vähän ortogonaalinen". Niin sanottu virhepolynomi aiheuttaa "huonolla" kannalla avattaessa epätarkkuuden, jolloin salatun viestin purkaminen epäonnistuu, sillä lähin hilapiste ei ole enää sama kuin hyvällä kannalla purkaessa.

Tutkielmassa esiteltävät osittaislinearisaatiokuvaukset V ja M toimivat työkaluina vektoreiden ja matriisien permutointiin siten, että saadaan uusia kantoja valmiina olevalle vektoriavaruudelle. Näitä kuvauksia voidaan myös hyödyntää Gram-Schmidt -ortgonalisaatioalgoritmiin sekä siihen liitännäiseen LDL*-hajotelmaan. GSO-algoritmi sekä LDL*-hajotelma toimivat kantojen ortogonalisointiin, jolloin niitä voidaan käyttää hilasalauksen olennaisiin laskutoimituksiin. Ducas ja Prest ovat artikkelissaan Fast Fourier Orthogonalization (2016) esitelleet nämä algoritmit ja kuinka niitä voidaan hyödyntää nopeuttamaan hilasalauksen yleisien ongelmien ratkaisua.