安全多方計(jì)算

在討論安全多方計(jì)算(下文使用 MPC) 之前，我們先討論安全多方計(jì)算的設(shè)定，在MPC 的所有參與者中，某些參與者可能會(huì)被一個(gè)敵手 (攻擊者) 控制，在敵手控制下的參與者被稱為被腐化方，它在協(xié)議執(zhí)行過程中會(huì)遵循敵手的指令對(duì)協(xié)議進(jìn)行攻擊。一個(gè)安全的協(xié)議應(yīng)經(jīng)得起任何敵手的攻擊。為了正式描述和證明一個(gè)協(xié)議是“安全”的，我們需要對(duì)MPC的安全性進(jìn)行精準(zhǔn)定義。

1.安全性

安全多方計(jì)算的安全性規(guī)范是通過一種理想世界/現(xiàn)實(shí)世界的范式 (Ideal/Real Paradigm)來定義的。在理想世界中，存在一個(gè)可信的第三方 (Trusted Third Party，TTP)，每個(gè)參與方將各自的秘密數(shù)據(jù)通過安全信道提供給可信第三方，由第三方在聯(lián)合的數(shù)據(jù)上進(jìn)行函數(shù)的計(jì)算，在完成計(jì)算后，可信第三方把輸出發(fā)給各個(gè)參與方。由于在計(jì)算過程中，每個(gè)參與者唯一可執(zhí)行的動(dòng)作是將秘密數(shù)據(jù)發(fā)送給可信第三方，因此，攻擊者唯一可執(zhí)行的是選擇被腐化參與者的輸入，且攻擊者除能獲得計(jì)算結(jié)果以外，不能得到其他任何信息。

與理想世界相對(duì)應(yīng)的是現(xiàn)實(shí)世界，現(xiàn)實(shí)世界中不存在可信第三方，參與者在沒有任何外部節(jié)點(diǎn)幫助下參與協(xié)議執(zhí)行，且部分參與者可能被攻擊者“腐化”或存在合謀。因此，現(xiàn)實(shí)世界中的一個(gè)安全協(xié)議，需要經(jīng)受它在現(xiàn)實(shí)世界的任竟敵手的攻擊，當(dāng)在理想世界中存在同樣敵手攻擊時(shí)，敵手與誠實(shí)參與者在理想世界執(zhí)行中的輸入/輸出數(shù)據(jù)的聯(lián)合分布與現(xiàn)實(shí)世界執(zhí)行中的輸入/輸出數(shù)據(jù)的聯(lián)合分布在計(jì)算上不可區(qū)分，即在理想世界中模擬了現(xiàn)實(shí)世界的協(xié)議執(zhí)行。

理想世界/現(xiàn)實(shí)世界范式是為了確保滿足“安全性”所隱含的多個(gè)屬性。

1) 隱私：任何一方都不應(yīng)該獲取超過它規(guī)定的輸出，特別是不應(yīng)該從輸出信息中獲取其他合作方的輸入信息。攻擊者在理想世界中獲取不到任何除被腐化方輸出以外的其他信息，那么在現(xiàn)實(shí)世界中也同樣如此。

2) 正確性：保證每一方收到的輸出都是正確的。誠實(shí)參與者在現(xiàn)實(shí)世界所得到的輸出與理想世界從可信第三方得到的輸出是相同的。

3) 輸入獨(dú)立性:被腐化的參與者所選擇的輸入必須與誠實(shí)參與者輸人無關(guān)。在理想世界的協(xié)議執(zhí)行中，被腐化參與者在發(fā)送輸入給可信第三方時(shí)，無法獲取誠實(shí)參與者的任何輸入信息。

4) 保證輸出：被腐化的參與者不應(yīng)當(dāng)具備阻止誠實(shí)參與者獲取輸出的能力。

5)公平性：當(dāng)且僅當(dāng)誠實(shí)參與者獲取輸出時(shí)，被腐化的參與者才能獲取輸出，即不存在被腐化參與者獲取了輸出而誠實(shí)參與者未獲取輸出的情況。在理想世界中，可信第三方總是將輸出返回給所有參與者。因此可以保證輸出和公平性。這也意味著在現(xiàn)實(shí)世界中，誠實(shí)參與者得到與理想世界同樣的輸出。

2.參與者

我們需要對(duì) MPC 的參與者進(jìn)行定義：MPC 的參與者是指參與協(xié)議的各方，每個(gè)參與者可被抽象為具有概率多項(xiàng)式時(shí)間算法 (Probabilistic Polynomial Time Algorithm，PPT Algorithm）的交互圖靈機(jī)。根據(jù)協(xié)議執(zhí)行過程中的敵手對(duì)參與者的控制能力/權(quán)利，可將被腐化參與者分為三種敵手類型。

1) 半誠實(shí)敵手：這類參與者會(huì)按照協(xié)議的要求執(zhí)行各個(gè)步驟。然而，半誠實(shí)敵手會(huì)設(shè)法獲取所有協(xié)議執(zhí)行過程中的信息 (包括執(zhí)行腳本和所有接收到的消息)，并試圖推導(dǎo)額外的隱私信息。

