什麼是硬格子問題？ 一個線程 🧵

基於格的密碼學依賴於一個核心挑戰：尋找一個短向量解 s，滿足一組模整數 q（通常是質數或質數的冪）的線性方程組。這被稱為 SIS（短整數解）問題，形式簡單，但被認為對量子/經典攻擊來說是困難的。

有兩個主要版本：在承諾方案中使用的不均勻形式，作為單向函數 f_A(s) = A * s mod q，其中我們在給定 A 和目標 t 的情況下解決 A * s = t (mod q)...

...以及同質的 SIS 問題，要求找到一個短的 s，使得 A * s = 0 (mod q) 對於隨機矩陣 A。

承諾方案因 SIS 的困難性而保證具有約束力。如果 A * s = t = A * s'，那麼 A * (s - s') = 0，這意味著找到一個不同的 s' 解決了困難的齊次 SIS 問題。

s（小範數）的短小性是至關重要的。如果不對 s 進行限制，使用傳統線性代數的解將是平凡的。這一範數限制是 SIS 難以解決的本質，即使面對量子計算機也是如此。

Ajtai 在 1996 年的結果將 SIS 問題的困難性與解決最壞情況的格問題聯繫起來，為後量子密碼學假設奠定了基礎。

SIS 問題使得從一個大型秘密向量 s（維度 M）壓縮到一個較短的承諾 t 成為可能。矩陣 A 的維度為 N x M，其中 N 通常與安全參數相關，這使得它對於需要簡潔性的零知識證明具有吸引力。

綜合來看，SIS 很容易表述，但卻極難解決，在承諾、零知識證明以及更廣泛的後量子安全中扮演著基本角色。