Mikä on kovan hilan ongelma? Lanka 🧵

Hilapohjainen kryptografia perustuu keskeiseen haasteeseen: löytää lyhyt vektoriratkaisu s lineaaristen yhtälöiden järjestelmään, joka on moduloin kokonaisluku q (yleensä alkuluku tai alkuluku). Tätä kutsutaan SIS (Short Integer Solution) -ongelmaksi, joka on yksinkertainen muodoltaan mutta uskotaan vahvasti kvantti- ja klassisia hyökkäyksiä vastaan.

On kaksi pääversiota: epähomogeeninen muoto, jota käytetään yksisuuntaisena funktiona f_A(s) = A * s mod q sitoutumisskeemoissa, jossa ratkaistaan A * s = t (mod q) annettuna A ja kohde t...

... ja homogeeninen SIS-ongelma, jossa pyydetään löytämään lyhyt s siten, että A * s = 0 (mod q) satunnaismatriisille A.

Sitoumusjärjestelmä on taattu, että se on sitova SIS:n kovuuden vuoksi. Jos A * s = t = A * s', niin A * (s - s') = 0, mikä tarkoittaa, että toisen s' löytäminen ratkaisee vaikean homogeenisen SIS-ongelman.

S:n (pieni normi) lyhyys on olennaista. Ilman rajoitusta s ratkaisut ovat triviaaleja klassisen lineaarialgebran avulla. Tämä normirajoitus tukee SIS:n vaikeasti ratkaistavaa luonnetta, jopa kvanttitietokoneita vastaan.

Ajtain vuoden 1996 tulos yhdisti SIS-ongelman vaikeuden pahimman tapauksen hilaongelmien ratkaisemiseen, muodostaen perustan post-kvanttikryptografian oletuksille.

SIS-ongelma mahdollistaa pakkaamisen suuresta salaisesta vektorista s (dimensio M) lyhyempään sitoutumiseen t. Matriisi A on dimensionaalisesti N x M, missä N on tyypillisesti sidottu turvallisuusparametriin, mikä tekee siitä houkuttelevan nollatiedon todistuksille, jotka vaativat ytimekkyyttä.

Yhdessä ottaen SIS on helppo sanoa, mutta äärimmäisen vaikea ratkaista, sillä sillä on keskeinen rooli sitoumuksissa, nollatiedon todistuksissa ja laajemmassa post-kvanttiturvallisuudessa.