2) 惡意敵手：這類參與者在執(zhí)行協(xié)議過程中，完全按照攻擊者的指令執(zhí)行協(xié)議的各個(gè)步驟，不僅會(huì)將所有的輸入、輸出，以及中間結(jié)果泄露給攻擊者，還會(huì)根據(jù)攻擊者的意圖改變輸入信息、偽造中間及輸出信息，甚至終止協(xié)議。

3) 秘密敵手：這種類型的敵手可能對(duì)協(xié)議進(jìn)行惡意攻擊，一旦它發(fā)起攻擊，有一定的概率會(huì)被檢測到。如果沒有被檢測到，那么它就可能完成了一次成功的攻擊 (發(fā)起攻擊是為了獲取額外的信息)。

因此，根據(jù)安全多方計(jì)算協(xié)議中的不同參與者在現(xiàn)實(shí)世界的攻擊行為，可將協(xié)議的安全模型進(jìn)行如下劃分。

1)半誠實(shí)模型 (The Semi-Honest Model)：在協(xié)議執(zhí)行時(shí)，參與者按照協(xié)議規(guī)定的流程執(zhí)行，但是可能會(huì)被惡意攻擊者監(jiān)聽并獲取到在協(xié)議執(zhí)行過程中自己的輸入、輸出，以及在協(xié)議運(yùn)行過程中獲得的信息。

2)惡意模型 (The Malicious Model)：在協(xié)議執(zhí)行時(shí)，攻擊者可以利用在其控制下的參與者，通過不合法的輸入或者惡意篡改輸入等方法來分析誠實(shí)參與者的隱私信息，還可以通過提前終止和拒絕參與等方式導(dǎo)致協(xié)議終止。

另外，根據(jù)敵手何時(shí)及如何控制參與方，可以將敵手的腐化策略分為下列三種模型。

1)靜態(tài)腐化模型 (Static Corruption Model)：在該模型中，在協(xié)議開始之前，由敵手固定控制一組合作方。誠實(shí)的合作方始終是誠實(shí)的，腐化的合作方始終是腐化的。

2)自適應(yīng)腐化模型 (Adaptive Corruption Model)：敵手能夠自主決定什么時(shí)間對(duì)哪個(gè)參與者進(jìn)行腐化，需要注意的是，一旦一個(gè)參與者被腐化，它將始終保持腐化狀態(tài)。

3)主動(dòng)安全模型(Proactive Security Model)：誠實(shí)參與者可能在某一段時(shí)間被腐化，被腐化參與者也可能在某一段時(shí)間變?yōu)檎\實(shí)參與者。主動(dòng)安全模型是從一個(gè)可能存在入侵網(wǎng)絡(luò)、服務(wù)或設(shè)備的外部敵手的角度來講的，當(dāng)網(wǎng)絡(luò)被修復(fù)時(shí)，敵手失去了對(duì)機(jī)器的控制，被腐化的參與者變?yōu)檎\實(shí)參與者。

在現(xiàn)實(shí)世界中，MPC 協(xié)議不是孤立運(yùn)行的，通常是對(duì)協(xié)議進(jìn)行模塊序列化組合或與其他協(xié)議并行 (運(yùn)行) 組合得到一個(gè)更大的協(xié)議來運(yùn)行。

有研究證明，如果一個(gè) MPC 協(xié)議在一個(gè)更大的協(xié)議中按序列運(yùn)行，則它仍然遵守現(xiàn)實(shí)/理想世界范式，即存在一個(gè)可信第三方執(zhí)行該協(xié)議并輸出對(duì)應(yīng)結(jié)果。這個(gè)理論被稱為“模塊化組合”，它允許使用安全子協(xié)議以模塊化的方式構(gòu)造更大的協(xié)議，以及分析一個(gè)使用MPC 進(jìn)行某些計(jì)算的更大的系統(tǒng)。

對(duì)于協(xié)議并行運(yùn)行的情況，當(dāng)有其他協(xié)議與當(dāng)前協(xié)議并行運(yùn)行時(shí)，若該協(xié)議不需要其他并行協(xié)議發(fā)送任何消息，則可將該假設(shè)稱為協(xié)議的獨(dú)立設(shè)定，它也是 MPC 安全性的基本安全定義。在獨(dú)立設(shè)定下，一個(gè)并行運(yùn)行的協(xié)議與可信第三方執(zhí)行的行為一樣。

最后，在一些其他場景中，MPC 協(xié)議可能與該協(xié)議的其他實(shí)例，或其他 MPC 協(xié)議，抑或其他不安全協(xié)議并行運(yùn)行，協(xié)議實(shí)例可能需要與其他實(shí)例進(jìn)行交互，此時(shí)該協(xié)議的運(yùn)行可能是不安全的。協(xié)議在理想世界中不包含與其他協(xié)議 (功能函數(shù)) 的交互，而在現(xiàn)實(shí)世界中需要與另一個(gè)功能函數(shù)進(jìn)行交瓦，與理想世界的模擬存在不同的執(zhí)行條件 (可將此時(shí)的現(xiàn)實(shí)世界稱為混合世界)。在這種情況下，主流的方式是采用“通用組合”(Universal Composability) 進(jìn)行安全定義，在此定義下，任何被證明是安全的協(xié)議都被保證按照理想的行為執(zhí)行，而不論它與其他任何協(xié)議是否并行執(zhí)行。

