格子活板門
我參考了一篇文章https://eprint.iacr.org/2011/501。我專注於（稍加修改）算法 1，其執行如下（在我的理解中）：對於給定 $ n, m\in \mathbb N $ , $ q=2^k $ 和分佈 $ \mathcal D $ , 算法選擇一個均勻隨機矩陣 $ \overline {\mathbf A}\in \mathbb Z_q^{n\times m-nk} $ 和一個矩陣 $ \mathbf R \in \mathbb Z_q^{m-nk \times nk } $ 來自 $ \mathcal D $ 並輸出一個矩陣 $ \mathbf A=[\overline {\mathbf A}| \mathbf G - \overline {\mathbf A}\mathbf R] \in \mathbb Z_q^{n\times m} $ 和一個活板門 $ \mathbf R \in \mathbb Z^{m-nk\times nk} $ .
如果 $ \mathbf G $ 是公開的並且 $ \overline {\mathbf A} $ 可以從 $ \mathbf A $ 自從 $ \mathbf A = [\overline {\mathbf A} | \mathbf A_1] $ ，為什麼得不到 $ \mathbf R $ ? 這很重要，因為 $ \mathbf R $ 包含有關簡短基礎的所有資訊 $ \mathbf A $ ，通常被視為私鑰，而 $ \mathbf A $ 是公鑰。
在計算上是不可行的 $ R $ （或任何其他滿足關係的短矩陣）因為求解 $ A R = V \pmod{q} $ 對於均勻隨機 $ A, V $ 是 SIS 問題（在其非均勻版本中）。可以證明 SIS 與解決格上的最壞情況逼近問題一樣難。
（另外，對於論文中考慮的參數， $ [\bar{A} \mid -\bar{A}R] $ 非常接近制服，所以找到一個有效的活板門給定 $ A $ 真的等價於SIS問題。）