Wat is het Hard Lattice Probleem? Een draad 🧵

Rastergebaseerde cryptografie is afhankelijk van een centrale uitdaging: het vinden van een korte vectoroplossing s voor een systeem van lineaire vergelijkingen modulo een geheel getal q (meestal een priemgetal of een priemkracht). Dit wordt het SIS (Short Integer Solution) probleem genoemd, eenvoudig van vorm maar wordt als moeilijk beschouwd tegen quantum/classieke aanvallen.

Er zijn twee hoofdversies: de inhomogene vorm die wordt gebruikt als de eenrichtingsfunctie f_A(s) = A * s mod q in toezeggingsschema's, waarbij we A * s = t (mod q) oplossen gegeven A en doel t...

...en het homogene SIS-probleem, dat vraagt om een korte s te vinden zodat A * s = 0 (mod q) voor een willekeurige matrix A.

Het verbintenischema is gegarandeerd bindend door de moeilijkheidsgraad van SIS. Als A * s = t = A * s', dan betekent A * (s - s') = 0, wat betekent dat het vinden van een andere s' het moeilijke homogene SIS-probleem oplost.

De kortheid van s (kleine norm) is essentieel. Zonder s te begrenzen, zijn oplossingen triviaal met behulp van klassieke lineaire algebra. Deze normbeperking onderbouwt de moeilijk op te lossen aard van SIS, zelfs tegen quantumcomputers.

Ajtai's resultaat uit 1996 verbond de moeilijkheid van het SIS-probleem met het oplossen van de slechtste geval-latticeproblemen, wat een basis vormde voor aannames over post-kwantumcryptografie.

Het SIS-probleem maakt compressie mogelijk van een grote geheime vector s (dimensie M) naar een kortere verbintenis t. De matrix A heeft de afmetingen N x M, waarbij N doorgaans is gekoppeld aan de beveiligingsparameter, wat het aantrekkelijk maakt voor zero-knowledge bewijzen die beknoptheid vereisen.

Gecombineerd is SIS gemakkelijk te formuleren, maar extreem moeilijk op te lossen, en speelt het een fundamentele rol in verplichtingen, zero-knowledge bewijzen en bredere post-kwantum beveiliging.