Czym jest problem twardej siatki? Wątek 🧵

Kryptografia oparta na siatkach opiera się na centralnym wyzwaniu: znalezieniu krótkiego wektora rozwiązania s dla układu równań liniowych modulo liczbę całkowitą q (zwykle liczbę pierwszą lub potęgę liczby pierwszej). Nazywa się to problemem SIS (Short Integer Solution), prostym w formie, ale uważanym za trudny w obliczu ataków kwantowych/klasycznych.

Istnieją dwie główne wersje: forma niejednorodna używana jako funkcja jednokierunkowa f_A(s) = A * s mod q w schematach zobowiązań, gdzie rozwiązujemy A * s = t (mod q) mając A i docelowe t...

...i jednorodny problem SIS, polegający na znalezieniu krótkiego s, takiego że A * s = 0 (mod q) dla losowej macierzy A.

Schemat zobowiązań jest gwarantowany jako wiążący przez trudność SIS. Jeśli A * s = t = A * s', to A * (s - s') = 0, co oznacza, że znalezienie innego s' rozwiązuje trudny jednorodny problem SIS.

Krótkotrwałość s (mała norma) jest kluczowa. Bez ograniczenia s, rozwiązania są trywialne przy użyciu klasycznej algebry liniowej. To ograniczenie normy stanowi podstawę trudności w rozwiązaniu SIS, nawet w obliczu komputerów kwantowych.

Wynik Ajtaia z 1996 roku połączył trudność problemu SIS z rozwiązywaniem najgorszych problemów siatki, tworząc fundament dla założeń kryptografii post-kwantowej.

Problem SIS umożliwia kompresję z dużego wektora tajnego s (wymiar M) do krótszego zobowiązania t. Macierz A ma wymiary N x M, gdzie N jest zazwyczaj związane z parametrem bezpieczeństwa, co czyni ją atrakcyjną dla dowodów zerowej wiedzy wymagających zwięzłości.

Zebrane razem, SIS jest łatwe do sformułowania, ale niezwykle trudne do rozwiązania, odgrywając fundamentalną rolę w zobowiązaniach, dowodach zerowej wiedzy i szerszym bezpieczeństwie post-kwantowym.