在這篇短文，我們簡介同態加密( homomorphic encryption) 的基本概念，以及應該具有的密碼學性質。
之後會在系列文章給予兩個例子 (asymmetric algorithm)：Paillier 和 C.L. homomorphic encryption。並且在例子 Paillier 解釋為何滿足同態加密的特性。在 C.L. homomorphic encryption 我們點出在應用上為何它比 Paillier 更優越之處。
什麼是同態加密( homomorphic encryption)：
同態加密指的是一種加密方式，使得使用者可以對密文做計算，計算出來的結果，再做解密的時候的明文是預期的計算結果。
舉個例，當用戶想要做大量的統計數據，但是他的個人電腦無法執行這些大量的計算。由於資料可能是敏感的，因此不能直接明文的跑在雲端超強電腦計算。同態加密提供一個媒介，讓用戶把資料加密後傳給雲端電腦，根據用戶寫好的算式，電腦執行對應密文的運算，最終把結果傳回給用戶。當用戶取得結果，只要將其解密，便可以解決用戶的問題。
在這個例子，同態加密扮演的角色是提供一個方法，將資訊傳到一個公開平台前先加密，之後在平台做密文運算。對於平台方，他也不知道他處理的數據明文是什麼？但是他卻能正確得到用戶期許的結果。
聽起來似乎很神奇，如果是學習過基本代數的人，可以用更簡單的方式去了解這個過程。考慮兩個群 G 和 H，兩個群中有自己的運算。所謂的 (partial) homomorphic encryption 就是一個 (group) homomorphism 從 G 到 H。因此 G 裡面的運算，可以藉由這個 homomorphism 傳到 H 裡面的元素作運算。因此講白了，同態加密就是一個 homomorphism 從明文的世界送到密文的世界。在下圖中，我們想在 G 中計算 x*y，但是因為某些原因，我們藉由 f 作加密，送到 H 的 世界計算 f(x)*f(y) (i.e. 既然 f 是 homomorphism，所以 f(x)*f(y)=f(x*y)，接著在 H 世界的人把 f(x)*f(y) 傳回給我們，我們會有解密函數，可以想像成 f 的反函數 g (i.e. g(f(x)) = x)，可以把結果 f(x)*f(y)=f(x*y) 做解密得到 x*y。以上的流程就是同態加密的精神。
要構造 homomorphism 是容易的。基本上從小到大學過各式各樣的 homomorphism。舉個例子：假設兩個空間都是實數，運算是加法。令f(x) = 3x，則 f(x) 是一種加法的 homomorphism。
因為：f(x+y)=3(x+y)=f(x)+f(y)。
同時可以看出以這種函式作加密的密文是某個數字叫做 a (i.e. a=3x)。假設現在有兩個密文 a, b 分別對應明文 x, y，因此必須滿足關係 a=3x 和 b=3y。此時我們對密文作加法運算 a+b。此時對 a+b 做解密換句話就是找出什麼變數 z 滿足 3z = a+b，這時候會有一個解叫 z = x+y。在這個例子我們看出，我們對密文作操作 (i.e. a+b) 可以等 “ 同於 ” 對明文做操作 (i.e. x+y)。
但是呢，如果用這種加密法 f 當作你的加密函數。此時你會發現這個 homomorphism 不大靠譜，因為當你朋友收到密文假設是 15 時，他如果知道你加密的方式(i.e. 也就是去反解 f(x)=15 )，他立刻可以知道明文是 5。因此同態加密的如同其他的密碼學加密法都必須有一個特性：當沒有一些關鍵資訊時，經過加密的密文是很難回推明文的。而這個需求，在密碼學會引入一些作者和大家共識 “ 相信某類型的數學問題很難解 ” 去解決這個需求 。而為了方便解密，同態加密會對應這些困難的數學問題設立巧門，在特別的條件下，這些困難的問題會變成很好解，也就是可以容易的找到明文。
除此之外，好的同態加密還會有個特性稱作 semantic security。擁有這個特性的同態加密可以抵抗選擇明文攻擊 (i.e. chosen-plaintext attacks)。這邊不詳述兩個專業名詞的定義。但是用個例子讓大家理解擁有 semantic security 的同態加密會有什麼現象。對於相同的明文稱作 x，則今天用同態加密方法 En去加密他，也就是得到 En(x)。對同樣的 x 和相同的 En計算 En(x) 100 次，你會發現這一百次出來的結果都不一樣。但是呢，你將這一百個值做解密，會發現給出的答案都是 10。產生這個效果的方法，通常是在加密階段加上一個隨機數將他作用上去，造成產生的密文可以有多樣的變化。因此對於外人而言，他很難由加密的結果去判斷到底原本的明文是什麼。因為每個明文經過加密的結果是複雜度高的。
小結：同態加密是一個允許對密文作運算的加密法且會滿足 semantic security。
ＰＳ：在這邊的討論，並不特別討論半同態 (partial homomorphic encryption：只能對密文做一種運算)或是全同態 (full homomorphic encryption：可以對密文兩種運算)的差異，只是基於同態加密的特性做一個概念性的介紹。
Thanks to Chang-Wu Chen and Yu-Te Lin.
感謝 AMIS ChihYun Chuang 提供本文
