FHE 中的批處理如何工作？
假設我們有一個 BGV 風格的同態加密方案。消息空間將是環$$ R_p = \mathbb Z_p[x]/(x^d + 1) $$在哪裡 $ p $ 是一個素數 $ 1 $ 模組 $ 2d $ . 現在假設我們說消息 $ m_1(x), m_2(x) \in R_p. $ 我們如何獲得加密兩者的密文 $ m_1(x) $ 和 $ m_2(x) $ ? BGV 論文提到了 CRT 同構$$ R_p \cong R_{\mathscr{p_1}} \times … \times R_{\mathscr{p_d}}. $$在這種同構下，我們有映射 $ m_1(x) \to ((m_{1,1})(x),…,(m_{1,d})(x)) $ 我們有一個類似的表示 $ m_2(x) $ . 我仍然不確定我們如何使用此映射來獲得加密兩者的密文 $ m_1(x) $ 和 $ m_2(x) $ 然而同時。
任何澄清將不勝感激。
您的同構意味著您正在分解素數 $ p $ 成幾個素數 $ p_1,…p_d $ ，但當然，您實際考慮的是分圓多項式模 $ p $ ， IE， $ x^d + 1 = f_1(x) \cdot … \cdot f_u(x) \pmod p $ . 由於分圓多項式的性質，每個 $ f_i $ 具有相同的學位 $ o $ , 這實際上等於 $ p $ 在 $ \mathbb{Z}_{2d}^* $ . 然後，槽數為 $ u = d / o $ .
所以，你不能加密兩個多項式 $ d $ 成單個密文。你能做的就是選擇 $ u $ 多項式 $ m_1,…,m_u $ 程度不超過 $ o-1 $ ，然後用 CRT “打包”它們，獲得 $ m \in R_p $ , 最後加密 $ m $ .