Lattice-Crypto
q-ary 晶格的 q 約束？
在格密碼學中，人們經常使用 q-ary 格，以便我們可以使用短整數解 (SIS) 的硬度和錯誤學習 (LWE)。我在一些筆記中看到有時我們想要 $ q $ 成為主要力量或主要力量。然而，沒有任何解釋為什麼會這樣。所以我有幾個關於選擇的問題 $ q $ :
- 將 q 設為任何正整數有什麼問題嗎？或者是否有任何價值被證明是有問題的？
- 選擇它作為素數或素數有什麼好處？有沒有更適合的素數？
正如 Hilder 提到的，通過“模數切換”技術，特定的選擇 $ q $ LWE 的安全性無關緊要。因此，特定的形式 $ q $ 主要是為了提高效率。我不是詳盡列出所有這些的錯誤的人，但是通過閱讀 NIST PQC KEM 提案可以很容易地指出其中的一些。
例如：
- 選擇 $ q = 2^k $ 對於一些 $ k $ 允許一個替換模組化減少 $ q $ 移位，更便宜的操作。這也是Saber選擇的部分原因 $ q = 2^{13} $ .
- 選擇 $ q $ 成為“NTT友好”。NTT是FFT“mod的某種類似物 $ q $ “（而不是結束 $ \mathbb{C} $ ），可以在多項式乘法中實現大幅加速（大致從 $ O(n^2) $ 天真的複雜性 $ O(n\log n) $ ）。加速的大小與是否有合適的類似物直接相關 $ i\in\mathbb{C} $ . 最好的情況（比如在加班時 $ \mathbb{Z}_q /(x^n+1) $ 為了 $ n = 2^k $ ) 當你有一個“原始 $ 2n $ 統一的根”，這發生在 $ q\equiv 1\bmod 2n $ （我認為）。請注意，這與先前的優化不兼容。KEM Kyber 做出了這個選擇（幾乎存在小的技術差異）。
- 選擇 $ q $ 是小（字長）互質數的乘積，因此可以訴諸中國剩餘定理，並保持所有算術字長。我不知道有這樣做的 KEM，但這在 FHE 文獻中很流行（通常稱為“殘基數係統”或 RNS 算術）。
所以有選擇的論據 $ q \equiv 0 \bmod 2^k $ , $ q\equiv 1\bmod 2\times 2^k $ ， 和 $ q $ 小互質數的乘積。這些似乎都是相互排斥的優化，但其中一個可能有點聰明，一次使用多個優化。例如，有這項關於嵌入算術 mod的工作 $ 2^k $ （即“模組化減少友好”）到 NTT 友好環中，讓一個人同時使用優化 1 和 2。