Was ist das Hard Lattice Problem? Ein Thread 🧵

Gitterbasierte Kryptographie beruht auf einer zentralen Herausforderung: das Finden einer kurzen Vektorlösung s für ein System linearer Gleichungen modulo einer ganzen Zahl q (in der Regel eine Primzahl oder eine Primzahlpotenz). Dies wird als SIS (Short Integer Solution) Problem bezeichnet, das in seiner Form einfach, aber gegen Quanten-/klassische Angriffe als schwierig angesehen wird.

Es gibt zwei Hauptversionen: die inhomogene Form, die als die Einwegfunktion f_A(s) = A * s mod q in Verpflichtungsschemata verwendet wird, wo wir A * s = t (mod q) gegeben A und Ziel t lösen...

...und das homogene SIS-Problem, bei dem gefragt wird, ein kurzes s zu finden, sodass A * s = 0 (mod q) für eine zufällige Matrix A.

Das Verpflichtungsschema ist durch die Schwierigkeit von SIS garantiert bindend. Wenn A * s = t = A * s' ist, dann gilt A * (s - s') = 0, was bedeutet, dass das Finden eines anderen s' das schwierige homogene SIS-Problem löst.

Die Kürze von s (kleine Norm) ist entscheidend. Ohne eine Begrenzung von s sind die Lösungen trivial unter Verwendung klassischer linearer Algebra. Diese Normbeschränkung untermauert die schwer zu lösende Natur von SIS, selbst gegen Quantencomputer.

Ajtais Ergebnis von 1996 verband die Schwierigkeit des SIS-Problems mit der Lösung von Worst-Case-Gitterproblemen und bildete eine Grundlage für Annahmen der post-quantum Kryptographie.

Das SIS-Problem ermöglicht die Kompression von einem großen geheimen Vektor s (Dimension M) zu einem kürzeren Commitment t. Die Matrix A hat die Dimensionen N x M, wobei N typischerweise an den Sicherheitsparameter gebunden ist, was sie attraktiv für Zero-Knowledge-Beweise macht, die Kürze benötigen.

Insgesamt ist SIS leicht zu formulieren, aber extrem schwer zu lösen und spielt eine grundlegende Rolle bei Verpflichtungen, Zero-Knowledge-Beweisen und umfassender post-quanten Sicherheit.