使用 Babai 的 Naive Rounding 算法進行解碼，在 SIS 問題的條件下，是否安全？
給定 SIS 問題：給定一個整數 q，一個矩陣 $ A \in \mathbb{Z}_q^ {n \times m} $ 均勻隨機，真實 $ \beta $ , 一種綜合症 $ u \in \mathbb{Z}q^n $ , 找到一個非零整數 $ e \in \mathbb{Z}^m $ 這樣 $ Ae=u \mod q $ 和 $ || e||{2} \leq \beta $ .
採樣制服 $ A \in \mathbb{Z}_q^ {n \times m} $ ，以及相對較短的全秩“陷門”向量集 $ S \in \Lambda^{\perp}(A) $ 如 1999 年 Ajtai 的論文（生成短基問題的硬實例）。選擇 $ t \in \mathbb{Z}^m $ 通過線性代數使得 $ At=u \mod q $ 並使用 Babai 樸素舍入算法與基礎 $ S $ 解碼 $ -t \in \mathbb{Z}^m $ 到一個點 $ v \in \Lambda^{\perp}(A) $ 產生SIS問題的解決方案 $ e=t+v $ . 因此很難獲得 $ e $ 正確的？
但另一方面，GGH 方案的 Nguyen 和 Regev 的攻擊（學習平行六面體：GGH 和 NTRU 簽名的密碼分析）在這種情況下不起作用嗎？這是否與 SIS 硬度相矛盾？我哪裡錯了！
對 GGH 和 NTRU 的 Nguyen-Regev 攻擊奏效了，因為這些計劃在簽名時“洩露”了活板門 S。所以在觀察到一定數量的簽名後，他們的算法可以恢復 S。所以他們的攻擊與解決 SIS 無關，而是與如何使用洩露的資訊來恢復一個陷門（然後可以用來解決 SIS）。在正常 SIS 問題中，S 對對手來說是未知的，當然也沒有來自任何地方的“洩漏”。