MPC 的安全定義具有重要作用，具體地講，如果一個(gè) MPC 協(xié)議在現(xiàn)實(shí)世界是安全的，那么對(duì)于一個(gè)使用 MPC 協(xié)議的從業(yè)人員，他可以僅考慮該 MPC 協(xié)議在理想世界中的執(zhí)行情況，即對(duì)于非密碼學(xué)的 MPC 協(xié)議的使用者，可以不考慮 MPC 協(xié)議如何運(yùn)行，或者該協(xié)議是否安全，因?yàn)槔硐肽Ｐ蛯?duì) MPC 的功能提供了更清晰和更簡單的抽象。

盡管理想模型提供了簡單的抽象，但有些情況下容易產(chǎn)生如下問題。

1) 在現(xiàn)實(shí)世界中，敵手可能輸入任何值，且 MPC 協(xié)議沒有通用的解決方案來防止這種情況。例如，對(duì)于“百萬富翁”問題，敵手可以任意輸入被腐化參與者的財(cái)富量 (比如直接輸入最大值)，那么敵手腐化方永遠(yuǎn)是“勝利”的一方。如果一個(gè) MPC 協(xié)議的應(yīng)用依賴于參與者的正確輸入，那么需要通過其他技術(shù)增強(qiáng)/驗(yàn)證參與者輸入的正確性。

2) MPC 協(xié)議僅保證計(jì)算過程安全，而無法保證輸出安全。MPC 協(xié)議的輸出結(jié)果在各參與者揭秘之后，給出的輸出結(jié)果可能會(huì)透露其他參與者的輸入信息。例如，需要計(jì)算兩個(gè)參與者薪資的平均數(shù)，MPC 協(xié)議可以保證除輸出平均薪資以外不會(huì)輸出任何其他信息。但是，其中一個(gè)參與者完全可以根據(jù)自己的薪資和平均薪資，計(jì)算出另一個(gè)參與者的薪資。因此，使用 MPC 并不意味著所有信息都能受到保護(hù)。

在實(shí)踐過程中，考慮到 MPC 的計(jì)算和通信開銷問題，通常會(huì)以半誠實(shí)模型為主要安全設(shè)定。因此，本書中討論的 MPC 協(xié)議也主要以半誠實(shí)模型的協(xié)議為主，雖然部分 MPC 協(xié)議可以同時(shí)支持半誠實(shí)和惡意安全性，但本文仍主要關(guān)注 MPC 協(xié)議的半誠實(shí)設(shè)定。

密碼學(xué)

密碼學(xué)是隱私計(jì)算技術(shù)的重要基礎(chǔ)，在隱私計(jì)算的各個(gè)技術(shù)路線中經(jīng)常被使用。密碼學(xué)理論體系非常龐大且復(fù)雜，感興趣的讀者可參考《現(xiàn)代密碼學(xué)及其應(yīng)用》等圖書擴(kuò)展學(xué)習(xí)，本文僅對(duì)密碼學(xué)的基礎(chǔ)知識(shí)和隱私計(jì)算中常用密碼學(xué)原語進(jìn)行簡單介紹。

在MPC 協(xié)議中，經(jīng)常會(huì)使用兩種數(shù)據(jù)加密方式：對(duì)稱加密和非對(duì)稱 (公鑰) 加密。

1) 對(duì)稱加密是應(yīng)用較早的加密算法，其技術(shù)成熟。因?yàn)榧用芎徒饷苁褂猛粋€(gè)密鑰，所以它被稱為對(duì)稱加密。常見的對(duì)稱加密算法有 DES、AES、IDEA 等。

2) 非對(duì)稱加密也叫作公鑰加密。與對(duì)稱加密不同的是，非對(duì)稱加密算法需要兩個(gè)密鑰：公 (public key) 和私鑰 (private key)，且二者成對(duì)出現(xiàn)。私鑰被自己保存，不能對(duì)外泄露。公鑰指的是公共的密鑰，任何人都可以獲得該密鑰。通常使用公鑰對(duì)數(shù)據(jù)進(jìn)行加密，使用私鑰進(jìn)行解密。非對(duì)稱加密還有另一種用法，即數(shù)字簽名，使用私鑰對(duì)數(shù)據(jù)進(jìn)行簽名，使用公鑰進(jìn)行驗(yàn)簽。數(shù)字簽名可以讓公鑰持有者驗(yàn)證私鑰持有者的身份并且防止私鑰持有者發(fā)布的內(nèi)容被篡改。常見的非對(duì)稱加密算法有 RSA、EIGamal、D-H、ECC 等。

1.橢圓曲線加密

橢圓曲線加密是一種公鑰加密技術(shù)，它常常與其他公鑰加密算法結(jié)合以得到對(duì)應(yīng)橢圓曲線版本加密算法。通常認(rèn)為，橢圓曲線可以使用更短的密鑰而達(dá)到更高的安全性。橢圓曲線加密是將實(shí)數(shù)域上的橢圓曲線加法群限制在素?cái)?shù)域內(nèi)，基于離散對(duì)數(shù)困難問題構(gòu)造的加密算法。實(shí)數(shù)域上的一個(gè)橢圓曲線通?？赏ㄟ^一個(gè)二元三次方程定義，以常用的Weierstrass橢圓曲線方程為例：

