同態加密 (Part 1:簡介)

前言:

ChihYun Chuang
Nov 5 · 5 min read

在這篇短文,我們簡介同態加密( 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。

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

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

getamis

Using breakthrough blockchain technology, Amis has created a standardized platform to let business create information exchange systems and make transaction data open and shareable to improve the quality of life for everyone.

ChihYun Chuang

Written by

getamis

getamis

Using breakthrough blockchain technology, Amis has created a standardized platform to let business create information exchange systems and make transaction data open and shareable to improve the quality of life for everyone.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade