Co je problém tvrdé mřížky? Nit 🧵

Kryptografie založená na mřížkách se opírá o ústřední výzvu: nalezení krátkého vektorového řešení s soustavy lineárních rovnic modulo celého čísla q (obvykle mocniny prvočísla nebo prvočísla). Tento problém se nazývá SIS (Short Integer Solution), jednoduchý ve formě, ale věří se, že je tvrdý proti kvantovým/klasickým útokům.

Existují dvě hlavní verze: nehomogenní forma používaná jako jednosměrná funkce f_A(s) = A * s mod q v závazkových schématech, kde řešíme A * s = t (mod q) pro daný A a cíl t...

... a homogenní problém SIS, který hledá krátké s takové, že A * s = 0 (mod q) pro náhodnou matici A.

Schéma závazků je zaručeno závazné kvůli tvrdosti SIS. Pokud A * s = t = A * s', pak A * (s - s') = 0, což znamená, že nalezení jiného s' řeší těžký homogenní problém SIS.

Krátkost s (malá norma) je zásadní. Bez omezení s jsou řešení triviální pomocí klasické lineární algebry. Toto omezení normy je základem obtížně řešitelné povahy SIS, a to i proti kvantovým počítačům.

Ajtaiův výsledek z roku 1996 spojil obtížnost problému SIS s řešením nejhorších případů mřížkových problémů, čímž vytvořil základ pro předpoklady postkvantové kryptografie.

Problém SIS umožňuje kompresi z velkého tajného vektoru s (rozměr M) na kratší závazek t. Matice A má rozměry N x M, kde je N obvykle vázána na bezpečnostní parametr, což ji činí atraktivní pro důkazy s nulovým znalím, které vyžadují stručnost.

Společně je SIS snadné vyjádřit, ale extrémně obtížné ji vyřešit, hraje zásadní roli v závazcích, důkazech nulových znalostí a širší postkvantové bezpečnosti.