什么是硬晶格问题？ 一个线程 🧵

基于格的密码学依赖于一个核心挑战：找到一个短向量解 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 容易表述但极难解决，在承诺、零知识证明以及更广泛的后量子安全中发挥着基础性作用。