LWE 與身份子矩陣並重用從米磷12MP12MP12: 為什麼安全？
不久前我研究了這篇論文，但現在我對Miccincio 和 Peikert的論文Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller感到困惑。第 24 頁和第 25 頁，他們提出了一種算法，該算法解釋瞭如何對偽隨機矩陣進行採樣 $ \mathbf{A} $ 帶活板門。
本節的簡短介紹
基本上，這個想法是先採樣一個矩陣 $ \mathbf{A} $ 均勻隨機，對矩陣進行採樣 $ \mathbf{R} $ 根據一些分佈 $ \mathcal{D} $ ，然後計算 $ \mathbf{A} = [\bar{\mathbf{A}} | \mathbf{G} - \bar{\mathbf{A}}\mathbf{R}] $ 在哪裡 $ \mathbf{G} $ 是一個固定矩陣，即使在存在雜訊的情況下也很容易反轉（而且我不需要標籤 $ \mathbf{H} $ ， 所以 $ \mathbf{H} = \mathbf{I} $ ）。他們，如果我理解正確的話，他們會說 $ \mathbf{A} $ 如果看起來很隨機 $ [\bar{\mathbf{A}} | \bar{\mathbf{A}}\mathbf{R}] $ 看起來很隨機，這是有道理的，尤其是當我們刪除標籤時。所以從那時起 $ \mathbf{G} $ 不再用於研究不可區分性。
然後，他們提出了兩種採樣方式 $ \mathbf{R} $ 並選擇尺寸 $ \mathbf{A} $ ，取決於您是否想要統計或計算上的不可區分性 $ \mathbf{A} $ . 但是，計算版本對我來說有點奇怪：而不是採樣 $ \bar{\mathbf{A}} $ 均勻隨機，他們似乎取而代之的是另一個矩陣 $ \hat{\mathbf{A}} \in \mathbb{Z}_q^{n \times n} $ 均勻隨機，並設置 $ \bar{\mathbf{A}} = [\mathbf{I} | \hat{\mathbf{A}}] $ . 他們還採樣 $ \mathbf{R} = \begin{bmatrix}\mathbf{R}_1\\mathbf{R}_2\end{bmatrix} $ 根據離散高斯。那麼這意味著 $ [\bar{\mathbf{A}} | \bar{\mathbf{A}}\mathbf{R}] = [\mathbf{I}|\hat{\mathbf{A}}|\hat{\mathbf{A}}\mathbf{R}_2+\mathbf{R}_1] $ . 他們說這個矩陣（直到恆等式）與隨機矩陣無法區分，因為它是正常形式的 LWE 的一個實例。
我的（也許是初級的？）問題
所以我有兩個問題：
- 首先，為什麼在最終矩陣中有一個矩陣恆等式不是問題 $ \mathbf{A} $ ? 我感覺它洩露了更多關於這個秘密的資訊 $ \mathbf{s} $ , 因為你學的基本 $ \mathbf{s}^t\mathbf{I}+\mathbf{e}^t = \mathbf{s}^t+\mathbf{e}^t $ 對於一些小錯誤 $ \mathbf{e} $ . 特別是，您將學習到最重要的位 $ \mathbf{s} $ 正確的？我看不出你怎麼能從中學到同樣的資訊 $ \mathbf{s}^t\mathbf{A}+\mathbf{e}^t $ 什麼時候 $ \mathbf{A} $ 真的是隨機的。我想你可以嘗試做一些列操作來恢復身份，但我希望這會顯著增加噪音。
- 其次，**為什麼 $ [\hat{\mathbf{A}}|\hat{\mathbf{A}}\mathbf{R}_2+\mathbf{R}_1] $ 甚至是偽隨機的？**我理解 LWE 正常形式的方式是允許您採樣 $ \mathbf{s} $ 直接來自一個小高斯，而不是像這裡幻燈片 10/15中所解釋的那樣隨機均勻。所以我同意 $ [\hat{\mathbf{A}}|\hat{\mathbf{A}}\mathbf{R}_2+\mathbf{R}_1] $ 是偽隨機的，如果 $ \mathbf{R} $ 是一個向量。然而， $ \mathbf{R} $ 是一個矩陣，所以這意味著每一行 $ \hat{\mathbf{A}} $ 將用於生成多個樣本（每列一個或 $ \mathbf{R} $ ）。所以它表明如果我們重用 LWE 也是安全的 $ \mathbf{a} $ 樣品多次……我是對的還是我錯過了什麼？如果是，我們是否知道當這些樣本多次重複使用時 LWE 是安全的？
謝謝！
編輯：回答馬克
感謝您的回答。非常感謝您
$$ PW07 $$參考：引理 6.2 正是我所需要的：它非常有幫助，完美地回答了我的第二個問題！(+1) 關於第一個問題，我確實嘗試閱讀了相關部分$$ MR09 $$（重要的部分在最後，有點在開頭）。但是，它對我來說仍然有點神秘。我想可能是因為我還不習慣矩陣和晶格之間的這種聯繫。我仍然不明白我是否可以使用 $ \mathbf{A} $ “as it”（由於我提到的“攻擊”而奇怪），或者我在使用它時需要特別小心，比如採樣 $ s $ 來自一個小的錯誤集（也很奇怪，更不用說在論文中：稍後 $ g_{\mathbf{A}} $ 被定義在所有 $ s $ )，或者如果我可以擺脫身份並使用其餘的身份（但我不確定是否適用）。
關於參考
$$ MR09 $$，例如，我不確定他們如何得出第 24 頁的表達式 $ P’ $ . 只是為了確保，當他們說“減少 E 模 HNF 的列”時，他們的意思是某種 LLL 減少？在那條線之後，其餘的都是非常具體的，有自己的奇怪結構，我不確定我能說什麼。我覺得這個 Hermitian 矩陣只是格子空間中 A 的一種方便、高效的表示，但是使用這個矩陣而不是 A 需要一些適應（也許，正如你所說，使用一個小的 $ s $ 而不是一個統一的元素，這可能是$$ MR09 $$紙，因為他們使用 $ a $ 之間均勻採樣 $ -r $ 和 $ r $ …而且我覺得他們還需要更新採樣方式 $ E $ ，通過先做這個減少）。所以如果我需要調整我的方法來使用 $ \mathbf{A} $ ，然後我很驚訝他們沒有在論文中提到它，只是定義 $ g_\mathbf{A} $ 對所有人 $ s $ . 任何澄清將不勝感激，非常感謝！
順便說一句，雖然 Hermite 指的是同一個人，但“Hermitian”對於矩陣的含義與“Hermite Normal Form”不同。HNF 本質上是“不能分割的行梯隊形式/高斯消除”。
HNF 優化：
首先，我們可以討論“減少列 $ E $ 以 HNF 為模”，這並不意味著執行 LLL 減少或其他東西。
$$ MR2009 $$在第 15 頁隱含地定義了這個符號：
在
$$ 47 $$建議選擇向量 $ v $ 這樣所有的座標 $ (r+v) $ 以沿 HNF 公共基對角線的相應元素為模減少 $ H $ . 向量 $ (r+v) $ 由這樣的過程產生的表示 $ r\mod H $ ，並且可以證明它使密碼分析變得最困難，因為 $ r\mod H $ 可以從形式的任何向量有效地計算 $ (r+v) $ 和 $ v\in \mathcal{L}(B) $ . 所以，任何攻擊 $ r\mod H $ 可以很容易地適應任何形式的向量 $ r+v $ 通過第一次計算 $ (r+v) \mod H=r\mod H $ . 請注意 $ r\mod H $ 可以直接計算 $ r $ 和 $ H $ （沒有顯式計算 $ v $ ) 通過迭代地減去列的倍數 $ H $ 從 $ r $ . 柱子 $ h_{i} $ 用於減少 $ i $ 第一個元素 $ r $ 模組 $ h_{i,i} $ .
這對於“減少格的模數意味著”是相當典型的。任何格子將空間劃分為由格點轉換（非唯一）“基本域”的並集。減少模格大致意味著（對於某些基本域）將空間中的一個點移動格點（保留基本域中的相對位置），直到到達與 0 關聯的基本域。如果您有 CVP 預言機，這些基本域是 Voronoi 單元，但是對於“更糟糕”的基本域有有效的算法（在第 25 頁描述了一個）
$$ MR2009 $$如果你感興趣）。 這就是說，“減少格子模數”通過格子向量移動，直到您靠近原點，同時保持您在某個平鋪空間內的相對位置。減少模式最好地證明了這一點 $ q $ , 它有一個自然的解釋 mod the lattice $ q\mathbb{Z}^n $ . 這裡的基本域是 $ [-q/2, q/2)^n $ （這是立方晶格的 Voronoi 單元 $ q\mathbb{Z}^n $ )，它會從空間中的某個任意點映射您 $ x = q\vec{y} + e $ ， 在哪裡 $ q\vec{y}\in q\mathbb{Z}^n, e \in[-q/2, q/2)^n $ 至 $ e\in [-q/2, q/2)^n $ ，其中“被保留的相對位置”是指 $ x $ 在基本域（ $ e $ ) 不變。請注意，對於空間中的任意點 $ x $ ， 這 ” $ e $ 部分”是唯一確定的（因為晶格將空間劃分為基本域的轉換），因此保留 $ e $ 部分是有意義的。
回到第 24 頁，從考慮公鑰開始：
$$ [\mathbf{A}, \mathbf{A}\mathbf{S} + \mathbf{E}] $$
HNF 優化背後的想法有兩個方面：
- 代替 $ \mathbf{A} $ 用“簡潔”的格子描述 $ \mathbf{S} $ 編碼下
- 減少 $ \mathbf{AS} + \mathbf{E} $ 修改晶格以強制 $ \mathbf{AS} + \mathbf{E} $ 被包含在一些“更小”的空間中，同時“保留 $ \mathbf{E} $ 部分”
兩者都以關鍵方式使用 HNF。考慮格子基的 HNF $ \Lambda_q(\mathbf{A}^t) $ 再次。這可以通過列減少晶格的生成集來計算 $ \Lambda_q(\mathbf{A}^t) = \mathcal{L}(\mathbf{A}) + q\mathbb{Z}^n $ ，由下式給出 $ [\mathbf{A}, q\mathbf{I}] $ . 在“標准假設”下 $ \mathbf{A} $ （在第 23 頁底部列出），這產生了以下形式的基礎：
$$ \mathbf{H} = \begin{pmatrix}\mathbf{I} & \mathbf{0}\ \mathbf{A}’ & q\mathbf{I}\end{pmatrix} $$
請注意，更改為此基礎不需要以某種方式修改我們的公鑰。如果 $ \mathbf{A} = \mathbf{H}\mathbf{U} $ 是我們對 HNF 的表達 $ \mathbf{H} $ 就初始基礎和單模矩陣而言，我們簡單地說：
$$ [\mathbf{H}\mathbf{U}, \mathbf{H}\mathbf{U}\mathbf{S} + \mathbf{E}] $$
但 $ \mathbf{H} $ 和 $ \mathbf{H}\mathbf{U} $ 都生成相同的格子，所以我們可以自由替換 $ \mathbf{H}\mathbf{U} $ 和 $ \mathbf{H} $ . 我接下來寫 $ \mathbf{P} = \mathbf{U}\mathbf{S} $ , 是均勻隨機的 iff $ \mathbf{S} $ 是 （ $ \mathbf{U} $ 是可逆的）。因此，我們認為公鑰的形式為：
$$ [\mathbf{H}, \mathbf{H}\mathbf{P} + \mathbf{E}] $$
現在檢查等式的第二部分：
$$ \mathbf{H}\mathbf{P} + \mathbf{E} = \begin{pmatrix} \mathbf{I} & \mathbf{0} \ \mathbf{A}’ & q\mathbf{I}\end{pmatrix}\begin{pmatrix}\mathbf{P}’’\\mathbf{P}’\end{pmatrix} + \begin{pmatrix}\mathbf{E}’’ \ \mathbf{E}’\end{pmatrix} $$
可以進行塊矩陣乘法得到兩個方程：
$$ \begin{pmatrix}\mathbf{P}’’ + \mathbf{E}’’ \ \mathbf{A}’\mathbf{P}’’ + q\mathbf{P}’ + \mathbf{E}’\end{pmatrix} $$
這裡的想法是減少對晶格的模數，以將最後一個方程的“頂部”部分歸零。如果你看的形式 $ \mathbf{H} $ , 這很容易在不知道的情況下完成 $ \mathbf{P}’’ $ 或者 $ \mathbf{E}’’ $ （相關部分 $ \mathbf{H} $ 包含一個單位矩陣，從中添加列直到它為零）。
正如我所提到的，這種技術改變了正在編碼的特定格點。作為 $ \mathbf{P}’’ + \mathbf{E}’’ = 0 $ ，當我們將其歸零時，我們將得到編碼點 $ \mathbf{P}’’ = -\mathbf{E}’’ $ 現在，產生方程：
$$ \begin{pmatrix}-\mathbf{E}’’ + \mathbf{E}’’ \ -\mathbf{A}’\mathbf{E}’’ + q\mathbf{P}’ + \mathbf{E}’\end{pmatrix} = \begin{pmatrix}\mathbf{0} \ -\mathbf{A}’\mathbf{E}’’ + q\mathbf{P}’ + \mathbf{E}’\end{pmatrix} $$ 經過考慮的 $ \bmod q $ ，這可以讓人們將公鑰寫為：
$$ \left[\begin{pmatrix}\mathbf{I} & \mathbf{0}\ \mathbf{A}’ & q\mathbf{I}\end{pmatrix}, \begin{pmatrix}\mathbf{0} \ -\mathbf{A}’\mathbf{E}’’ + \mathbf{E}’\end{pmatrix}\right] $$
這很容易壓縮成對 $ [\mathbf{A}’, -\mathbf{A}’\mathbf{E}’’ + \mathbf{E}’] $ ，這是獲得效率增益的地方。另請注意，如果可以破壞此 LWE 實例，他們也可以破壞 LWE。為了簡單起見，考慮搜尋 LWE — 在這裡打破它可以讓你恢復 $ \mathbf{E}’, \mathbf{E}’’ $ ，這是整個 $ \mathbf{E} $ 在最初的 LWE 實例中。從中你可以減少 $ [\mathbf{A}, \mathbf{AS} + \mathbf{E}]\mapsto [\mathbf{A}, \mathbf{AS}] $ ，這是微不足道的。該技術還可用於將具有均勻誤差的 LWE 減少為具有高斯誤差的 LWE。我認為如果一個人真的想要統一的錯誤，你可以通過添加重新隨機化它 $ -\mathbf{A}’\mathbf{U}’ $ 制服 $ \mathbf{U}’ $ ，但沒有考慮這麼多（高斯誤差平均也會“更短”，因此在採樣離散高斯時出現問題，它們通常會導致誤差增長較慢）。
重用隨機矩陣：
您可以重複使用隨機墊。重用它 $ \ell $ 次大致給對手一個 $ \ell $ 通過簡單的混合參數獲得更大的優勢。因此，如果 $ \ell $ 是多項式大小的（對於誠實的各方來說，這是最大的可以計算的）一切都很好。詳細資訊可在PW2007的第 6.2 節中找到。這就是連結幻燈片的第 8 張幻燈片中提到的“多個秘密”（如果您將多個秘密收集到一個矩陣中，這正是您的情況）。請注意，其中一個當然必須重用 $ \mathbf{A} $ 帶有獨立鍵。