在過去的文章對後量子密碼學作出一系列的講解，相信有不少人會也留意到當中的理論/情況及其應用都有不少問題或難題。在這一篇中，就挑出一小部分的問題作出講解，希望大家可以有更深入的了解。

27 基礎理論
帶誤差或捨入的學習。對於誤差率為 α<1 的高斯誤差和任何模數

的 LWE問題，在量子計算下至少與

 和 

問題一樣困難，其中 

[Reg05]。相比之下，已知的經典歸約[Pei09] 僅對 GapSVP 有效，對 SIVP 無效，並且需要指數級大的模數 qq（或者一個不減少樣本位元長度的維度-模數權衡[BLP+13]）。這種情況留下了以下重要問題。

問題 27.1. 是否存在一個經典的最壞情況硬度歸約適用於 LWE，能完全涵蓋已知的量子歸約？
對於適當的參數，帶捨入學習問題至少與 LWE 一樣困難。然而，已知的歸約[BPR12, AKPW13] 要麼涉及 LWE 的超多項式模數 q 和反誤差率 1/α（對應於格問題的超多項式近似因子），要麼涉及 LWR 樣本數量的先驗限制（這會影響底層的 LWE 參數）。然而，LWR 在更激進的參數下（例如，足夠大且整數的 q/p=poly(n)）似乎也是困難的。對於所有基於 LWE 的偽隨機函數構造[BPR12, BLMR13, BP14]，情況也是類似的。

問題 27.2. LWR，以及更廣泛地說，現有基於 LWE 的 PRF 構造，是否在多項式有界的 q 和無限數量樣本的情況下具有最壞情況硬度？
理想格與環-LWE。現在轉向基於環的密碼學，對於安全性而言，最重要的問題可能是環上理想和模的額外代數結構，是否會為相關格問題帶來任何新型攻擊的突破口。特別是對於環-SIS/LWE 密碼學，一個核心問題是：

問題 27.3. 對於理想格上的最壞情況問題，特別是在分圓環中，是否存在（可能是量子的）演算法，其效能顯著優於已知的適用於一般格的演算法？如果是，這些攻擊是否也能延伸應用於對抗環-SIS 和環-LWE 問題本身？
對於環-LWE，目前沒有已知的、能與經典 LWE 硬度歸約 [Pei09] 相媲美的有意義的類比結果，這是因為對於相關的多項式近似因子，理想格上的 GapSVP 是容易的。這引出了下面這個非常重要的問題。

問題 27.4. 是否存在針對環-LWE 的有意義的經典最壞情況硬度歸約？
雖然針對環-LWE搜索版本的已知最壞情況歸約適用於任意代數數域（參見 [LPR10, Theorem 4.1]），但 [LPR10, Section 5] 中的搜索-判定等價性核心依賴於分圓數域 - - 具體來說，是依賴於它們是伽羅瓦域（擁有許多自同構）這一事實，而這是一個相當稀有的性質。

問題 27.5. 在沒有許多自同構的數域中，是否存在環-LWE 的搜索到判定歸約，或者其他針對判定性環-LWE 的硬度歸約？
已知的針對環-LWE 搜索版本的最壞情況硬度歸約涉及一系列橢圓形誤差分佈。因此，（針對分圓環的）搜索-判定歸約涉及一個判定問題，其中誤差分佈要麼具有 n 個隨機且秘密的參數，要麼是一個球面分佈，其參數取決於區分者可用的樣本數量（參見 [LPR10, Theorems 5.1 and 5.2]）。更理想的情況是證明搜索問題對於固定的球面誤差分佈是困難的，因為除了其簡單性之外，對於球面誤差，搜索和判定問題是等價的，且誤差寬度不會惡化（參見 [LPR10, Theorem 5.3]）。

問題 27.6. 是否存在針對環-LWE（搜索或判定均可）的最壞情況硬度歸約，該歸約使用窄的球面誤差分佈，且誤差量不需要隨樣本數量增長？
（我們提到，標準的「噪聲泛洪」技術可以證明具有超多項式寬度的球面誤差的硬度，但使用這種技術會在效率和最壞情況近似因子方面付出不令人滿意的代價。）
已知的來自 [LPR10, Section 5] 的環-LWE 搜索-判定歸約，將一個能以不可忽略優勢解決判定問題的區分器，轉換成一個能以高機率解決搜索問題的演算法，但使用的樣本數量遠多於區分器所需。就最壞情況硬度而言，這種增加不是問題，但對於將環-LWE 的偽隨機性與其作為密碼學函數的單向性聯繫起來來說，這是不理想的。對於普通 LWE，Micciancio 和 Mol [MM11] 的工作（基於 [IN96] 關於子集和函數的工作）給出了一個樣本保持的搜索-判定歸約，其中搜索問題的解決器使用與區分器相同數量的樣本（並且成功機率與區分器的優勢多項式相關）。

問題 27.7. 對於環-LWE，是否存在樣本保持的搜索-判定等價性？
NTRU。Stehlé 和 Steinfeld [SS11] 提出了一種 NTRU 密碼系統的變體，其中公鑰 

在統計上接近均勻隨機（由於 f,g 的尺寸相對較大），並在環-LWE 假設下證明其具有被動安全性。然而，典型的 NTRU 定義使得公鑰在統計上遠非均勻，但被猜想是偽隨機的 - 然而我們目前幾乎沒有支持這一猜想的理論證據。事實上，我們甚至不知道針對 NTRU 相關問題的搜索-判定等價性。

參考資料
[Reg05] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):1–40, 2009. Preliminary version in STOC 2005.

[Pei09] C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In STOC, pages 333–342. 2009.

[BLP+13] Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehle. Classical hardness of learning with errors. In STOC, pages 575–584. 2013.

[BPR12] A. Banerjee, C. Peikert, and A. Rosen. Pseudorandom functions and lattices. In EUROCRYPT, pages 719–737. 2012.

[AKPW13] J. Alwen, S. Krenn, K. Pietrzak, and D. Wichs. Learning with rounding, revisited - new reduction, properties and applications. In CRYPTO, pages 57–74. 2013.

[BLMR13] D. Boneh, K. Lewi, H. W. Montgomery, and A. Raghunathan. Key homomorphic PRFs and
their applications. In CRYPTO, pages 410–428. 2013.

[BP14] A. Banerjee and C. Peikert. New and improved key-homomorphic pseudorandom functions. In CRYPTO, pages 353–370. 2014.

[LPR10] V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. Journal of the ACM, 60(6):43:1–43:35, November 2013. Preliminary version in Eurocrypt 2010.

[MM11] D. Micciancio and P. Mol. Pseudorandom knapsacks and the sample complexity of LWE
search-to-decision reductions. In CRYPTO, pages 465–484. 2011.

[IN96] R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology, 9(4):199–216, 1996.

[SS11] D. Stehle and R. Steinfeld. Making NTRU as secure as worst-case problems over ideal lattices. In EUROCRYPT, pages 27–47. 2011.