京東云開發(fā)者｜經(jīng)典同態(tài)加密算法Paillier解讀 - 原理、實(shí)現(xiàn)和應(yīng)用 _生活百科

文章插圖
摘要隨著云計(jì)算和人工智能的興起，如何安全有效地利用數(shù)據(jù)，對持有大量數(shù)字資產(chǎn)的企業(yè)來說至關(guān)重要。同態(tài)加密，是解決云計(jì)算和分布式機(jī)器學(xué)習(xí)中數(shù)據(jù)安全問題的關(guān)鍵技術(shù)，也是隱私計(jì)算中，橫跨多方安全計(jì)算，聯(lián)邦學(xué)習(xí)和可信執(zhí)行環(huán)境多個技術(shù)分支的熱門研究方向。
本文對經(jīng)典同態(tài)加密算法Pailier算法及其相關(guān)技術(shù)進(jìn)行介紹，重點(diǎn)分析了Paillier的實(shí)現(xiàn)原理和性能優(yōu)化方案，同時(shí)對基于公鑰的加密算法中的熱門算法進(jìn)行了橫向?qū)Ρ?。最后介紹了Paillier算法的一些實(shí)際應(yīng)用。
【關(guān)鍵詞】：同態(tài)加密，多方安全計(jì)算，聯(lián)邦學(xué)習(xí)，隱私計(jì)算
1 背景知識1.1 同態(tài)加密同態(tài)加密（Homomorphic Encryption，HE）[1]是將數(shù)據(jù)加密后，對加密數(shù)據(jù)進(jìn)行運(yùn)算處理，之后對數(shù)據(jù)進(jìn)行解密，解密結(jié)果等同于數(shù)據(jù)未進(jìn)行加密，并進(jìn)行同樣的運(yùn)算處理。同態(tài)加密的概念最初在1978年，由Ron Rivest，Leonard Adleman和Michael L. Dertouzos共同提出，旨在解決在不接觸數(shù)據(jù)的前提下，對數(shù)據(jù)進(jìn)行加工處理的問題。
目前，同態(tài)加密支持的運(yùn)算主要為加法運(yùn)算和乘法運(yùn)算。按照其支持的運(yùn)算程度，同態(tài)機(jī)密分為半同態(tài)加密（Partially Homomorphic Encryption, PHE）和全同態(tài)加密（Fully Homomorphic Encryption, FHE）。半同態(tài)加密在數(shù)據(jù)加密后只持加法運(yùn)算或乘法運(yùn)算中的一種，根據(jù)其支持的運(yùn)算的不同，又稱為加法同態(tài)加密或乘法同態(tài)加密。半同態(tài)加密由于機(jī)制相對簡單，相對于全同態(tài)加密技術(shù)，擁有著更好的性能。全同態(tài)加密對加密后的數(shù)據(jù)支持任意次數(shù)的加法和乘法運(yùn)算。
1.2 復(fù)合剩余類問題【京東云開發(fā)者｜經(jīng)典同態(tài)加密算法Paillier解讀 - 原理、實(shí)現(xiàn)和應(yīng)用】如果存在一個數(shù)

文章插圖
那么符合公式z ≡ yn (mod n2)的數(shù)z，稱為y的模n2的n階剩余。復(fù)合剩余類問題（decisional composite residuosity assumption , DCRA)，指的是給定一個合數(shù)n和整數(shù)z，很難確定模n2的n階剩余數(shù)z是否存在。
1.3 中國剩余定理中國剩余定理（Chinese Remainder Theorem, CRT），又稱為孫子定理，源于《孫子算經(jīng)》，是數(shù)論中的一個關(guān)于一元線性同余方程組的定理，說明了一元線性同余方程組有解的準(zhǔn)則以及求解方法。
有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？翻譯為數(shù)學(xué)語言為：

文章插圖
其通用方程為：

文章插圖
中國剩余定理的解法流程為：

文章插圖
2 Paillier算法原理2.1 Paillier簡介在Paillier算法出現(xiàn)之前，基于公鑰加密的算法主要有兩個分支：

以RSA為代表的，基于大數(shù)因數(shù)分解難題的公鑰加密算法
以ElGama為代表的，基于大數(shù)離散對數(shù)難題的公鑰加密算法

Paillier加密算法，由Pascal Paillier于1999年發(fā)表，給出了公鑰加密算法的一個新的分支領(lǐng)域。Paillier基于復(fù)合剩余類難題，滿足加法同態(tài)和數(shù)乘同態(tài)，具有非常高效的運(yùn)行時(shí)性能。
2.2 一個典型的應(yīng)用場景

文章插圖
圖1 傳統(tǒng)聯(lián)邦學(xué)習(xí)同態(tài)加密算法使得密文數(shù)據(jù)，在沒有額外數(shù)據(jù)泄露的情況下，可以在第三方平臺進(jìn)行進(jìn)一步加工處理。隨著大規(guī)模云計(jì)算的興起，尤其是涉及到敏感數(shù)據(jù)的云計(jì)算，同態(tài)加密算法將是其中至關(guān)重要的技術(shù)基礎(chǔ) 。我們以一個典型的聯(lián)邦學(xué)習(xí)的例子為切入點(diǎn)，看看Paillier算法的原理和在實(shí)踐中應(yīng)用的問題。