按位同態加密

我對 HE 很陌生，想簡要說明一下整數是如何使用位安全加密的。主要思想是加密每個位值並將n位數字表示為n個密文，如下所示：$$ E(x)=(E(x1),E(x2),…,E(xn)) $$其中 xi 是位置 i 上的位。當我只有以特定順序對應於“0”和“1”的密文時，為什麼這樣安全？例子： $$ 101 -> (E(1), E(0), E(1)) $$ 我不能只從 E() 值中猜測 101。為什麼這是不可能的？向我指出一篇好論文或閱讀將不勝感激！

是的，對手可以猜測明文，並且有一定的機率 $ p $ 他的猜測是正確的。我們無法阻止這種情況，這不是加密方案的安全漏洞。

如果您使用的同態加密方案是 IND-CPA 安全的（或等效的語義安全），則密文應該是不可區分的。這意味著任何（PPT）對手都無法從密文中獲得關於明文的有用資訊，因此密文不會給對手任何猜測正確明文的優勢。所以沒有密文，猜對的機率是 $ p $ ，而對於密文，猜對的機率為 $ p+\epsilon $ 在哪裡 $ \epsilon $ 可以忽略不計。因此，密文雖然是從明文產生的，但從對手的角度來看是無用的。

所以外賣的資訊是，加密方案的安全性不是用“無法恢復明文”（這是不可能實現的）來定義的，而是用“該方案不會讓對手更容易恢復明文”來定義”。

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