從綠逗薏人開始的同態加密 Homomorphic Encryption

從下午茶聊起

你是公司下午茶的固定採購，有天，同事邊吃著綠逗薏人過來問你：

「誒？你那碗料怎麼這麼多，是不是偷偷加料？」

「沒有啊，大家都一樣，一碗 90。」

「我不信，收據拿來！」

你遞上會計工讀生開的會計傳票，上面只寫著：

2607 + 6435 = 9042
By 會計工讀生

這三小？你是不是在唬爛作假賬？

同事感到非常奇怪，直接對你發起質疑。 別急，這是用 Paillier 加密的收據。數學公式是這樣的。

# 加密公式
c = (m + k * p) mod n

# 解密公式
m = c mod p

其中：

• m：原始金額
• k：隨機鹽
• p：密鑰
• n：模數（確保加密後的密文長度不會爆炸） 我們的密鑰是 211，來驗算總金額：

m = c mod p = 9042 mod 211 = 180

你看，1 碗 90，2 碗總金額是 180，對上了吧。

李組長眉頭一皺，發現案情並不單純

雖然同事暫時被唬住，但他還是不死心去問工讀生：

「欸你下午茶金額怎麼輸入的？180 是怎麼來的？」

工讀生一臉黑人問號

「180？我只是照著 2607 和 6435 加的啊，總和就是 9042。」

同事震驚

「帳是你做的你卻不知道原始數據？這怎麼可能？」

同事依舊不放棄向你提出質疑

「2607 和 6435 兩碗金額根本不同！」

「哎呀，你誤會我了，公式裡面不是有 k 嗎？每個數字加鹽用的 k 都不一樣，算出來當然不同啊」

年底會計師來查帳了

會計師看著報表皺著眉頭請你進會議室

「兩碗綠逗薏人 9042 元？這報銷你解釋一下。」

「這是加密的資料啦，實際金額是 180，我馬上解給你看。」

你打開區塊鏈記錄，指出密鑰 p = 211，並開始計算：

# 第一碗：金額 75, k = 12
c1 = 75 + 12 * 211 = 2607

# 第二碗：金額 105, k = 30
c2 = 105 + 30 * 211 = 6435

# 加總密文
c_add = c1 + c2 = 9042

# 解密加總
m_add = c_add mod p = 9042 mod 211 = 180

「75 + 105 = 180，帳完全對得上！」

會計師點了點頭，很滿意地叫你回去。走出會議室，你的同事在門外堵你，他非常火大。

「兵不厭詐，這是同態加密」