Hva er problemet med hard gitter? En tråd 🧵

Gitterbasert kryptografi bygger på en sentral utfordring: å finne en kort vektorløsning s til et system av lineære ligninger modulo et heltall q (vanligvis et primtall eller en primpotens). Dette kalles SIS-problemet (Short Integer Solution), enkelt i form, men ansett som vanskelig mot kvante-/klassiske angrep.

Det finnes to hovedversjoner: den inhomogene formen brukt som enveisfunksjon f_A(s) = A * s mod q i commitment-skjemaer, hvor vi løser A * s = t (mod q) gitt A og mål t...

... og det homogene SIS-problemet, som ber om å finne en kort s slik at A * s = 0 (mod q) for en stokastisk matrise A.

Forpliktelsesordningen er garantert bindende på grunn av SIS' hardhet. Hvis A * s = t = A * s', så er A * (s - s') = 0, noe som betyr at det å finne en annen s' løser det harde homogene SIS-problemet.

Kortheten til s (liten norm) er essensielt. Uten avgrensning s er løsningene trivielle ved bruk av klassisk lineær algebra. Denne normbegrensningen ligger til grunn for den vanskelige naturen til SIS å løse, selv mot kvantedatamaskiner.

Ajtais resultat fra 1996 koblet hardheten til SIS-problemet til løsning av verst-tilfelle gitterproblemer, og dannet grunnlaget for antakelser om post-kvantekryptografi.

SIS-problemet muliggjør komprimering fra en stor hemmelig vektor s (dimensjon M) til en kortere forpliktelse t. Matrisen A har dimensjonene N x M, hvor N vanligvis er knyttet til sikkerhetsparameteren, noe som gjør den attraktiv for nullkunnskapsbevis som krever kortfatthet.

Samlet sett er SIS lett å formulere, men ekstremt vanskelig å løse, og spiller en grunnleggende rolle i forpliktelser, nullkunnskapsbevis og bredere post-kvantesikkerhet.