什麼是密碼學中的“格”？
這裡有一些關於基於格的密碼學的問題，如果假設存在量子電腦，這種密碼學似乎特別有用。
閱讀此類問題時，我總是問自己：“什麼是格子？”
現在我在這裡問：
- 晶格是如何定義的？
- 對晶格/使用晶格執行的最常見操作是什麼？（如在 ECC 中加倍和添加）
如果您需要對可用知識的假設：
關於大多數非抗量子密碼學的紮實知識，就像在 HAC 中教授的那樣。
晶格是如何定義的？
一個格子 $ \mathcal L(B) $ 是基的所有整數組合的集合 $ B = {b_1, …, b_n} $ 的 $ n $ 線性獨立向量。也就是格子 $ \mathcal L(B) $ 定義為：
$$ \begin{equation} \mathcal L(B) = { B \cdot z ;: ; z \in \mathbb Z^n} \end{equation} $$ 在密碼學中，我們對整數格感興趣，即那些 $ B \in \mathbb Z^{n\times n} $ , 並且, 特別是, 在 $ q $ -ary lattices，它是整數格的模組化版本。
對晶格/使用晶格執行的最常見操作是什麼？（如在 ECC 中加倍和添加）
如您所見，晶格中的元素只是定義矩陣的空間中的向量。在整數格的情況下，空間是 $ \mathbb Z^{n\times n} $ ，所以晶格的元素只是整數向量。出於這個原因，基於格的方案通常使用向量和矩陣進行操作，因此基本操作通常是：向量/矩陣加法、內積等。
為了便於說明，以下是 Miccincio 和 Peikert 的 CCA1-secure 密碼系統的加密功能的主要步驟
$$ 1 $$: $$ \begin{equation} b^t = 2(s^t A_u \mod q) + e^t + (0, \operatorname{encode}(m))^t \mod 2q \end{equation} $$ 在哪裡 $ b $ 是密文， $ s $ 和 $ e $ 是隨機向量和 $ A_u $ 是公鑰（或更準確地說，是從公鑰派生的）。從執行的實際操作的角度來看，您可以看到一切都非常簡單： $ b, s $ ， 和 $ e $ 是向量，並且 $ A_u $ 是一個矩陣，執行的操作是加法和乘法。這裡唯一的“特殊”部分是將消息從位串編碼為格點。
$$ 1 $$Miccincio, D. 和 Peikert, C. (2012)。格子活板門：更簡單、更緊密、更快、更小。在密碼學進展中——EUROCRYPT 2012（第 700-718 頁）。施普林格柏林海德堡 ( PDF )。