其中，a、b 為可配置參數(shù)。該橢圓曲線方程對(duì)應(yīng)的所有解 (二維平面在該方程對(duì)應(yīng)曲線上所有的點(diǎn))再加上一個(gè)無窮遠(yuǎn)處的點(diǎn)0? (群的單位元，0 點(diǎn))構(gòu)成該橢圓曲線的元素集合。在這些點(diǎn)的集合上，再定義對(duì)應(yīng)的滿足封閉、交換、結(jié)合性質(zhì)的加法計(jì)算和逆元計(jì)算，即可構(gòu)成橢圓曲線加法群。通過修改橢圓曲線不同的參數(shù)a、b，即可得到不同的圓曲線群，如圖1所示。

圖1.不同參數(shù)的橢圓曲線群

對(duì)于橢圓曲線上的兩個(gè)點(diǎn) P、Q，首先定義經(jīng)過兩個(gè)點(diǎn)的直線以及與橢圓曲線的交點(diǎn) R，P與Q在橢圓曲線上的加法結(jié)果為 R 關(guān)于x軸的對(duì)稱點(diǎn)。這個(gè)加法操作定義包含了多種情況，如圖2所示。

圖2.?橢圓曲線四種不同點(diǎn)加法情況

1) P、Q 不是切點(diǎn)且不互為逆元，則有第三個(gè)交點(diǎn) R，此時(shí) P+Q=-R。

2) P或Q為切點(diǎn) (假設(shè)為 0)，此時(shí) P與0連接后的線稱為切線，則定義 R=O，此時(shí)P+Q+Q=0。即加法結(jié)果為 P+O=-Q。

3) 若 P與Q的連線垂直于x軸，此時(shí)連線與橢圓曲線沒有交點(diǎn)，則認(rèn)為交點(diǎn)位于無窮遠(yuǎn)處，即 P+Q=0。

4) 若 P=Q，則此時(shí)認(rèn)為連線為橢圓曲線在 P 點(diǎn)的切線；若該切線與橢圓曲線有交點(diǎn)R，則結(jié)果為-R，否則認(rèn)為交點(diǎn)為無窮遠(yuǎn)處點(diǎn)。

橢圓曲線的加法具體到實(shí)現(xiàn)上，則是先計(jì)算 P與Q連線的斜率

然后根據(jù)韋達(dá)定理計(jì)算交點(diǎn) R的坐標(biāo)：

若P和Q為同一點(diǎn)，其斜率計(jì)算修改為

然后按照上式計(jì)算 R的坐標(biāo)。

橢圓曲線的標(biāo)量乘法 (或稱多倍點(diǎn)運(yùn)算) 可以通過點(diǎn)的多次相加實(shí)現(xiàn)，如nP表示對(duì)n個(gè)P點(diǎn)進(jìn)行加法：

由于橢圓曲線加法群滿足交換律和結(jié)合律，因此可通過 Double-and-Add 算法進(jìn)行優(yōu)化。

在將橢圓曲線加法群應(yīng)用到加密時(shí)，通常需要將橢圓曲線的元素限制在一個(gè)素?cái)?shù)域內(nèi)，于是可基于其標(biāo)量乘法構(gòu)造離散對(duì)數(shù)難題。素?cái)?shù)域的橢圓曲線定義如下：

a=-1，b=3 的一個(gè)素?cái)?shù)域橢圓曲線點(diǎn)分布如圖 3 所示。

圖3

對(duì)于定義在素?cái)?shù)域

上的橢圓曲線的點(diǎn)，其坐標(biāo)的加法和標(biāo)量乘法與實(shí)數(shù)域計(jì)算規(guī)則一樣，但所有的計(jì)算均需要在素?cái)?shù)域E進(jìn)行。如圖1-3 所示的 P點(diǎn) (16,20)與0點(diǎn)(41.120)的交點(diǎn)為 R (86，46)在素?cái)?shù)域F定義下的 PO 直線上[素?cái)?shù)域下。上的直線定義為所有滿足 ax+by+c三0(modp)的點(diǎn)T，其加法結(jié)果-R(86,81)。同樣,根據(jù)加法計(jì)算規(guī)則,可得到素?cái)?shù)域的標(biāo)量乘法,當(dāng)標(biāo)量 n 很大時(shí),計(jì)算 Q=nP后,將Q點(diǎn)作為公鑰,n 作為私鑰,已知P、Q計(jì)算n 就構(gòu)造了素?cái)?shù)域圓曲線的離散對(duì)數(shù)難題。顯然,若 n 定義在整數(shù)域,則P 的標(biāo)量乘法所遍歷得到的點(diǎn)集構(gòu)成了該橢圓曲線的循環(huán)子群,為保證安全性,需要使 P的標(biāo)量乘法覆蓋的點(diǎn)足夠多(子群的階足夠大),因此需要找到一個(gè)元素階較高的基點(diǎn)。

