同態加密如何在允許進行數學運算的同時具有機率性？
我一直在玩一些同態加密庫。它讓我更加欣賞機率加密。這兩個答案有助於導致這個問題，但它們本身並不包含這個問題的答案：
對於那些不知道的人，在機率加密中：
- 通過在其開頭附加一個與時間相關的隨機字元串來匿名化一段數據
- 這意味著每次加密時，相同的數據（或“明文”）可以具有不同的值
- 當擁有密鑰的使用者解密數據時，他們會刪除這個前導字元串以取回原始明文
- 在 HE 空間中，單個“位”數據可以是很長的字元串。這意味著 HE 加密字元串包含比正常位更多的“資訊”。這些資訊包含的內容對我來說是個謎。
如您所知，我（認為我）了解機率加密。但我不明白你怎麼可能在機率空間內保留同態。
如果每條數據都有不同的前導隨機字元串，那麼算法如何知道加密數據的哪些部分包含真實值？如何添加和減去兩個具有不同前導字元串的加密數據？
顯然，對加密數據進行數學運算的人無法知道用於解密它的密鑰。所以HE不知何故使用不同的前導隨機字元串來加密每個數據，但是這些數據仍然可以一起相加和相減？這怎麼可能是真的？
機率加密是任何公鑰加密方案的必要條件。原因是在這種方案中，任何人都可以執行加密，因此如果加密是確定性的，則可以檢查明文的猜測。在許多應用程序中，這將是一場徹底的災難：對拋硬幣、班級名冊上的姓名、價格、公告投票、信用卡號或 SSN、密碼進行加密。
有一個非常簡單但有點過於簡單的解釋：
如果使用機率加密算法，解密如何返回正確的消息？
該解釋說加密獲取消息，將其與隨機性結合，然後加密；和解密解密，然後去除隨機性以獲得原始消息。這正是使用隨機填充在 RSA 加密中完成的方式，其中組合有時就像在消息中附加隨機性和固定位一樣簡單（參見例如RSAES-PKCS1-V1_5)）。
但是，這種簡單的解釋達不到同態加密的目標，因為（如問題中所述）它不會產生一種在不持有解密密鑰的情況下對加密消息執行算術的方法。這就是為什麼帶有隨機填充的 RSA 加密不是同態的，而沒有填充的 RSA 是（乘法，以公共模數為模）。
安全的同態加密方案確實結合了消息和隨機性，就像在過度簡化的解釋中一樣，但這種結合不是通過連接來實現的。為了使同態隨機加密起作用，隨機性和消息的組合必須通過一種與方案的其餘部分精確匹配的方法。
Paillier密碼系統是提供安全性和同態性的隨機組合的最簡單範例之一。
對於普通的公鑰加密系統，加密需要最終解密的實體的公鑰。但是（顧名思義）公鑰不是秘密的。在 Pailler 中，它是 $ (n,g) $ 與大 $ n $ 難以分解（類似於 RSA）和選擇 $ g $ 和 $ g^n\bmod n^2=1 $ （通常 $ g=n+1 $ ）。覆蓋加密消息 $ m $ 和 $ 0\le m<n $ 進入
$$ E(m)=g^m,r^n\bmod n^2\quad=c $$在哪裡 $ r $ 是一個新鮮的隨機 $ 0<r<n $ 和 $ \gcd(r,n)=1 $ . 知道因式分解，有效解密是可能的 $ n $ ， 和 $ D(E(m))=m $ 對於所有有效 $ m $ 和 $ r $ .
那種組合消息的方式 $ m $ , 隨機性 $ r $ , 和公鑰 $ (n,g) $ 是這樣的，我們有一個同態屬性：
$$ \begin{array}{llll} E(m_0)E(m_1)\bmod n^2&=g^{m_0},{r_0}^n&g^{m_1},{r_1}^n&\bmod n^2\ &=g^{m_0+m_1}&{(r_0,r_1)}^n&\bmod n^2\ &=g^{(m_0+m_1\bmod n)+w,n}&((r_0,r_1\bmod n)+x,n)^n&\bmod n^2\ &=g^{m_0+m_1\bmod n},{(g^n)}^w&{(r_0,r_1\bmod n)}^n&\bmod n^2\ &=g^{m_0+m_1\bmod n}&{(r_0,r_1\bmod n)}^n&\bmod n^2 \end{array} $$ $ w $ 和 $ x $ 是必然存在的整數，在計算後會消失。在左側，這是由選擇 $ g $ . 在右邊，那是因為多項式 $ x $ 被提升到權力 $ n $ 有所有非常數項的倍數 $ n^2 $ . 我們看到 $ E(m_0)E(m_1)\bmod n^2 $ 與加密的相同 $ m=m_0+m_1\bmod n $ 可能是為了選擇隨機性 $ r=r_0,r_1\bmod n $ .
注意要求 $ 0\le m<n $ , $ 0<r<n $ 和 $ \gcd(r,n)=1 $ 被滿足。
因此，對於有效的解密，我們必須有
$$ D(E(m_0),E(m_1)\bmod n^2)=m_0+m_1\bmod n $$ 或者，對於正常添加：如果 $ 0\le m_0<n/2 $ 和 $ 0\le m_1<n/2 $ 然後 $$ D(E(m_0),E(m_1)\bmod n^2)=m_0+m_1 $$ 要根據該同態屬性生成密碼，需要
至少一個密文 $ c_0=E(m_0) $ 對於未知的消息 $ m_0 $ ，通常由其他人準備（否則為什麼要使用同態加密？）
任何一個
- 第二個類似 $ c_1=E(m_1) $ ，以便能夠計算普通產品 $ c_0, c_1=c $
- 一個新的 $ m_1 $ 組合，以及允許計算的公鑰 $ c_1 $ 並返回上一個選項。
通常至少，公鑰（具體來說，它是組件 $ n $ )，以允許減少 $ c_1,c_2 $ 模組 $ n $ , 有兩個原因
- 隱瞞一個特定的 $ c_i $ 參與了密文的準備（否則可通過測試是否確定 $ c_i $ 劃分 $ c $ )
- 減少的 $ c\bmod n^2 $ 短於 $ c $ 大約 2 倍。