用於 McEliece 密碼系統的程式碼

在McEliece 密碼系統中，攻擊者是否知道程式碼的選擇？如果結構性攻擊成功並且攻擊者找到了程式碼的生成矩陣，那麼攻擊者是如何解碼加密消息的呢？

“種子”程式碼是已知的（通過 $ G $ ) 包括攻擊者在內的所有人，但實際使用的程式碼是未知的。種子程式碼座標在右側排列（ $ P $ ) 可逆變換後 $ S $ 應用於左側，形成活板門。 $ S,P $ 是秘密的。如果置換生成矩陣是 $ \hat{G} $ 我們有 $$ \hat{G}=SGP. $$

如果攻擊者找到（未置換的）生成矩陣，那麼他們可以按照下一段中的說明進行解碼。

如果接收到的密文是 $ c=c’\oplus e, $ 在哪裡 $ e $ 是為安全添加的雜訊向量，並且 $ c’=m\hat{G}, $ 合法的收件人可以做 $$ \hat{c}=cP^{-1}, $$ 並且可以解碼 $ \hat{c} $ 至 $ \hat{m} $ 使用程式碼的標準解碼算法。她終於可以計算 $$ m=\hat{m}S^{-1}. $$ 您可以按照正常方式進行檢查。

**編輯：**為了闡明安全性的來源，通過排列和矩陣乘法的遮罩產生了一個等效的“偽隨機”程式碼，其屬性與原始程式碼相似。

所以等價的解碼問題看起來像*一個隨機碼的解碼問題，*而且由於隨機碼的解碼很困難，強度在於乘法和排列，它們是只有授權解碼器才能使用的陷門資訊。

請注意，添加的雜訊不得超出程式碼的校正能力。如果是這樣，即使使用陷門資訊，合法接收器也可能解碼為錯誤的程式碼字，或者無法解碼為正確的程式碼字。

這是一個（一般的、數學的）視角，可能並不對所有讀者都有用，但我仍然覺得特別好。它通過與格同構問題的類比來實現。這是一個相對較新的硬度假設（見這裡，雖然我知道還有其他兩部作品在處理它），在某種意義上它是“程式碼到格子”中的“McEliece 假設的概括”。我將首先描述第二部分，然後再描述它如何給出一個很好的數學表徵，即矩陣的精確度 $ G $ （和 $ \hat{G} $ ） 是。

首先，簡要討論符號。線性碼是一個子集 $ C\subseteq\mathbb{F}_2^n $ （或一個子集 $ \mathbb{F}_p^n $ 更普遍）。一種是根據漢明度量來測量線性碼的大小。一個類似的概念是格子的概念，它是 $ \mathbb{R}^n $ ，其中一個根據歐幾里得度量來測量晶格中的大小。注意格子 $ L $ 密碼學中使用的通常被認為是 $ q $ -ary 表示一些常數（不一定是素數） $ q $ . 這意味著 $ q\mathbb{Z}^n\subseteq L $ . 另外當 $ L\subseteq\mathbb{Z}^n $ , 可以在格子之間畫一個強連接 $ L $ , 和 $ q $ -ary碼 $ L\cap [0,q)^n $ . 這種連接的一側稱為構造 A。這需要一個 $ q $ -ary碼 $ C\subseteq\mathbb{Z}_q^n $ ，並建構晶格 $ C + q\mathbb{Z}^n $ .

無論如何，McEliece 假設已經根據晶格同構問題推廣到晶格。這個問題（大致）如下。給定一個格子 $ L $ ，人們經常想通過乘以一個基來明確表示它 $ B $ ，即寫任意格點 $ l =Bx $ 為了 $ x\in\mathbb{Z}^n $ . 有兩種明顯的方式表明這是非唯一的，即

1. 給定一個自同構 $ \mathbb{Z}^n $ 我們稱之為 $ U $ （通常稱為unimodular，或 $ \mathsf{SL}_n(\mathbb{Z}) $ . 可以等效地將其視為“基礎更改”），可以替換 $ x\mapsto Ux $ ，即晶格在自然作用下是不變的 $ \mathsf{SL}_n(\mathbb{Z}) $ 在右邊，和
2. 給定一個正交變換 $ O $ （可以將其視為廣義旋轉），晶格不會通過向左旋轉而從根本上改變，即 $ OB\mathbb{Z}^n\approx B\mathbb{Z}^n $ 本質上是一樣的。

這就是說，給定一個依據 $ B\in\mathsf{Mat}_{n\times n}(\mathbb{R}) $ ，它與一個格子相關聯 $ L\in\mathcal{L}_n $ , 的空間 $ n $ 維晶格。以上兩點可以用來論證 $ \mathcal{L}n = O(n) \backslash \mathsf{Mat}{n\times n}(\mathbb{R})/ \mathsf{SL}_n(\mathbb{Z}) $ . 這是一個“雙陪集空間”，並且（簡而言之）意味著改變 $ B\mapsto BU $ 不會從根本上改變事物，以及 $ B\mapsto OB $ 不會從根本上改變事情。

這對程式碼意味著什麼？好吧，人們可以對程式碼重複完全相同的論點。一個得到那個

1. 右邊的動作還在 $ \mathsf{SL}_n(\mathbb{Z}) $ ， 但
2. 左邊的動作應該是 $ S_n $ . 這是（大致）因為保留規範的矩陣組 $ \lVert\cdot\rVert_0 $ 是簡單的排列，而保留範數的矩陣組 $ \lVert\cdot\rVert_2 $ 大得多（它是 $ O(n) $ ，通常稱為“正交群”）。

這導致程式碼被描述為某個矩陣 $ G $ , 最多乘以一個單模矩陣 $ S $ 在右邊，和排列矩陣 $ P $ 在左邊，即 $ \hat{G} = PGS $ 將“相同的程式碼”定義為 $ G $ （請注意，我使用程式碼下編碼的約定是 $ x\mapsto Gx $ . 如果一個人更喜歡另一種表示法 $ \mapsto xG^t $ ，你在上面的討論中交換了“左”和“右”）。

在此背景下，McEliece 密碼系統公開了一個（適當地隨機的）代表程式碼的等價類 $ G $ 屬於。它通過乘以隨機選擇來做到這一點 $ P $ 和 $ S $ 如上。但從根本上說， $ \hat{G} $ 和 $ G $ 是“相同的程式碼”，我們說“相同”取決於

1. 潛在的基礎變化 $ S $ ， 和
2. 潛在的“旋轉”（在漢明範數中） $ P $ .

引用自：https://crypto.stackexchange.com/questions/81954