尋找基點(diǎn)的一個(gè)簡單方法是,首先根據(jù)橢圓曲線的階N確定子群的階n(需要為素?cái)?shù))，計(jì)算余因子h=N/n,然后在橢圓曲線中隨機(jī)選擇點(diǎn) P,計(jì)算 G=hP,若 G=0,則重新選擇點(diǎn),否則點(diǎn) G 即為基點(diǎn)。有多個(gè)主流的被認(rèn)為安全的橢圓曲線及參數(shù)可供選擇,如比特幣簽名中的橢圓曲線secp256k1、curve25519等；在開源框架FATE 中，實(shí)現(xiàn)了扭曲愛德華曲線Edwards25519。

密文計(jì)算

若經(jīng)過加密的密文可進(jìn)行直接計(jì)算,則可將對(duì)應(yīng)的加密技術(shù)稱為同態(tài)加密?！巴瑧B(tài)”的概念來自于抽象代數(shù)中的同態(tài)映射，它是指兩個(gè)代數(shù)系統(tǒng)(群/環(huán)/域)之間能保持運(yùn)算的一類映射,即對(duì)于代數(shù)系統(tǒng)

，若經(jīng)過某個(gè)映射

后，對(duì)

，有F(A·B)= F(A)XF(B)，則可稱F為A到B的同態(tài)映射。

若一個(gè)明文經(jīng)過某種加密算法，其密文進(jìn)行與明文“對(duì)應(yīng)的”密文運(yùn)算后，解密得到與明文運(yùn)算相同的結(jié)果，則可認(rèn)為該加密算法具有同態(tài)性質(zhì)，即可對(duì)明文進(jìn)行同態(tài)加密。同態(tài)加密根據(jù)支持的計(jì)算類型和支持程度，可分為三種類型:半同態(tài)加密 (Partially Homomorphic Encryption，PHE)、近似全同態(tài)加密 (SomeWhat Homomorphic Encryption，SWHE) 和全同態(tài)加密 ( Fully Homomorphic Encryption，F(xiàn)HE)。

(1) 半同態(tài)加密

半同態(tài)加密是指只支持加法或乘法運(yùn)算的加密算法，可分別稱為加法同態(tài)和乘法同態(tài)。常見的半同態(tài)加密算法包括RSA、EIGamal、ECC-EIGamal、Paillier，其中 RSA 和EIGamal具有乘法同態(tài)性質(zhì)，ECC-EIGamal和Paillier具有加法同態(tài)性質(zhì)。Paillier 是常用的一個(gè)半同態(tài)加密算法。它依賴于復(fù)合剩余類的困難問題構(gòu)造，經(jīng)過多年研究，已被證實(shí)非?？煽?，且在多個(gè)開源隱私計(jì)算框架中經(jīng)常被使用。下面將對(duì) Paillier 原理做簡要介紹。

一個(gè) PHE 通常包含以下幾個(gè)功能。

1) KeyGen()：密鑰生成，用于產(chǎn)生加密數(shù)據(jù)的公鑰 pk 和私鑰 sk，以及一些公共參數(shù)( public parameter)。

2) Encrypt()：加密算法，使用pk 對(duì)用戶數(shù)據(jù) m 進(jìn)行加密，得到密文 (ciphertext) c。

3) Decrypt()：解密算法，使用 sk 對(duì)密文c解密，得到數(shù)據(jù)原文 (plaintext) m。

4) Add()：密文同態(tài)加法，輸入兩個(gè)密文 c1、c2，進(jìn)行同態(tài)加運(yùn)算。

5) ScalaMul()：密文同態(tài)標(biāo)量乘法，輸入 c 和一個(gè)標(biāo)量 s，計(jì)算c與標(biāo)量乘的結(jié)果。

對(duì)于 Paillier 加密，其各個(gè)算法功能的實(shí)現(xiàn)如下。

1) KeyGen()。隨機(jī)生成兩個(gè)獨(dú)立的大素?cái)?shù)p 和q，滿足gcd(pg,(p-1)(q-1))=1，且p、q長度相等。計(jì)算n=pq，A=lcm(p-1,q-1)，

=(n)為n 的卡邁克爾函數(shù)，Icm 為最小公倍數(shù)。隨機(jī)選擇，不妨設(shè) g=n+1，并定義L函數(shù)，。返回公鑰 (n,g)和私鑰 (,)。

2)。輸入明文消息m，隨機(jī)選擇，計(jì)算密文。

3)。輸入密文消息c，計(jì)算。

解密的正確性可根據(jù)卡邁克爾函數(shù)性質(zhì)，及二項(xiàng)式定理(1+x)”=1+推導(dǎo)驗(yàn)證。

由可得

。

4)。輸入密文，其密文加法被定義為正確性可驗(yàn)證：。

5)。輸入密文c 和標(biāo)量s，其標(biāo)量乘法被定義為

正確性可驗(yàn)證：。

(2) 近似全同態(tài)加密

