FHE 輸出的最短密文大小是多少？
假設我們使用批處理和模數切換技術來減少全同態加密 (FHE) 中密文的大小。
問題：最有效的全同態加密輸出的最短密文比特大小是多少？
備註：我知道有不同的 FHE 方案。我想看看我們可以從輸出最短密文的高效 FHE 中獲得的最短密文是什麼（即使使用上述技術）。
這取決於您是要加密單個位還是多個位。
如果你想加密一個比特，我認為（免責聲明：我可能會遺漏其他方案）最短的密文是由本文的基於 TLWE 的 FHE 實現的（另請參見它所基於的這篇論文）。根據他們的說法，密文擴展“只有”10000 位（即加密一位需要10000 位）。這是因為它們可以簡單地使用類似 LWE 的密文，然後在需要時將它們轉換為 GSW 密文（支持完全同態操作）。
但是，如果您想加密多個位，那麼任何 FHE 方案都可以實現最佳速率 $ 1+o(1) $ 使用標準混合加密： $ n $ 位明文 $ m_1, \cdots, m_n $ 是 $ (\mathsf{FHE}(K), \mathsf{SymEnc}_K(m_1, \cdots m_n)) $ ， 在哪裡 $ \mathsf{SymEnc}_K $ 是帶有密鑰的密鑰加密方案 $ K $ . 要在此密文上同態地評估函式，只需先同態地應用以下電路 $ C $ 至 $ \mathsf{FHE}(K) $ : $ C $ 有 $ E = \mathsf{SymEnc}_K(m_1, \cdots m_n) $ 在其描述和輸入中硬編碼 $ K $ ，它輸出 $ \mathsf{SymDec}_K(E) $ . 因此，此步驟為您提供 $ \mathsf{FHE}(C(K)) = \mathsf{FHE}(\mathsf{SymDec}_K(E)) = \mathsf{FHE}(m_1, \cdots m_n) $ ，然後您可以從中評估您選擇的任何功能。密文大小為 $ n + O(\lambda) $ ， 在哪裡 $ \lambda $ 是一個安全參數，假設 $ \mathsf{SymEnc}_K $ 有率 $ 1+o(1) $ （每個現代對稱加密方案都是這種情況，例如 AES）。