是否可以在完全同態加密下修剪一些加密值
假設我們有 $ N $ 同態加密（BFV/BGV ..）下的加密值，我們知道 $ M $ 其中如下 $ t $ . 是否可以刪除那些 $ M $ 價值觀？
眾所周知，有些方法（例如同態比較）可以輸出 $ N $ 加密 $ 1 $ 或者 $ 0 $ s 表示值是否高於 $ t $ 與否，但我需要裁剪下面的 $ t $ , 離開 $ N-M $ 加密值。
編輯：我知道無法直接刪除 $ M $ 值，但是否可以輸出 $ N-M $ 新的加密值，其明文正是那些 $ N-M $ 以上數值 $ t $ .
只要您可以設計一個電路來做到這一點，那麼可以。有幾種方法可以做到這一點。一是搭建排序網路，輸出最高的 $ N-M $ 價值觀。
如果你想直接輸出一個數組 $ N-M $ 新值，您可能需要排序網路。另一種選擇是輸出一個數組 $ N $ 值，其中所有值為 0 或 $ \geq t $ （但你不知道是哪個）。這在應用程序中可能仍然有用。您可以通過映射函式來做到這一點： $$ f(x) = \mathsf{compare}(x, t) \times x $$ 在數組上，其中： $$ \mathsf{compare}(x, t) = \begin{cases} 0 & x < t\ 1 & x \geq t\end{cases} $$ 這給出了一個複雜度 $ N $ 比較計算，和 $ N $ 乘法。一個實用的分揀網路需要 $ \Omega(N(\log N)^2) $ 比較交換門（我相信常數很小，例如 1/2），其中： $$ \mathsf{compare}\text{-}\mathsf{exchange}(x, y) = (\min(x, y), \max(x, y)) $$ 當然比較門和比較交換門是不同的，但我想它們在同態評估方面的難度大致相同。所以你可以保存一個 $ O((\log N)^2) $ 通過不使用排序網路刪除 0 值來考慮因素。