近似全同態(tài)加密 (有限級(jí)數(shù)同態(tài)加密)是同時(shí)支持密文加法和密文乘法的加密算法，但它往往僅能支持有限級(jí)數(shù)的密文乘法。近似全同態(tài)加密是大部分全同態(tài)加密的基礎(chǔ)。全同態(tài)加密算法往往會(huì)在近似全同態(tài)加密方案上加人一個(gè)自舉(Bootstraping)或漸進(jìn)式的模數(shù)切換 (Modulus Switching)。全同態(tài)加密算法起源于 2009年 Gentry 提出的方案，通過對(duì)近似全同態(tài)加密算法加入自舉操作，控制運(yùn)算過程中噪聲的增長。自舉方法是指通過將解密過程本身轉(zhuǎn)化為同態(tài)運(yùn)算電路，并生成新的公私鑰對(duì)，對(duì)原私鑰和含有噪聲的原密文進(jìn)行加密，然后用原私鑰的密文對(duì)原密文的密文進(jìn)行解密的同態(tài)運(yùn)算，其可得到不含噪聲的新密文。

(3) 全同態(tài)加密

Gentrv于2009年提出一種基于電路模型的全同態(tài)加密算法，它僅支持對(duì)每個(gè)比特進(jìn)行加法和乘法同態(tài)運(yùn)算(布爾運(yùn)算)。目前主流的同態(tài)加密方案基于格上 LWE Learning With Errors)/Ring-LWE (RLWE) 問題構(gòu)造，LWE/RLWE 都可以規(guī)約到基于格上的困難問題【如最短線性無關(guān)向量 (SIVP) 問題】，然而LWE 問題中涉及矩陣與向量的乘法，計(jì)算較復(fù)雜，而基于 RLWE 的問題僅涉及環(huán)上多項(xiàng)式的運(yùn)算，具有更小的計(jì)算開銷。因此，雖然主流的同態(tài)加密算法 (如BGV、BFV 等)都可同時(shí)基于LWE/RLWE 構(gòu)造，但在實(shí)現(xiàn)上會(huì)以RLWE 為主。另外，Cheon 等人在 2017 年提出了一種浮點(diǎn)數(shù)的全同態(tài)加密方案--CKKS，該方案支持針對(duì)實(shí)數(shù)或復(fù)數(shù)的浮點(diǎn)數(shù)加法和乘法同態(tài)運(yùn)算，得到的計(jì)算結(jié)果為近似值，它通常適用于機(jī)器學(xué)習(xí)模型訓(xùn)練等不需要精確結(jié)果的場景。

3.偽隨機(jī)函數(shù)

隱私計(jì)算中另一個(gè)被廣泛使用的密碼學(xué)原語為偽隨機(jī)函數(shù) (Pseudo Random Function)。一個(gè)偽隨機(jī)函數(shù)是一個(gè)形如 y= F(k,x)的確定性函數(shù)，其中是密鑰空間K 的一個(gè)密鑰，x 是輸人空間X的一個(gè)元素，y 是輸出空間Y上的一個(gè)元素。其安全性要求:給定一個(gè)隨機(jī)密鑰k，函數(shù) F(k，·)應(yīng)該看上去像一個(gè)定義在X到Y(jié)的隨機(jī)函數(shù)。Oded 等人證明了通過偽隨機(jī)數(shù)生成器可構(gòu)造偽隨機(jī)函數(shù)。

三、機(jī)器學(xué)習(xí)

從隱私計(jì)算根據(jù)其保護(hù)的計(jì)算過程來看，有一大類是隱私保護(hù)的機(jī)器學(xué)習(xí)。機(jī)器學(xué)習(xí)根據(jù)其學(xué)習(xí)方式通?？煞譃槿N類型:監(jiān)督學(xué)習(xí)、半監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)。

監(jiān)督學(xué)習(xí)是在給定帶標(biāo)簽/標(biāo)記訓(xùn)練數(shù)據(jù)下的學(xué)習(xí)方式，其目標(biāo)是在給定的訓(xùn)練數(shù)據(jù)集中學(xué)習(xí)到一個(gè)模型(函數(shù))，當(dāng)新數(shù)據(jù)出現(xiàn)時(shí)，可根據(jù)這個(gè)函數(shù)給出預(yù)測結(jié)果。常見的監(jiān)穆學(xué)習(xí)算法包括樸素貝葉斯、邏輯回歸、線性回歸、決策樹、集成樹、支持向量機(jī)、(深度)神經(jīng)網(wǎng)絡(luò)等。然而，很多實(shí)際問題中，因?yàn)閷?duì)數(shù)據(jù)進(jìn)行標(biāo)記的代價(jià)有時(shí)很高，所以通常只能拿到少量標(biāo)簽數(shù)據(jù)和大量的無標(biāo)簽數(shù)據(jù)。半監(jiān)督學(xué)習(xí)是在給定較少帶標(biāo)簽訓(xùn)練數(shù)據(jù)和大量無標(biāo)簽數(shù)據(jù)下的學(xué)習(xí)方式，它使用無標(biāo)簽數(shù)據(jù)來獲得數(shù)據(jù)結(jié)構(gòu)更多的信息，其目標(biāo)是要得到比單獨(dú)使用帶標(biāo)簽數(shù)據(jù)訓(xùn)練的監(jiān)督學(xué)習(xí)技術(shù)更好的結(jié)果。常見的半監(jiān)督學(xué)習(xí)策略包括 selftraining、PU Learning、Co-training 等。無監(jiān)督學(xué)習(xí)中的常見任務(wù)有聚類、表示學(xué)習(xí)和密度估計(jì)。這些任務(wù)都是希望在無明確提供的標(biāo)簽的情況下了解數(shù)據(jù)的內(nèi)在結(jié)構(gòu)。常見的無監(jiān)督學(xué)習(xí)算法包括 k-means 聚類、主成分分析和自動(dòng)編碼器等。由于沒有提供標(biāo)簽，因此在多數(shù)無監(jiān)督學(xué)習(xí)算法中沒有用于比較模型性能的具體方法。

