Vad är problemet med hårda gitter? En tråd 🧵

Gitterbaserad kryptografi bygger på en central utmaning: att hitta en kort vektorlösning s till ett system av linjära ekvationer modulo ett heltal q (vanligtvis ett primtal eller en primpotens). Detta kallas SIS (Short Integer Solution)-problemet, enkelt i formen men ansett vara svårt mot kvant-/klassiska attacker.

Det finns två huvudversioner: den inhomogena formen som används som envägsfunktion f_A(s) = A * s mod q i åtagandescheman, där vi löser A * s = t (mod q) givet A och mål t...

... och det homogena SIS-problemet, som kräver att hitta en kort s sådan att A * s = 0 (mod q) för en slumpmatris A.

Åtagandesystemet är garanterat bindande på grund av SIS svårighet. Om A * s = t = A * s', så är A * (s - s') = 0, vilket innebär att att hitta en annan s' löser det hårda homogena SIS-problemet.

Kortheten av s (liten norm) är avgörande. Utan begränsning s är lösningarna triviala med klassisk linjär algebra. Denna normbegränsning ligger till grund för SIS:s svårlösta natur, även mot kvantdatorer.

Ajtais resultat från 1996 kopplade svårigheten i SIS-problemet till att lösa värsta fall-gitterproblem och lade grunden för antaganden inom postkvantkryptografi.

SIS-problemet möjliggör komprimering från en stor hemlig vektor s (dimension M) till en kortare åtagande t. Matrisen A har dimensionerna N x M, där N vanligtvis är kopplad till säkerhetsparametern, vilket gör den attraktiv för nollkunskapsbevis som kräver kortfattadhet.

Tillsammans är SIS lätt att formulera men extremt svår att lösa, och spelar en grundläggande roll i åtaganden, nollkunskapsbevis och bredare post-kvantsäkerhet.