SEAL 同態乘法
在 SEAL 同態加密庫中，有一個內部過程將一個係數較大的多項式分解為一個係數較小的多項式向量。該過程在此處的第 3-4 頁中進行了描述。我想知道是否有人可以解釋該過程並提供一個簡單的範例來說明如何通過該過程完成多項式乘法以及為什麼它比教科書多項式乘法然後進行模減少更好。
讓 $ n = 4 $ , $ q = 199 $ , $ w = 16 $ . 這意味著 $ \ell_{w,q}=2 $ , $ \mathbb{Z}_q = {-99,…,99} $ ， 和 $ \mathbb{Z}_w = {-8,…,7} $ .
讓 $ a = 70X^2 + 56X+45 $ 和 $ b = 61X+31 $ .
請展示 $ Dec_{w,q}(a) $ 和 $ Pow_{w,q}(b) $ 以及內積如何等效於多項式乘法如下： $ \langle Dec_{w,q}(a),Pow_{w,q}(b) \rangle = a.b \pmod q $ .
在這個答案中，我正在減少使用的中心表示 $ \mathbb{Z}_q $ 和 $ \mathbb{Z}w $ . 還有，我在寫 $ \ell $ 代替 $ l{w,q} $ 簡化符號。
具體例子：
- $ Dec_{w,q}(a) = (6x^2 - 8x - 3, 4x^2 + 4x + 3) $
- $ Pow_{w,q} = (61x + 31, 61\cdot16x + 31\cdot16) = (61x + 31, -19 x + 98) \pmod q $
因此，我們有以下內積：
$$ \begin{align} Dec_{w,q}(a)\cdot Pow_{w,q}(b) &= (6x^2 - 8x - 3) \cdot (61x + 31)+( 4x^2 + 4x + 3) \cdot (-19 x + 98) \ &= (366 x^3-302 x^2-431 x-93) + (-76x^3+316 x^2+335 x+294)\ &= 290 x^3+14 x^2-96 x+201 \ &= 91x^3 + 14x^2 -96x + 2 \end{align} $$
和通常的產品減少模 $ q $ 是：
$ a \cdot b = 4270 x^3+5586 x^2+ 4481x+1395 = 91x^3 + 14x^2 + -96x + 2 $
解釋：
為了有一個簡單的理解，想想整數（或者，次數等於 0 的多項式）：在這種情況下，很容易看出給定一個整數 $ a $ ，我們可以寫 $ a $ 在基地 $ w $ 獲取數字 $ a_\ell, …, a_1, a_0 $ 這樣
$$ a = \sum_{i=0}^\ell a_i \cdot w^i $$
特別是，如果 $ w = 2 $ ，那麼這是二進製表示。
現在的關鍵是要理解為什麼它仍然有效，如果 $ a $ 是任何多項式。事實上，它是有效的，因為我們只是將每個係數寫在 base $ w $ , 獲得 $ \ell $ 每個係數的數字，然後我們定義 $ \ell $ 多項式，每個多項式 $ a_i $ 擁有 $ i $ -每個係數的第一個數字…
例如，讓 $ p(x) = 3x^3 + 2x + 1 $ , $ q = 199 $ 和 $ w = 2 $ ，然後，將每個係數寫入基數 $ w $ , 獲得 $ 3 = (1,1)w $ , $ 2 = (0,1)w $ ， 和 $ 1 = (1, 0)w $ ，因此，我們得到 $$ Dec{w,q}(p) = (\underbrace{1x^3 + 0x + 1}{\text{First digits}}, \underbrace{1x^3 + 1x + 0}{\text{Second digits}}) $$
所以，一旦我們接受了上面的總和適用於任何多項式 $ a $ ，即，我們可以分解任何多項式，將其係數寫入基數 $ w $ ，那麼，理解為什麼內積等於通常的積就很簡單了。
功能 $ Pow_{w,q}(b) $ 只需將上述總和分解的指數放入具有多項式的向量中 $ b $ : $ Pow_{w,q}(b) = (b\cdot w^0, b\cdot w^1, …, b\cdot w^\ell) $ .
因此，我們有
$$ \begin{align} Dec_{w,q}(a) \cdot Pow_{w,q}(b) &= (a_0, …, a_\ell) (b\cdot w^0, …, b\cdot w^\ell) & \ &= \sum_{i=0}^\ell a_i b w^i & (\text{By defn. of dot product}) \ &= b \sum_{i=0}^\ell a_i w^i & (\text{Since } b \text{ doesn’t depend on } i)\ &= b a & (\text{With the above equality}) \end{align} $$
關於您的其他問題：
為什麼它優於教科書多項式乘法，然後是模減少。
我想你已經錯過了了解 SEAL 的手冊……這兩個函式用於重新線性化步驟（在原論文中稱為 KeySwitch），它們不是用來提高乘法的效率，它們是用來保證正確性的原始私鑰下的解密（以及管理雜訊增長）。我建議你閱讀原 YASHE論文的第 5 部分。