同態加密 (Part 1:簡介)

在這篇短文,我們簡介同態加密( 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。以上的流程就是同態加密的精神。

Image for post

要構造 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。

PS:在這邊的討論,並不特別討論半同態 (partial homomorphic encryption:只能對密文做一種運算)或是全同態 (full homomorphic encryption:可以對密文兩種運算)的差異,只是基於同態加密的特性做一個概念性的介紹。

Thanks to Chang-Wu Chen and Yu-Te Lin.

感謝 AMIS ChihYun Chuang 提供本文

原文連結

分享在 facebook
Facebook
分享在 google
Google+
分享在 twitter
Twitter
分享在 linkedin
LinkedIn
分享在 pinterest
Pinterest
%d 位部落客按了讚: