在目前的實務上，最常使用的同態加密是 Paillier cryptosystem。是一種非對稱式加密：會有一組公鑰用來加密，一組私鑰用來解密。並且在這情況使用的是 RSA 模組。更具體的說就是公鑰有兩個參數決定：
1. N 決定了安全性滿足
這裡的p ,q 是兩個相異質數。
2. 另一個參數是可隨意選取的亂數 g in [2, N²] 並且 g 和 N 互質。
如同 RSA 的狀況，在 Paillier 的系統中，如果 N 被人家分解出是哪兩個質數，那這個加密法基本上就宣告被破解。因此對於實務上的應用至少 N 的長度至少要 2048-bits 以上。
基本功能
基本上大多數的同態加密都一定有以下這三個 functions ： KeyGeneration, Encryption, Decryption。在 Paillier 中，構造加密這隻函數的是使用以下的數學難題：
用個例子讓大家理解上面的問題有多困難。假設 n=10403 ，z=4。則現在請你找一個 y 使得
除了暴力解讓 y 從 0 到 108222409 帶入驗證以外，似乎是覺得毫無頭緒。不用意外，對數學家們，這個問題也沒有有效的辦法去解它(i.e. 這裡稱的有效指的是多項式時間的演算法)。
這邊我們特別的去看 Paillier 的 Encyption 這支函式的定義可觀察出下列的特性：
- 從加密的方式可以看到，對於同樣的 message m，每次產生的結果都會不一樣，因為每次的輸出都會乘上一個隨機亂數 r。因此這也呼應前面所說的 semantic security。
- 可觀察到這個函數的 input 是在範圍 0 到 N 之間。這個暗示了加密函數的 input 是跟 security level 綁在一起(i.e. N 越大安全性越強)。這一點之後會導致 Paillier cryptosystem 在使用上有其不方便性。
- 當取得密文，並且已知公鑰的所有參數，要能反解出 m，那麼需要能解決上面所提的數學難題。
- 以效率來說， N= 2048-bits 長時，以個人電腦來說加解密速度都是大約是 28 ms 左右的級距。算是相當的有效率。
- 最後從加密函式 Encryption 的定義，我們可以觀察到：
最後的結果可以看成把
當作 Encryption 的 input 後得到的結果。(i.e. 後面的兩個 r 值相乘依然是個亂數)。因此”大體”上我們可以相信 Paillier 的 Encryption 是一個 homomorphism 滿足：
PS： 這個式子的等號是有問題的，以值來說他們左右兩邊不相同，因為使用的 nonce r 是很大的機率是不一樣的。等號的概念可以想成對兩邊再做解密時，所得到的明文結果是一樣的。小結：我們給了一個同態加密的例子，並且展示它的加密是基於哪一個數學難題去保證它的安全性。同時也解釋了為何它有 semantic security以及滿足 homomorphism 的形式。
PS：嚴謹的證明請參考：Paillier 原始論文 或是 J. Katz and Y. Lindell 合寫的 Introduction to Modern Cryptography Section 13.2.
然而…..
Paillier cryptosystem 似乎很棒了，但是其實還藏著一個問題。注意到加密函數 Encryption 的 input 是 0 到 N 之間。然而 N 是由兩個大質數所相乘。但是常常實務上的應用時， message space 是在 0 到 某個質數 P 之間，甚至是更一般的合數( i.e. 非質數)。這種不一致性，會導致當你明明其實想在 message space 內做運算，但是當你使用了同態加密幫你運算，但是隨著運算的次數變多，會發生產生了 “誤差”，也就是說傳回給你的密文，根據你提交的公式計算後，你再用私鑰解密的產物，不是真正你期待的值。
我們舉個例子 (i.e. 裡面有些許不嚴謹的推論)：
假設 Paillier 的 N = 5 * 7 = 35。
假設你現在的 message space 的有效範圍是在 [0,10] 之間 (i.e. 等價 mod 11 的世界)。
此時你選 8 在你的 message space。你把它作加密變成 En(8)。
接下來你希望計算 En(8)En(8)En(8)En(8)En(8) “=” En(40)，再做解密後得到 5，因為
但是呢，依照你自己在 message space 的世界的計算是得到 7，因為
因此導致結果的不一致性。也是常常有人提到的使用同態加密超過一定運算量就會產生 “誤差”。
小結：在 Paillier cryptosystem， 加密函數的 message space 是跟系統的 security level 綁在一起的，使得在實務應用上因為是要用另一個 message space。這種不一致性導致 Paillier cryptosystem 在使用上要注意運算次數過多產生的誤差。
再去搜索大多數的同態加密(i.e. 比方說 Goldwasser–Micali cryptosystem, Benaloh cryptosystem, )會發現幾乎都是基於 RSA model 建立的，也就是會有上面所提的缺點，input 的空間大小被 security level 綁定。因此必定會產生誤差。因此是否存在一個同態加密是可以將兩著拆開，使得加密函數的 input 的空間可以自由指定。若是如此，這樣做任意次數運算，都不會產生誤差。我們會在下個系列文章討論。
Thanks to Chang-Wu Chen and Yu-Te Lin.