BGV密碼系統中的多項式位分解
我在使用BGV 密碼系統第 9 頁上的 BitDecomp 子常式時遇到問題。我專注於 RLWE 實例化，所以 $ R_q = \mathbb{Z}[x]/(x^d+1,q) $ . 我看不到 BitDecomp 如何處理多項式向量 $ R_q^n $ ，特別是如何 $ u_j $ 的在 $ R_2^n $ .
它是否假設多項式在係數表示中？有人可以舉個例子嗎 $ n=1 $ ， 和 $ n=2 $ ?
要理解這一點，我們必須了解它如何適用於單個多項式（這意味著，對於 $ n = 1 $ ).
首先，考慮一個整數值的二進制分解：給定 $ m \in \mathbb Z_q $ , 總是可以寫成 $ m = \sum_{i=0}^{\log q} b_i 2^i $ , 每個 $ b_i $ 在 $ {0, 1} $ .
現在，看看如果你分解每個係數 $ a_i $ 將多項式轉換為二進製表示 $ \sum_{j=0}^{\log q} b_{j,i} 2^j $ ， 你得到 $ \log q $ 多項式：
$ \begin{align} p(x) &= a_dx^d + a_{d-1}x^d_{d-1} + … + a_1x + a_0\ &= \left( \sum_{j=0}^{\log q} b_{j,d} 2^j \right)x^d + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j \right)x^{d-1} + … + \left( \sum_{j=0}^{\log q} b_{j,1} 2^j \right)x^1 + \sum_{j=0}^{\log q} b_{j,0} 2^j\ &= \left( \sum_{j=0}^{\log q} b_{j,d} 2^jx^d \right) + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j x^{d-1} \right) + … + \left( \sum_{j=0}^{\log q} b_{j,1} 2^jx^1 \right) + \sum_{j=0}^{\log q} b_{j,0} 2^j\ &= \sum_{j=0}^{\log q} \left(b_{j,d} 2^j x^d + b_{j,d-1} 2^j x^{d-1} + … + b_{j,1} 2^j x^1 + b_{j,0} 2^j \right) \ &= \sum_{j=0}^{\log q} \left(b_{j,d} x^d + b_{j,d-1} x^{d-1} + … + b_{j,1} x^1 + b_{j,0} \right) 2^j \ &= \sum_{j=0}^{\log q} u_j(x)2^j \end{align} $
因此，這個 BitDecomp 函式在接收到單個多項式時所做的是返回一個向量，其中包含那些 $ \log q $ 多項式 $ u_j $ .
因此，當給定一個向量時 $ n $ 多項式，它返回一個向量 $ n \cdot \log q $ 多項式。
也許這個答案對您有用，因為它與您的問題非常相關（ $ Dec_{w,q} $ 是使用參數的 BitDecomp 的泛化 $ w $ 到基礎而不是固定值 $ 2 $ ).