在實(shí)際應(yīng)用中，監(jiān)督學(xué)習(xí)應(yīng)用范圍比較廣，因此本文以監(jiān)督學(xué)習(xí)為主對(duì)一些基本概念進(jìn)行介紹。

1.損失函數(shù)

監(jiān)督學(xué)習(xí)通常給出帶標(biāo)簽訓(xùn)練數(shù)據(jù) (x,y)，x作為輸入數(shù)據(jù)，通常由一個(gè)向量表示，向量的每個(gè)元素稱為特征；y為模型需要學(xué)習(xí)的輸出數(shù)據(jù)，通常也稱為標(biāo)簽。訓(xùn)練數(shù)據(jù)一般由多條 (x,y) 數(shù)據(jù)組成，每條 (x,y) 數(shù)據(jù)被稱為一個(gè)樣本，所有樣本的輸入組成輸入空間/特征空間X，所有輸出標(biāo)簽組成輸出空間 Y。根據(jù)輸出空間的分布，可將監(jiān)督學(xué)習(xí)劃分為分類模型和回歸模型，分類模型通常根據(jù)輸出標(biāo)簽 y的基數(shù)分為二分類模型和多分類模型.

因此，監(jiān)督學(xué)習(xí)的目標(biāo)是通過一個(gè)學(xué)習(xí)算法，在訓(xùn)練集 X×Y 上找到一個(gè)模型f(x,w)使模型

得到的預(yù)測值與真實(shí)輸出值一致。然而，模型的預(yù)測值可能與y一致或不一致。因此，需要使用一個(gè)損失函數(shù)來量化模型預(yù)測值與真實(shí)值y的差異(一般稱

-y為殘差)。損失函數(shù) L(y,f(x,w))是一個(gè)非負(fù)實(shí)值函數(shù)，需要根據(jù)監(jiān)督學(xué)習(xí)的任務(wù)類型進(jìn)行不同定義。常用的損失函數(shù)包括 0-1 損失函數(shù)、平方損失函數(shù)、對(duì)數(shù)損失函數(shù)、交叉損失函數(shù)、合頁損失函數(shù)等。然而，前面的損失函數(shù)僅僅是定義在訓(xùn)練數(shù)據(jù)集上的期望損失，通常被稱為經(jīng)驗(yàn)損失或經(jīng)驗(yàn)風(fēng)險(xiǎn)，只有當(dāng)樣本數(shù)量趨于無窮大時(shí)，才可認(rèn)為其損失是期望的損失 (通常也被稱為期望風(fēng)險(xiǎn))。當(dāng)模型參數(shù)復(fù)雜而訓(xùn)練數(shù)據(jù)較少時(shí)，可能會(huì)存在模型在訓(xùn)練數(shù)據(jù)上預(yù)測正確性很高，而在訓(xùn)練集外的未知數(shù)據(jù)集上預(yù)測正確性較低的現(xiàn)象，這種現(xiàn)象被稱為“過擬合”。為了防止“過擬合”現(xiàn)象，通常會(huì)在經(jīng)驗(yàn)損失基礎(chǔ)上加入?yún)?shù)正則化項(xiàng)(正則化損失)，限制模型參數(shù)對(duì)的復(fù)雜度，這個(gè)新的損失函數(shù)可稱為結(jié)構(gòu)化損失函數(shù)(或結(jié)構(gòu)風(fēng)險(xiǎn)函數(shù))。

2.梯度下降

在定義了損失函數(shù)之后，便可以通過優(yōu)化方法尋找模型參數(shù)，使損失值不斷下降，損失值越低，則可認(rèn)為模型預(yù)測值與真實(shí)輸出值y之間的差異越小。一種常見的參數(shù)優(yōu)化方法是梯度下降法，對(duì)于每次訓(xùn)練迭代，先計(jì)算損失函數(shù)對(duì)參數(shù)的梯度 (一階連續(xù)偏導(dǎo)數(shù))，用梯度的反方向 (梯度的負(fù)數(shù)) 乘以一定步長 lr(學(xué)習(xí)速率)，對(duì)參數(shù)進(jìn)行更新：

步長lr 可以固定為一個(gè)比率，也可以通過各類優(yōu)化器計(jì)算得到一個(gè)自適應(yīng)的比率。梯度下降按照訓(xùn)練樣本的選取策略可分為隨機(jī)梯度下降 (每次隨機(jī)選取一個(gè)樣本)、批量梯度下降(每次使用所有樣本)和小批量 (mini batch) 梯度下降(每次按順序選取一批樣本)。

在聯(lián)邦學(xué)習(xí)中，有標(biāo)簽一方可直接計(jì)算梯度，在無標(biāo)簽一方，梯度必須在密態(tài)方式下計(jì)算，可通過有標(biāo)簽一方對(duì)殘差進(jìn)行同態(tài)加密并發(fā)送給無標(biāo)簽一方計(jì)算，也可以通過 MPC 方式聯(lián)合計(jì)算。

