短整数解问题

$A$ 把许多短整数向量压到只有 $q^n$ 个综合值。若短候选多于综合值，抽屉原理迫使两个候选 $x,y$ 碰撞，差 $z=x-y$ 就满足 $Az=0$。这解释了为何列数 $m$ 足够大时短解存在，也解释了 SIS 哈希的碰撞结构。

从格角度看，同余条件从 ${\mathbb{Z}}^m$ 切出一个指数约为 $q^n$ 的子格。Minkowski 界给出某个非零向量长度至多约

（在满秩情形使用粗欧氏界）。这只是存在上界；若该值不低于 $q$，保证的向量可能仍落在平凡的 $q{\mathbb{Z}}^m$ 中。参数设计必须让“存在短点”和“短到排除平凡点”同时成立。

取 $q=7$、$n=1$、$m=3$，并令

向量 $z=(1,1,-1)$ 满足

因此在 $\beta =2$ 时它是合法短解，而且 $2<q$ 排除了 $7e_i$ 一类平凡解。该手工矩阵和低维参数只展示三个条件怎样同时检查，不代表随机实例的安全强度。

存在性也可用碰撞复算。若从盒子 $\{0,1,\dots ,r{\}}^m$ 取候选，且 $(r+1{)}^m>q^n$，必有不同 $x,y$ 使 $Ax=Ay$；于是 $z=x-y$ 满足 $\Vert z{\Vert }_{\mathrm{\infty }}\le r$。这给的是某个差向量，未保证它在指定 ${\ell }_2$ 界内，换范数时必须乘上至多 $\sqrt{m}$ 的因子。

若 $A$ 模 $q$ 不满行秩，余体积不一定是 $q^n$；若 $q$ 合数，还要按像的实际大小计算指数。机械套用 $q^n$ 会把 Minkowski 界写错。即便短解高概率存在，穷举时间也可能巨大；存在性不等于高效可求。

Ajtai 型归约表明，在特定参数增长下，若能以足够概率解决随机 SIS，就能求解某些一般格上的最坏情形近似问题。这是从最坏情形格问题到平均情形 SIS 的归约，不是“每个随机矩阵都和任意 SVP 实例等价”，也不覆盖任意 $m,q,\beta$。引用时应保留范数、近似因子与分布条件。

令 $h_A(x)=Axmodq$。若找到两个不同短输入 $x,y$ 且哈希相同，则 $x-y$ 给出 SIS 解；反过来，SIS 解可制造受控域中的碰撞。这一接口支撑格哈希、承诺与签名，但具体构造还须限定输入域，防止差向量超出 $\beta$ 或出现编码歧义。