短整數解決方案是否有任何減少到SIVPCSIVPCtextrm{SIVP}_gamma

短整數解（SIS）通過減少被證明是困難的 $ \textrm{SIVP}\gamma $ 到SIS，即如果我們解決SIS，那麼我們可以解決 $ \textrm{SIVP}\gamma $ .

有什麼辦法可以將 SIS 的實例減少為 $ \textrm{SIVP}_\gamma $ ?

如果 $ A\in\mathbb{Z}_p^{n \times m} $ ，那麼你可以定義

$$ \mathcal{L}={y\in\mathbb{Z}^m~:~Ay=0,\bmod,p}. $$ $ \mathcal{L} $ 是一個 $ m $ -維晶格，如果你解決（搜尋） $ SIVP_\gamma $ 在這個格子中，這意味著你找到了一個向量 $ v $ （實際上很多這樣的向量）使得 $ Av=0\bmod,p $ 和 $ ||v||\leq \gamma\cdot\lambda_m(\mathcal{L}). $ 這就是 SIS 的解決方案。什麼時候 $ m>n $ （說 $ m>2n $ ） 和 $ A $ 是均勻隨機的，您實際上可以緊密綁定該值 $ \lambda_m(\mathcal{L}) $ 在周圍（忽略一些常數）

$$ \lambda_m(\mathcal{L})\approx \sqrt{m}\cdot \det(\mathcal{L})^{1/m}=\sqrt{m}\cdot p^{n/m}. $$ 所以，簡而言之，如果你能解決 $ SIVP_\gamma $ 對於上述形式的隨機格，那麼你可以找到短向量 $ v $ 這樣 $ Av=0\bmod,p $ 和 $ ||v||<\gamma\cdot\sqrt{m}\cdot p^{n/m} $ .

引用自：https://crypto.stackexchange.com/questions/48065