3.深度學(xué)習(xí)

深度學(xué)習(xí)是近年來非常流行的一種機(jī)器學(xué)習(xí)方法。與傳統(tǒng)機(jī)器學(xué)習(xí)相比，深度學(xué)習(xí)主要采用深度神經(jīng)網(wǎng)絡(luò)作為特定模型結(jié)構(gòu)，通過對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的層結(jié)構(gòu)、層連接方式、連接權(quán)重采樣、單元結(jié)構(gòu)、激活函數(shù)、學(xué)習(xí)策略、正則化等多種方式優(yōu)化，實(shí)現(xiàn)遠(yuǎn)超傳統(tǒng)機(jī)器學(xué)習(xí)的模型性能。多種經(jīng)典的深度學(xué)習(xí)技術(shù)被廣泛采用，包括卷積神經(jīng)網(wǎng)絡(luò) (Convolutional Neural Networks，CNN)、圖卷積神經(jīng)網(wǎng)絡(luò) (GCN)、Dropout、Poling、長短期記憶網(wǎng)絡(luò) (LongShort-Term Memory，LSTM)、RNN、GRU、殘差網(wǎng)絡(luò)、DQN、DDQN、Batch Normalization.Layer Normalization、 Attention 、Transformer 等。

由于深度學(xué)習(xí)模型復(fù)雜、參數(shù)量大，而隱私計(jì)算中很多計(jì)算涉及密文計(jì)算，因此，在實(shí)際應(yīng)用中，通常會(huì)使用網(wǎng)絡(luò)層級(jí)更少、結(jié)構(gòu)更為簡單的神經(jīng)網(wǎng)絡(luò)，如 CNN、Dropout、Pooling、Batch Normalization、Layer Normalization 等。隱私計(jì)算中有多種實(shí)現(xiàn)方案，如在聯(lián)邦學(xué)習(xí)中，通常首先會(huì)在參與方本地進(jìn)行神經(jīng)網(wǎng)絡(luò)的前向計(jì)算，然后在協(xié)調(diào)節(jié)點(diǎn)上進(jìn)行梯度計(jì)算，最后在各本地進(jìn)行網(wǎng)絡(luò)的反向傳播。MPC 實(shí)現(xiàn)的深度神經(jīng)網(wǎng)絡(luò)則通常將模型參數(shù)和數(shù)據(jù)進(jìn)行秘密共享，進(jìn)行全密態(tài)的訓(xùn)練或預(yù)測?；谌瑧B(tài)加密的方案 CKKS 可直接在全密態(tài)下(數(shù)據(jù)加密或模型加密) 進(jìn)行網(wǎng)絡(luò)的訓(xùn)練和預(yù)測，且可以滿足模型和數(shù)據(jù)的完全分離。以上內(nèi)容節(jié)選自《隱私計(jì)算：開源架構(gòu)實(shí)戰(zhàn)》

三、圖書推薦

隱私計(jì)算是指在保護(hù)數(shù)據(jù)本身不對(duì)外泄露的前提下，實(shí)現(xiàn)數(shù)據(jù)共享、分析、計(jì)算、建模的技術(shù)集合，以達(dá)到對(duì)數(shù)據(jù)“可用、不可見”的目的。隱私計(jì)算涉及多個(gè)學(xué)科和技術(shù)體系，從實(shí)現(xiàn)所使用的技術(shù)上看，包含三個(gè)主要技術(shù)路線：聯(lián)邦學(xué)習(xí)、安全多方計(jì)算和可信執(zhí)行環(huán)境。

本書主要介紹聯(lián)邦學(xué)習(xí)和安全多方計(jì)算兩種技術(shù)路線，在講解理論知識(shí)的基礎(chǔ)上結(jié)合開源架構(gòu)進(jìn)行代碼分析、安裝和運(yùn)行。第1章介紹隱私計(jì)算所需基礎(chǔ)理論知識(shí)；第2章根據(jù)聯(lián)邦學(xué)習(xí)建模流程結(jié)合開源框架FATE進(jìn)行介紹；第3～5章介紹安全多方計(jì)算，包括不經(jīng)意傳輸、秘密共享和混淆電路；第6章介紹具有特定功能的隱私計(jì)算協(xié)議，包括隱私集合求交和隱私信息檢索；第7章介紹隱私保護(hù)的安全聯(lián)合分析，分別介紹了SMCQL和Conclave兩個(gè)框架，主要涉及聯(lián)合分析過程的SQL計(jì)劃優(yōu)化和明密文混合運(yùn)行。本書提供關(guān)聯(lián)的開源架構(gòu)源代碼，獲取方式見封底。

本書適合隱私計(jì)算入門從業(yè)者，以及需要快速搭建隱私計(jì)算產(chǎn)品的研發(fā)人員閱讀學(xué)習(xí)。

作者介紹

內(nèi)容結(jié)構(gòu)及配套資源

撰? 稿? 人：計(jì)旭，責(zé)任編輯：張淑謙，審? 核? 人：曹新宇