Homomorphic-Encryption
如何理解 HE 中的這些概念：Bootstrapping、Modular Switching、Key Switching、Evaluation、Relinearization？
我想區分不同的概念：Bootstrapping、Modular Switching 和 Key Switching。我有時也對評估和重新線性化感到困惑。
我對這些概念的理解是：
- 自舉是一種縮小密文錯誤的方法。
- 模組化交換只是一種算術技術，用於傳輸例如環元素 $ \mathcal{R}{t} $ 進入 $ \mathcal{R}{q} $ .
- 密鑰切換涉及評估密鑰（或重新線性化密鑰），該密鑰基本上加密密鑰以實現對同態多重和旋轉的評估。
- 我對評估的理解是計算同態 add/mult/rotate/… 而重新線性化是應用關鍵切換技術來實現這些評估。所以基本上， eval 鍵和 relin 鍵幾乎是相同的東西，但命名方法不同？
我在這裡誤解了什麼嗎？
此外，這些技術是否有任何最新的調查/比較？
非常感謝！
- 有點，不是真的。“收縮”聽起來像是您可以重複某些過程，直到出現“沒有錯誤”（這是不安全的）。相反，我建議將其視為“重置”錯誤級別。這是一個很小的差異，但它清楚地表明了一個可以消除多少錯誤的“下限”。
- 是的，粗略。如果您將密文視為秘密的元素，這可能更有意義 $ \mathcal{R} $ ， 而不是 $ \mathcal{R}_q $ 或者 $ \mathcal{R}_t $ . 密文被編碼為 $ \mathcal{R} $ -以特定方式的元素，例如 $ (a(x), a(x)s(x) + e(x) + \Delta m(x)) $ 對於一些比例因子 $ \Delta $ . 模數切換實際上只是一種改變這個比例因子的技術 $ \Delta $ . 這有結果（當 $ \Delta\mid q $ ) 的“改變明文算術”從 mod $ q/\Delta $ 至 $ q/\Delta’ $ ，但您可以更改為某個比例因子 $ \Delta’\nmid q $ 這實際上並沒有連貫定義的“明文模數”。
- 密鑰切換確實是一種改變表單密文的方法 $ \mathsf{Enc}s(m) $ 至 $ \mathsf{Enc}{s’}(m) $ ，即切換一個正在加密的特定密鑰。你是對的，它通常涉及一個評估密鑰（通常稱為密鑰切換密鑰），但這並不完全是這個想法的基礎——如果有人有辦法在沒有循環安全假設的情況下進行密鑰切換/a key-switching key，我們可能都切換到它，仍然稱它為“keyswitching”。我說作為支持獲取任何密文的密碼系統並不完全是基本的 $ \mathsf{Enc}_s(m) $ 並將其切換為任意（可能是攻擊者控制的）密鑰顯然是不安全的。
- 並不真地。當你做“基於張量的乘法”時，你需要重新線性化。還有其他不需要重新線性化的乘法方法（“基於小工具”）。沒錯，您可以將所有不是私鑰/公鑰的密鑰統稱為“評估密鑰”，但並非每個評估密鑰都是重新線性化密鑰。
歡迎來到 Crypto SE :-)
這些概念在不同的層次上運作，所以我首先建議你在這裡製作一個層次的思維圖。最重要的是，您通常具有同態加密，我假設您已經熟悉了。事實證明，在我們所知道的所有（完全）同態結構中，每個密文都有一些相關的雜訊，並且可以有許多等效的密文解密為相同的東西，但具有不同的雜訊。通常，當對密文進行操作時，結果的雜訊嚴格大於操作數的雜訊，並且它會不斷增加，直到密文變得不可用。自舉可以防止這種情況發生；這種技術會清理密文，以便它可以進一步用於同態操作。
（您可能對為什麼將其稱為引導程序感到困惑。這是因為該技術的基本思想是對解密算法進行同態評估，例如，加密方案使用自己的解密電路來獲得更清晰的密文。）
其餘概念特定於同態加密方案的一種特定結構；請參考@Mark 的回答。