從基於格的原像採樣中恢復陷門
$$ GPV $$和$$ MP $$（下面的參考資料）給出了由定義的陷門函式的構造 $$ f_{\mathbf A} (\mathbf x) = \mathbf A \mathbf x, $$ 在哪裡 $ \mathbf A \in \mathbb Z_q^{n \times m} $ 是均勻隨機的，域是 $ { \mathbf x \in \mathbb Z^m \mid \lVert x \rVert \le \beta} $ . 鑑於任何 $ \mathbf y \in \mathbb Z_q^n $ ，秘密陷門允許計算原像 $ \mathbf x $ 的 $ \mathbf y $ ， IE $ \mathbf A \mathbf x = \mathbf y $ 和 $ \lVert \mathbf x \rVert \le \beta $ . 活板門在
$$ GPV $$是滿秩集 $ \mathbf S \in \mathbb Z^{m \times m} $ 這樣 $ \mathbf A \mathbf S = 0 $ . 活板門在$$ MP $$是 $ \mathbf R $ 這樣 $ \mathbf A \begin{bmatrix} \mathbf R \ \mathbf I \end{bmatrix} = \mathbf G $ ， 在哪裡 $ \mathbf G $ 是一些特殊的公共小工具矩陣。在任何情況下，每個活板門都有一些相關的數量 $ s $ 描述了它的質量。為了 $ \mathbf S $ , $ s = $ Gram-Schmidt 列的最大範數 $ \tilde{\mathbf S} $ 的 $ \mathbf S $ . 為了 $ \mathbf R $ , $ s = $ 的最大奇異值 $ \mathbf R $ . 鑑於任何 $ \mathbf y $ , 質量活板門 $ s $ 允許從離散高斯分佈中採樣 $ {\mathbf{x} \mid \mathbf A\mathbf x = \mathbf y} $ 寬度 $ \sigma \ge s\cdot\omega(\sqrt{\log m}) $ ， 這使 $ \lVert x \rVert \le \sigma\sqrt m $ （以壓倒性的機率）。
我的問題是關於相反的。假設我們有一個用於高斯原像採樣的預言機，它輸出解決方案 $ \mathbf A \mathbf x = \mathbf y $ 和 $ \lVert x \rVert \le \beta $ 為任意選擇 $ \mathbf y $ . 我們可以恢復某種活板門嗎？ $ \mathbf A $ 讓我們計算原像 $ \mathbf x’ $ 一個隨機的 $ \mathbf y’ $ 那不是以不可忽略的機率向預言機查詢的嗎？
一種明顯的嘗試是查詢 $ \mathbf A \mathbf x = \mathbf 0 $ 嘗試恢復“短”全等級集 $ \mathbf S $ 這樣 $ \mathbf A \mathbf S = \mathbf 0 $ . 但是這個 $ \mathbf S $ 似乎不夠短，無法計算長度的解 $ \le \beta $ . 我們可以嘗試晶格縮減。但我不知道最先進的晶格縮減是什麼，試圖從已經很短的基礎中獲得更短的基礎。
- $$ GPV $$ https://eprint.iacr.org/2007/432
- $$ MP $$ https://eprint.iacr.org/2011/501
您描述的想法（幾乎）有效，但正如您所注意到的，由此產生的陷門的“質量”比我們似乎需要生成規範的原像要差一些 $ \leq \beta $ . 但是，質量足以生成規範的原像，例如， $ \leq \beta \sqrt{m} $ . 如果參數設置正確，這對於應用程序來說就足夠了。
例如，這個想法被正式製定並用於 CHKP'10 “盆景樹”論文中的“委託”活板門，以及
$$ MP $$因為它的活板門風格。 不知道您所詢問的是否可以在不損失質量的情況下完成，但如果是這樣，那將是非常令人驚訝的；我認為大多數專家都不認為這是可能的。
為了使格子減少為所述目的起作用，人們希望減少給定的範數向量 $ < \beta $ 成範數向量 $ < \beta/ \sqrt{m} $ 或者。這似乎是一個非常困難的問題。事實上，即使只是將某些給定向量的長度減半似乎也很困難，因為直覺的原因是我們可以一次又一次地減半，直到程序停止工作，給我們一個近乎最短的晶格向量。事實上，這就是一些（指數時間）最短向量算法的工作原理，通過迭代減半。