經典安全和量子安全之間是否存在後量子密碼系統？
針對一些後量子安全假設，經典攻擊和量子攻擊之間是否存在差距？（我對非對稱密碼學特別感興趣。）
我知道沒有針對這些問題的多項式時間算法（否則它將不再被視為 PQ 安全假設）。但有時我們知道的量子攻擊是否比經典攻擊更有效（即使它仍然是指數級的）？
這是一個範例，其中最著名的量子攻擊在某種意義上只是在最著名的經典攻擊與另一側的完全中斷之間的“中間”：反轉密碼組操作，例如CSIDH。
讓 $ G $ 是一個（有限）交換群 $ G $ 作用於一組 $ X $ , 即我們考慮一張地圖 $$ \ast\colon; G\times X\to X $$ 與集團結構相適應 $ G $ 在某種意義上說 $ 1\ast x=x $ 和 $ (g\cdot h)\ast x=g\ast(h\ast x) $ .
要解決的問題類似於離散對數問題：
給定兩個元素 $ x,y\in X $ ， 尋找 $ g\in G $ 和 $ g\ast x=y $ ，假設它存在。
經典地，最著名的攻擊是中間相遇的方法，即嬰兒步巨人步，其中組 $ G $ 被分成兩個子集 $ U,V\subseteq G $ 這樣 $ G=U\cdot V $ , 並且尋找兩組之間的碰撞 $ U\ast x $ 和 $ V^{-1}\ast y $ . 確實，當 $ u\ast x=v^{-1}\ast y $ ， 然後 $ (u\cdot v)\ast x=y $ . 這需要時間和空間 $ O(!\sqrt{\lvert G\rvert}) $ ，這是指數的 $ \log{\lvert G\rvert} $ .
（實際上，有比這種簡單化的方法更好的時空權衡。）
然而，在量子上，這個問題可以使用 Kuperberg 算法 [ 1 , 2 []](//arxiv.org/abs/1112.3333)來解決阿貝爾隱藏移位問題，這在組大小中需要次指數（但超多項式）時間。更具體地說，漸近成本是 $$ {\exp}\Big(!\sqrt{\log{\lvert G\rvert}}+o(1)\Big) \text, $$ 大致可以概括為“在指數中取平方根”。
（為了比較，整數分解的數字域篩也是次指數的，但有一個立方根。）