密集球體填充和基於格的密碼學
眾所周知，格有兩種流行的應用：密集球體填充和基於格的密碼學。我在 Internet 上沒有找到任何有關這些域可能互動的資訊。讓我們暫時忘記大多數稠密晶格都是相當理論的結構，因此它們沒有快速的算法來處理它們。然而，在您看來，如果我們從計算的角度進行抽象，密集格在（數學）密碼學中是否有用？換句話說，與非密集點陣相比，密集點陣在加密上下文中是否提供任何優勢？
有幾位作者探索了用於密碼學的密集球體填充。他們分為（大致）兩個陣營
- 基於格同構問題的密碼系統的更有效實例化，以及
- 更高效（基於 LWE）的加密。
首先，請參閱this。潛在的硬度假設仍然相當小眾，但它似乎確實受益於具有密集球體填充的實例化。儘管如此，人們仍然不能簡單地訴諸密集的球體填料——論文中的結構需要這些球體填料具有其他一些額外的特性。
第二，確實有相當多的參考資料。有關簡短摘要，請參閱
還有更多論文，但這應該可以讓您了解文獻中已知的內容。在大多數情況下，有效的方案（例如 NIST-PQC 候選方案）傾向於忽略所有這些，原因有幾個。這是因為基於格的加密（大致）有兩種不同的設置
- KEMs：在這裡，您需要傳輸一個 $ \leq 256 $ 位鍵，並有 $ n\geq 512 $ 尺寸做它（並且正在傳輸 $ \approx n\log_2 q $ “數據”位）。結果，即使是相對較差的球體封裝也足以以較小的密文傳輸（相對）少量的數據。在非常特定的情況下可能會有一些好處，但它似乎不是通用的。我認為如何使用這些密碼系統有效地建構 IND-CCA2 KEM 也不太清楚（它們提供 IND-CPA KEM。您可以將它們轉換為 IND-CPA PKE，然後是 IND-CCA2 KEM，但這是間接的。那裡可能是已知的更智能的轉換）。還有一些奇怪的專利問題 — 參見NewHope，它使用了半緻密球填料 $ D_4^{n/4} $ 以一種關鍵的方式，以及沒有 Reconciliation 的 NewHope，它刪除了該計劃的這一部分。
- FHE：對於許多 FHE 方案，僅將您的消息編碼為良好的球體包裝是不夠的。相反（至少對於 GSW 類型的乘法），該消息還需要是一個“ gadget ”。完全不清楚是否可以利用密集的球體填充來建構密集的小工具（或者，類似於 LIP，球體填充需要具有一些單獨的屬性）。
這就是說
- 從格同構問題建構的密碼系統中似乎有密集球體堆積的應用，並且
- FHE 中似乎有密集球體填料的應用
但是在這兩種設置中，您確實希望從球體包裝中獲得更多，而不僅僅是密度。有一些警告，但對於第一個近似值，以上都是正確的。
單獨的一點是，密碼學家通常假設潛在的 LWE 雜訊在 $ \ell_\infty $ -規範，即他們想要密集 $ \ell_\infty $ -規範包裝，而不是密集 $ \ell_2 $ - 標準包裝。找到這些相對簡單——由定義的晶格堆積 $ \mathbb{Z}^n $ 是“完美”的 $ \ell_\infty $ -規範（意思是 $ \mathbb{Z}^n + [-1/2, 1/2)^n = \mathbb{R}^n $ 是一個分區，立方體包裝中沒有“浪費空間”）。（縮放）這個“密集 $ \ell_\infty $ lattice”在基於格的密碼學中一直使用，因此人們還可以回答您的問題，因為“人們確實使用它們，只是在 $ \ell_\infty $ -規範而不是 $ \ell_2 $ -規範”。
再次單獨地，密碼學中密集格的一個動機可以在密碼學家撰寫的論文的預備部分中找到，該論文給出了密集格的快速解碼算法。如果有明顯的加密應用程序，人們會期望在此處對其進行描述（按照慣例）。這些論文往往不描述（加密）應用程序。參見例如
- Peikert 的論文列出了解碼 Barnes Sloane 晶格或Barnes Wall 晶格，
- Miccincio 的巴恩斯壁格有界距離解碼器，
- Ducas 解決CVP問題的論文 $ A_p\otimes A_q $ （及其對偶），並給出允許有效 BDD 算法的準最優密度格。
這三個人都是著名的基於格的密碼學家。我不相信任何論文都在談論加密應用程序，儘管我相信上面的 Wyner-Ziv 論文確實使用了 Miccincio Nicolosi BDD 算法（此處可能已經改進）。這就是說有一些小的應用程序，但沒有任何東西可以使它成為標準化的 KEM（它統一使用 $ \mathbb{Z}^n $ , 而不是稠密的 $ \ell_2 $ -範數格子）。