【Eurocrypt 2025】一種對高精度運算的全同態加密（FHE）新方案
原文：https://www.esat.kuleuven.be/cosic/blog/eurocrypt-2025-a-new-fhe-scheme-for-high-precision-arithmetic/
作者：Robin Geelen
譯者：Kurt Pan
許多全同態加密（FHE）的應用都需要在大特徵有限域上進行運算。早前我們已經介紹過兩個此類應用——「盲zkSNARK」與「自舉」。然而，現有所有 FHE 編碼在大特徵有限域上的性能都相當欠佳。為了克服既有方法的缺陷，我們提出了一種稱為廣義 BFV（Generalized BFV，簡稱 GBFV）的新構造。
https://www.esat.kuleuven.be/cosic/blog/blind-zksnarks/ https://www.esat.kuleuven.be/cosic/blog/eurocrypt24-from-null-to-large-p-acceleration-in-bgv-bootstrapping/
先前的方案
BFV 方案
BFV 方案使用一個分圓環 。若要在素域 上運算，便將明文空間實例化為 。這個環上的元素通過標準的環帶錯誤學習（Ring-LWE）加密。
BFV 編碼方案可打包最多 個所謂的「明文插槽」，其中 為歐拉函數。換言之，每個密文可同時加密 個有限域元素。BFV的缺點在於，高Ring-LWE噪聲會隨 線性增長，因此在 很大時性能不佳。
CLPX 方案
CLPX 方案採用完全不同的思路：將明文空間實例化為
是一個的線性多項式。於是，明文空間就對兩個模數定義：分圓多項式和明文模數。這個洞見讓我們可以簡化明文理想：由於明文理想中包含 ，可將 替換為 ，得到
因此明文空間同構於，對。注意此處 未必為質數！
與 BFV 相比，CLPX 的噪聲為 的亞線性增長，可大幅降低Ring-LWE噪聲，但每次只能編碼單一的大整數模 。實際的FHE參數中通常包括數千位元，對於許多應用來說已經非常浪費。
廣義 BFV（GBFV）
GBFV 兼具上述兩者優勢：在大質數 （相較CLPX更小）下，噪聲亞線性增長；同時仍能打包多個插槽（雖較 BFV 少）。換句話說，它在插槽數量與噪聲之間做了巧妙的權衡。
明文空間
我們使用非線性明文模數 來構造 GBFV 的明文空間。利用標準恆等式
其中 為 的根式，我們可以將明文理想化簡為
並要求 為整數。結果，我們得到對模數
的原生算術。後文中，我們將假設 為素數，並稱之為「分圓素數」。
GBFV 在槽數與噪聲量之間存在權衡取捨。這裡先不展開數學細節，簡言之，槽數與 成正比，而 Ring-LWE 的噪聲則隨 增大。因此，根據上述 的定義，在保持 不變的情況下，較大的 （即更多槽）會導致同時較大的 （即更多噪聲）。
插槽編碼
BFV（及 GBFV）的插槽編碼，可視覺化為超立方體結構。每個小立方體（綠色或紅色）代表一個有限域元素的插槽。但注意GBFV 方案可用的插槽比 BFV 少。因此，只有綠色插槽的子集可以裝入有限域元素；紅色插槽完全不包含任何資料。
為了支持任意電路，一項重要操作是混合，也就是對明文插槽進行置換。在超立方體上，這些置換表現為一維的循環旋轉。例如，上圖中在垂直維度上旋轉兩個位置的操作。在 GBFV 方案中，我們必須非常謹慎，確保永遠將有效的綠色插槽映射到其他有效的綠色插槽，絕不可將綠色插槽映射到紅色插槽，因為紅色插槽本身並不包含任何資料。
附加單位根
現在讓我們更深入探討 GBFV 的功能。在盲 zkSNARK 應用 (https://www.esat.kuleuven.be/cosic/blog/blind-zksnarks/) 中，一個重要需求是為分圓多項式素數 （又稱 Goldilocks 素數）定義的擴域 。這可以通過加入適當的單位根來實現。特別地，為了獲得二次擴張，我們將左側的參數更新為右側的參數（此處僅使用密碼學上不安全的玩具參數作為示例）：
這是因為七次本原單位根存在於 而不存在於 。
最初的計畫是對這些參數也繪製一個超立方體可視化，但結果發現右側對應的是一個 4 維超立方體，難以在二維螢幕上呈現🙁。
消除單位根
以上所述的 Goldilocks 參數集位於一個非二的冪的分圓多項式環中。如果我們想使用更標準的二的冪分圓多項式來實現 Goldilocks 素數，就需要上述操作的逆操作：消除單位根。我由衷感謝其中一位匿名的 Eurocrypt 評審指出這一點！思路是從一個非二冪域到一個二冪域取相對範數。讓我們考慮另一個例子（這次包括一個圖）：
在圖中，我們將 3D 超立方體（非二冪分圓多項式的情況）處理為 2D 超立方體（二冪分圓多項式的情況）。此操作透過「剝離」一個維度完成。
環切換
一項有趣的 BFV 操作是在計算過程中更換分圓多項式環。這在 GBFV 中也能實現。我們在此提供另一個對Goldilocks 素數的可視化示例：
在此圖中，我們將分圓多項式環的大小減少一半。因此，明文插槽的數量也相應減少為原來的一半。
轉換為常規 BFV
另一項有趣的操作（尤其是在自舉過程中）是將 GBFV 密文轉換為常規 BFV。重要的是，這僅在保持不變的條件下才可能。讓我們考慮另一個可視化示例：
原有的綠色插槽僅從左側複製到右側。然而，右側的有效插槽數量多於左側，這些額外插槽在轉換後僅包含垃圾數據。
打包到常規 BFV
先前的轉換程序由於存在垃圾插槽，無法有效利用可用的 BFV 空間。為了解決此問題，我們提出了一種打包方法，將多個 GBFV 密文組合到一個 BFV 密文中。
總結來說，我們首先對每個 GBFV 密文分別執行轉換程序，然後將所有垃圾插槽乘以零。此外，為了確保原本的綠色插槽彼此不會互相干擾，我們對每個輸入的超立方體施加不同的旋轉偏移（在示例圖中，第二個超立方體向左旋轉了一個位置；若處理更多輸入超立方體則需使用其他偏移量）。最後，將所有密文（在此示例中最多 8 個）相加，形成一個整齊打包的 BFV 超立方體。再次考慮以下可視化示意：
但等一下：這裡我是不是違反了自己之前定下的規則，因為第二個超立方體將綠色插槽映射到了紅色插槽？事實並非如此，因為此映射是在 GBFV 到 BFV 的轉換程序之後執行的。到那時，我們已經更改了編碼機制，使得每個插槽都可以任意重新排列到新位置。
GBFV 的自舉
每次在全同態加密中執行運算都會累積一定量的密文雜訊。「自舉」則可還原這一過程：它會降低雜訊，以便後續的同態運算能在不影響正確性的情況下繼續進行。
由於技術限制，我們無法直接在 GBFV 方案中實現所有的自舉步驟。我們的解決方案是依賴轉換程序：首先將密文轉換到 BFV 域並使用 BFV 執行自舉的第一步（稱為「噪聲擴張」）；然後再切換回 GBFV 格式，並使用 GBFV 完成後續的自舉步驟（如下圖所示）。
我們也可以通過一次性對多個密文進行批量自舉來優化自舉的吞吐量。在此，我們僅需如下圖所示，用打包操作替代轉換步。
實現
由於 GBFV 的噪聲增長比 BFV 慢，我們可以降低自舉頻率，和／或使用較小的密文和密鑰進行自舉。下表展示了單次自舉的部分實驗結果──在普通 MacBook 上、單線程、128 位安全性下獲得。由於參數更小，我們僅需 2 秒即可完成自舉，這比常規 BFV 快了 5 倍！ 但請注意：使用的插槽越多，噪聲增長就越大。這一點在表中也很明顯：插槽數量多的參數集（例如最右側）會導致噪聲大幅膨脹，且剩餘容量有限；相比之下，最左側的參數集則還有大量空間可供後續計算。
結果採用 且使用費馬素數。