FHEW 中的刷新程序：成員資格測試

我面臨一個關於論文FHEW: Bootstrapping Homomorphic Encryption in less than a second的問題。它涉及刷新過程中的 MSBextract 算法。

特別是，他們提到我們可以將此算法更改為更“通用”的算法，以便檢查不同整數子集的成員資格 $ \bmod t $ 僅在一個刷新過程中。但是，我找不到解決此問題的“有效”方法（我想到的方法需要不止一次刷新）。

你們有沒有一些“提示”可以引導我走向正確的方向？

PS他們還提到了一個xor-for-almost-free程序，如果將明文模數轉換為 $ t=6 $ . 我真的不明白，因為 - 我相信 - 它完全適用於 $ t = 4 $ 與子集 $ S = {1;3} $ . 如果我錯了，請告訴我。

據我所知，有兩篇關於廣義成員測試（甚至函式）提取的文章進一步發展，我希望這可以幫助你：

https://link.springer.com/chapter/10.1007/978-3-319-22174-8_7和 https://eprint.iacr.org/2017/996.pdf

一個小的區別是環尺寸是素數而不是 2 的冪，這消除了對稱性約束。

我認為您對 XOR 的看法是正確的，幾乎可以免費工作 $ t=4 $ ，儘管它可能需要更改其他參數才能正確綁定錯誤。至於幾乎免費的部分，請注意，您可以從同一個密文中提取進位和異或，並且提取部分比循環的其餘部分便宜得多：基本上一次刷新就可以將兩者都取出。

引用自：https://crypto.stackexchange.com/questions/66498