即使給定 oracle 訪問來計算陷門函式的逆，I 型格陷門是否也很難找到？
考慮 I 型格子活板門
$$ GPV08 $$: https://eprint.iacr.org/2007/432.pdf
假設一個 PPT 對手被賦予了圖中的 LWE 陷門函式：
$ g_{A^\top} (s,e) = A^\top s + e = b (\text{mod } q) $
令 T 為 A 的類型 1 活板門。
現在給 PPT 對手一個預言機，它執行以下操作：在輸入 b’ 上，預言機用一對滿足的 (s’,e’) 回答 $ A^\top s’ + e’ = b’ (\text{mod } q) $ .
PPT 對手能否通過多次查詢該預言機的多項式來找到陷門 T？
圖片來自講義：https ://fangsong.info/teaching/s16_uw_pqc/qic891_pqc_lec3.pdf
如果對手是經典算法，那麼您的問題的答案是未知的。但是，如果對手是一個可以疊加查詢預言機的量子算法，那麼答案是肯定的：通過對某些（有效可生產的）量子狀態向預言機進行查詢，它可以恢復一個 Type-I 陷門 $ A $ .
對於經典算法，困難在於我們不知道如何生成有效的輸出 $ g $ （甲骨文有義務成功）除非通過選擇 $ s,e $ 我們自己和餵養他們 $ g $ . 但是預言機的答案對我們來說毫無用處，因為我們在查詢之前就已經知道答案了。
對於量子算法，情況就不同了。我們可以對“所有”有效的進行某種疊加 $ s,e $ , 餵牠通過 $ g $ 獲得輸出的疊加，並呼叫預言機返回 $ s,e $ . 至關重要的是，這使我們能夠取消計算（或“忘記”）我們最初的選擇，從而為我們留下有用的量子態。具體來說，通過其量子傅里葉變換，我們得到了短向量的疊加 $ x $ 這樣 $ Ax=0 $ . 通過測量狀態，我們得到這樣一個 $ x $ ，並且可以重複累積許多線性獨立的，產生一個 Type-1 活板門。
經典環境中的困難，以及處理它的量子策略，來自 Regev 關於 LWE 的原始論文。GPV 論文首先描述了與 SIS/LWE 的連接。