IEEE x ATEC

IEEE x ATEC科技思享會(huì)是由專(zhuān)業(yè)技術(shù)學(xué)會(huì)IEEE與前沿科技探索社區(qū)ATEC聯(lián)合主辦的技術(shù)沙龍。邀請(qǐng)行業(yè)專(zhuān)家學(xué)者分享前沿探索和技術(shù)實(shí)踐，助力數(shù)字化發(fā)展。

在萬(wàn)物互聯(lián)的大數(shù)據(jù)時(shí)代，數(shù)據(jù)鏈接了我們生活的方方面面。一方面，大數(shù)據(jù)極大便利了我們的工作與生活；另一方面，數(shù)據(jù)的海量化也增加了諸多隱私信息泄露的風(fēng)險(xiǎn)與挑戰(zhàn)。本期科技思享會(huì)邀請(qǐng)到了四位重磅嘉賓，共同圍繞“隱私保護(hù)的前沿技術(shù)及應(yīng)用”這個(gè)主題，分別從機(jī)器學(xué)習(xí)算法、通訊協(xié)議、APP及操作系統(tǒng)等不同層面，就隱私安全風(fēng)險(xiǎn)及技術(shù)創(chuàng)新應(yīng)用展開(kāi)討論。

以下是浙江大學(xué)張秉晟研究員的演講，《RAM模型下的多方隱私函數(shù)評(píng)估》。

 演講嘉賓 | 張秉晟

浙江大學(xué)百人計(jì)劃研究員、國(guó)家級(jí)青年人才項(xiàng)目獲得者、科技部重大科研項(xiàng)目首席科學(xué)家

《RAM模型下的多方隱私函數(shù)評(píng)估》

大家好，我是浙江大學(xué)的張秉晟。今天跟大家分享一個(gè)我們組和螞蟻摩斯最新的合作研究成果《RAM模型下的多方隱私函數(shù)評(píng)估》。什么是RAM模型，什么是隱私函數(shù)評(píng)估？在這個(gè)Talk中我會(huì)慢慢跟大家介紹。

目的與場(chǎng)景

首先是目的和場(chǎng)景。隱私泄露的問(wèn)題日益嚴(yán)重，也得到了越來(lái)越多人的關(guān)注，包括國(guó)家、政府和各級(jí)的地方機(jī)關(guān)。我國(guó)的大部分互聯(lián)網(wǎng)公司都或多或少有一些需要整改的地方，也收到過(guò)國(guó)家的整改條令、約束等。上圖中列舉了一些隱私泄露的相關(guān)案例，其他案例在此不再一一列舉。

最近，我們國(guó)家對(duì)數(shù)據(jù)安全和隱私保護(hù)的相關(guān)立法加速落地。從2012年開(kāi)始到現(xiàn)在，我們國(guó)家相繼出臺(tái)了網(wǎng)絡(luò)安全法、個(gè)人信息保護(hù)法、數(shù)據(jù)安全法等一系列法律法規(guī)。目前這些法律法規(guī)還只是比較上層的指導(dǎo)意見(jiàn)。例如在個(gè)人安全法里面提到，含有個(gè)人敏感信息的數(shù)據(jù)在通過(guò)處理不可以逆推、不可以反推出原始數(shù)據(jù)的情況下，是不受該法保護(hù)的。即它從側(cè)面提供了一個(gè)我們對(duì)隱私計(jì)算、對(duì)數(shù)據(jù)互流互通的一個(gè)約束，數(shù)據(jù)要經(jīng)過(guò)處理是不可以逆推成原始數(shù)據(jù)的。這些法律法規(guī)目前還比較上層，具體的評(píng)判標(biāo)準(zhǔn)還在制定當(dāng)中。但是我們相信在不久的將來(lái)，我們這個(gè)評(píng)判標(biāo)準(zhǔn)也會(huì)越來(lái)越明確，至少現(xiàn)在去標(biāo)識(shí)化已經(jīng)有相關(guān)的標(biāo)準(zhǔn)。

去年Gartner給出了一個(gè)預(yù)測(cè)，根據(jù)預(yù)測(cè)報(bào)告：在2023年底，全球有75%的人口的個(gè)人數(shù)據(jù)將受到隱私法律的保護(hù)。到2023年底之前，全球有超過(guò)80%的公司將面臨至少一項(xiàng)以隱私為重點(diǎn)的數(shù)據(jù)保護(hù)法規(guī)。到2024年，全球隱私驅(qū)動(dòng)的數(shù)據(jù)保護(hù)和合規(guī)技術(shù)將突破150億美元。到2025年，有60%的大型組織和企業(yè)，他們會(huì)通過(guò)至少一種或者多種隱私增強(qiáng)技術(shù)來(lái)實(shí)現(xiàn)數(shù)據(jù)的分析、云計(jì)算、建模制、數(shù)據(jù)的智能化處理等等。

隱私保護(hù)和數(shù)據(jù)安全的技術(shù)有很多，我們這個(gè)工作主要是屬于安全多方計(jì)算的范疇。那什么是安全多方計(jì)算呢？它的英文叫Secure Multiparty Computation，它是密碼學(xué)的一個(gè)重要研究分支。如果你去網(wǎng)上搜索什么是安全多方計(jì)算，那么你一般會(huì)找到以下這句定義：為解決一組互不信任的參與方之間在保護(hù)隱私信息以及沒(méi)有可信第三方的前提下協(xié)同計(jì)算問(wèn)題而提出的密碼協(xié)議與理論框架。

如果你是學(xué)習(xí)密碼學(xué)或者密碼協(xié)議或者隱私計(jì)算的圈內(nèi)人士，那我們有相關(guān)的狹義定義。在狹義定義中，安全多方計(jì)算一般可以分為兩種主要的實(shí)現(xiàn)形式：一種是姚氏混淆電路，它主要是用于兩方計(jì)算，當(dāng)然也可以用于多方計(jì)算。姚氏混淆電路比較好的特點(diǎn)是它對(duì)布爾電路的支持非常好，這也是安全多方計(jì)算。姚期智教授是在1982年提出安全多方計(jì)算時(shí)提出的設(shè)想。現(xiàn)在的姚氏混淆電路經(jīng)過(guò)40年的優(yōu)化和改良，效率已經(jīng)非常非常高了。第二種是針對(duì)布爾電路或者代數(shù)電路，我們是以秘密分享的形式來(lái)實(shí)現(xiàn)兩方或者多方的協(xié)議。這種實(shí)現(xiàn)方式有什么好處？它的通信量會(huì)比姚氏混淆電路整體通信量小，但是它的通信輪次會(huì)比較多，比較適用于帶寬比較小、但是延時(shí)比較少的應(yīng)用場(chǎng)景。如果延時(shí)比較高的話(huà)還是建議用姚氏混淆電路，當(dāng)然秘密分享對(duì)代數(shù)電路的支持肯定是好于姚氏混淆電路。

當(dāng)然現(xiàn)在也有一些混合的協(xié)議，即你在同一個(gè)函數(shù)中或者同一個(gè)計(jì)算任務(wù)中，既要解決布爾電路，又要解決代數(shù)電路如何在它們之間進(jìn)行轉(zhuǎn)換，比如說(shuō)ABY系列。廣義來(lái)說(shuō)，就我個(gè)人理解而言，安全多方計(jì)算可以包括密碼學(xué)的一些原語(yǔ)，比如說(shuō)全同態(tài)加密。

有人問(wèn)，全同態(tài)加密和安全多方計(jì)算是什么關(guān)系？它們是不是兩個(gè)不同的技術(shù)？

在我看來(lái)它們是不對(duì)等的一個(gè)比較。因?yàn)槿瑧B(tài)加密只是一個(gè)加密的原語(yǔ)，這就相當(dāng)于在安全多方計(jì)算里我可不可以應(yīng)用例如AES加密，你說(shuō)可以。在我看來(lái)，AES加密和全同態(tài)加密都是一種加密算法，而安全多方計(jì)算是一種協(xié)議、是一個(gè)更高維度的東西。安全多方計(jì)算的協(xié)議如果使用了比如說(shuō)簽名算法、加密算法，這個(gè)協(xié)議仍然是安全多方計(jì)算協(xié)議。所以在我個(gè)人的理解里面，安全多方計(jì)算協(xié)議即使使用了同態(tài)加密、半同態(tài)、全同態(tài)，它仍然是安全多方計(jì)算協(xié)議。在業(yè)界，因?yàn)橐恍┮笏鸦诳尚庞布陌踩喾接?jì)算叫做Confidential Computing（機(jī)密計(jì)算），又把聯(lián)邦學(xué)習(xí)從安全多方計(jì)算中分離出來(lái)。其實(shí)聯(lián)邦學(xué)習(xí)提出的時(shí)候，它并沒(méi)有安全的定義。在我看來(lái)，聯(lián)邦學(xué)習(xí)和安全多方計(jì)算其實(shí)也是一個(gè)不可比較的概念。因?yàn)槁?lián)邦學(xué)習(xí)里面是可以應(yīng)用安全多方計(jì)算技術(shù)去做一些隱私保護(hù)的事情。

我們研究這個(gè)成果的研究目的是什么呢？

我們主要是為了解決兩方或者多方在比如說(shuō)云計(jì)算的時(shí)候，要保護(hù)計(jì)算任務(wù)、要保護(hù)特定的算法。什么意思呢？傳統(tǒng)的安全多方計(jì)算指你在計(jì)算的時(shí)候所有的安全多方計(jì)算參與方都會(huì)知道你要計(jì)算的是什么任務(wù)，也就是說(shuō)我的算法是公開(kāi)給所有的安全多方計(jì)算參與方。而我們要保護(hù)的只是數(shù)據(jù)、只是輸入，只是這個(gè)計(jì)算的輸入。但是對(duì)于一些應(yīng)用場(chǎng)景，它的算法是非常重要的，比如別人的知識(shí)產(chǎn)權(quán)，比如DNA精準(zhǔn)、靶向制藥。例如我有一個(gè)算法，我的算法需要應(yīng)用到你的DNA產(chǎn)生藥的配方，但是我的算法不能公開(kāi)給你，雖然你的DNA也是隱私保護(hù)的，但我和你做兩方計(jì)算的時(shí)候你不可以得到我的算法。也就是說(shuō)我有需求是保護(hù)算法，你有需求是保護(hù)輸入。這個(gè)就牽扯到一個(gè)分支，這個(gè)分支一般我們?cè)贑ommunity里面會(huì)把它稱(chēng)為Private Function Evaluation，我把它翻譯成隱私函數(shù)評(píng)估，也就是說(shuō)我們?cè)诒Ｗo(hù)輸入的前提下，還要保護(hù)我們所計(jì)算的函數(shù)、我們要計(jì)算的任務(wù)。我們不可以讓計(jì)算方知道在計(jì)算什么任務(wù)，即保護(hù)你的計(jì)算算法的IP。

顯然這是一個(gè)安全多方計(jì)算的一個(gè)分支，也就是說(shuō)它仍然是屬于安全多方計(jì)算的領(lǐng)域。據(jù)我所知，目前傳統(tǒng)的安全多方計(jì)算，所有商用的安全多方計(jì)算都是基于電路格式。Sort格式什么意思？也就是說(shuō)你只能順序執(zhí)行，你在安全多方計(jì)算里面是不可以支持RAM計(jì)算模型的。什么叫RAM計(jì)算？RAM就是Random Access Machine。我們現(xiàn)在的常規(guī)電腦是馮諾依曼結(jié)構(gòu)，在內(nèi)存里可以隨機(jī)訪問(wèn)或跳轉(zhuǎn)Random Access。比如說(shuō)你做一個(gè)Binary Search，二分搜索，你不需要scan整個(gè)Memory，你可以跳到你指定的位置去做讀寫(xiě)、做比較，然后再做下一步操作。但是因?yàn)橐恍┘夹g(shù)的限制，在安全多方計(jì)算里面我們現(xiàn)在不能做這種類(lèi)似操作，我們現(xiàn)在只能順序執(zhí)行。而這種順序執(zhí)行會(huì)極大程度的限制我們安全多方計(jì)算可以使用的場(chǎng)景，比如說(shuō)有一些我們需要跳轉(zhuǎn)或者跳轉(zhuǎn)比較多的算法就沒(méi)辦法高效的用安全多方計(jì)算來(lái)實(shí)現(xiàn)。

我們這次想要做的一個(gè)工作是在RAM模型下去實(shí)現(xiàn)一個(gè)Private Function Evaluation。也就是說(shuō)我們這個(gè)安全多方計(jì)算系統(tǒng)再也不用被編譯成電路就能支持RAM的計(jì)算結(jié)構(gòu)。如果你有一個(gè)死循環(huán)，你有一個(gè)While Loop，甚至你的While Loop里面的Condition是一個(gè)不確定的Condition。比如說(shuō)一個(gè)死循環(huán)里面，你有一個(gè)基于私密數(shù)據(jù)的隱私保護(hù)數(shù)據(jù)的條件，那么我們這個(gè)模型也能夠去支持，并且我們這個(gè)模型會(huì)保護(hù)你的算法。我們的做法大致講來(lái)是把一些高級(jí)語(yǔ)言(比如C++語(yǔ)言或者Java等)用編譯器(比如用LLVM的編譯器)編譯成TinyRAM的指令集，為什么是TinyRAM呢？因?yàn)槲覀冃枰粋€(gè)精簡(jiǎn)指令集，如果指令集太復(fù)雜了我們整個(gè)系統(tǒng)的開(kāi)銷(xiāo)就會(huì)非常的大。所以我們就選了一個(gè)精簡(jiǎn)指令集，TinyRAM。當(dāng)然RISC-V也是可以的，我們對(duì)程序和輸入都進(jìn)行隱私保護(hù)。具體來(lái)說(shuō)我們都進(jìn)行秘密分享，我后面會(huì)一一和大家解釋具體操作。

我們?cè)诔绦蛎孛芊窒砗蛿?shù)據(jù)秘密分享的前提下進(jìn)行安全的執(zhí)行，我們可以密態(tài)的執(zhí)行。

MPC分布式ORAM

先講一下我們構(gòu)建的一個(gè)前提工作，也就是我們要構(gòu)建一個(gè)分布式的ORAM。

什么是分布式的ORAM呢？

傳統(tǒng)的ORAM是講你有一個(gè)服務(wù)器或者有多個(gè)服務(wù)器，然后有一個(gè)Client，這個(gè)Client在服務(wù)器上面進(jìn)行讀寫(xiě)，它不能讓服務(wù)器知道你讀寫(xiě)的是哪一個(gè)位置。分布式ORAM指的是我已經(jīng)不存在這樣的一個(gè)Client，我在安全多方計(jì)算時(shí)我要讀寫(xiě)哪一格的位置，其實(shí)我要讀寫(xiě)的這個(gè)數(shù)據(jù)也是隱私保護(hù)的，比如說(shuō)它是以秘密分享的形式去保護(hù)的，然后在服務(wù)器上面進(jìn)行讀寫(xiě)，它也是一個(gè)分布式的結(jié)構(gòu)。具體我們采用了4個(gè)服務(wù)器架構(gòu)。如果你要只讀的話(huà)，我們也可以做出3PC的格式。這個(gè)2PC的格式后面我們會(huì)講，這是一個(gè)經(jīng)典的PIR，但它不是標(biāo)準(zhǔn)的ORAM，它只是一個(gè)Private Information Retrieval的實(shí)現(xiàn)形式，主要是基于DPF（Distributed Point Function），也就是FSS（Functioning Secret Sharing）。

我們構(gòu)建的這個(gè)分布式有幾個(gè)特點(diǎn)：第一個(gè)特點(diǎn)，它可以進(jìn)行任意次的讀和寫(xiě)，而且讀和寫(xiě)之間的轉(zhuǎn)換是不需要Refresh、是不需要Eviction的。即我們看見(jiàn)的一些常見(jiàn)操作，可能它的讀會(huì)很快，但是讀轉(zhuǎn)到寫(xiě)的過(guò)程中需要非常多的時(shí)間或者它的讀寫(xiě)都比較快，但是它經(jīng)過(guò)若干次的讀寫(xiě)突然要進(jìn)行一次Refresh或者進(jìn)行一次Image，這就極大程度的限制了這些ORAM在我們這個(gè)場(chǎng)景中的使用。具體來(lái)說(shuō)，我們的O-READ，它的通信量是12log2(n) bits，這個(gè)N就是你這個(gè)Memory大概有多少M(fèi)emory的size。然后你在Memory里面取一個(gè)數(shù)，不讓這個(gè)服務(wù)器知道你取哪一個(gè)數(shù)。我們需要的通信量是12倍的log2(n)，然后你想oblivious去改寫(xiě)那個(gè)Memory，就是你在一個(gè)N個(gè)size的Memory里面，你在某一條里面想去寫(xiě)入一個(gè)數(shù)。比如說(shuō)在i條里面寫(xiě)入一個(gè)數(shù)，在我們這里All Right的通信量是24倍的log2(n)加12t bits，T其實(shí)就是你要寫(xiě)入的這個(gè)數(shù)據(jù)的長(zhǎng)度，具體的操作它分Open δ、Cyclic- shift、Scale、Re-randomize，稍后我會(huì)一一介紹。

我先簡(jiǎn)單介紹一下DPF。DPF是Distributed Point Function，它最經(jīng)典的構(gòu)造是兩方的DPF，就是有個(gè)Generate，它會(huì)Generate出兩個(gè)K，這個(gè)K一方給左邊，一方給右邊，兩個(gè)服務(wù)器S1和S2。這兩個(gè)服務(wù)器分別針對(duì)這個(gè)K做Evaluate，把做出來(lái)的最后一行的從β0到β3兩個(gè)東西全加起來(lái)，它其實(shí)是一個(gè)Unit vector。什么叫Unit vector？它只有一位是non-zero，none-zero位通常在這個(gè)應(yīng)用場(chǎng)景里面會(huì)把它取為1，其他每一位都是0，也就是說(shuō)這其實(shí)是一個(gè)Compression的過(guò)程，把一個(gè)Unit vector給compress成一個(gè)log2(n) Size的T。因時(shí)間問(wèn)題，具體的做法我在此就不一一講了，這是一個(gè)比較經(jīng)典的技術(shù)，它是用一個(gè)Tree的Structure，在每一層會(huì)有一個(gè)Correction。也就是說(shuō)它一共有l(wèi)og2(n)層，所以它的K Size會(huì)有l(wèi)og2(n)。這個(gè)在數(shù)據(jù)量比較大的時(shí)候，這個(gè)Tree的Expansion耗時(shí)會(huì)比較長(zhǎng)；但是在數(shù)據(jù)量比較小的時(shí)候，它的操作會(huì)非常的快。

2PC會(huì)有一些缺點(diǎn)，2PC的這個(gè)FSS，傳統(tǒng)的FSS-based PIR：

第一,它不能直接用在我們這里，原因是它需要兩個(gè)Server兩個(gè)服務(wù)器，看見(jiàn)相同的銘文，它其實(shí)是一個(gè)多Server的PIR。服務(wù)器上面的兩個(gè)服務(wù)器要有一模一樣的數(shù)據(jù)，然后你選取這個(gè)數(shù)據(jù)里面一模一樣的PIR的位置，再到自己本地進(jìn)行合成。

第二是這個(gè)Client知道自己要取哪一個(gè)數(shù)。那我們要做這個(gè)分布式的RAM，首先服務(wù)器不能知道這個(gè)數(shù)據(jù)的銘文是什么。其次，服務(wù)器在我們這個(gè)應(yīng)用場(chǎng)景里面甚至也不可以知道它要取哪一個(gè)數(shù)。也就是說(shuō)這兩個(gè)都必須得秘密分享、必須得保護(hù)。

所以我們才會(huì)有一個(gè)4Server的結(jié)構(gòu)。大概的思路是一個(gè)DPF需要兩個(gè)服務(wù)器，有相同的值。在雙服務(wù)器的情況下，這兩個(gè)服務(wù)器必須存明文。但我們?nèi)绻?服務(wù)器，我們其實(shí)可以把這個(gè)數(shù)據(jù)秘密分享成兩份。舉個(gè)例子，這兩份分別由S3和S4去拿同一份秘密分享的Share，S1和S2拿同一份秘密分享的Share，也就是Replicated Share。這兩個(gè)拿同一份、那兩個(gè)拿同一份，這樣我們可以讓S1去生成一個(gè)DPF的K分給S3和S4。S3和S4針對(duì)他們共有的Share可以做剛才的PIR的Evaluation。同理，這個(gè)S1和S2也可以對(duì)他們共有的Share去做PIR的Evaluation。

這里還會(huì)有一個(gè)問(wèn)題，就是我們要取的這個(gè)點(diǎn)也不能透露給別人。要取的這個(gè)點(diǎn)不透露給別人，我們的做法就是在offline階段，可以做一個(gè)DPF針對(duì)一個(gè)隨機(jī)的點(diǎn)。比如說(shuō)i是0到N減一里面任意的一個(gè)數(shù)，等到你實(shí)際上你要存取的那個(gè)值出來(lái)的時(shí)候，你把實(shí)際要存取的值減掉我們之前prepare的時(shí)候隨機(jī)選的那個(gè)值，出來(lái)的那個(gè)數(shù)它其實(shí)就是一個(gè)offset，就是一個(gè)糾正量。我們讓所有的服務(wù)器對(duì)自己的數(shù)據(jù)shift這個(gè)Cyclic的shift，就是去循環(huán)的移動(dòng)偏移量，使得我們做的這個(gè)DPF它就相當(dāng)于是針對(duì)一個(gè)未知的秘密分享的目標(biāo)索引做的DPF。具體我在此就不細(xì)講了。

做完了以后，4方各自會(huì)做一個(gè)linear function，也就是說(shuō)他們不需要通信就可以以秘密分享的形式去得到要取的數(shù)，就比如說(shuō)你要取第i個(gè)數(shù)，那么這個(gè)數(shù)就叫Xi。根據(jù)上圖的公式，你其實(shí)就可以算出這個(gè)Xi是什么，即Xi也是一個(gè)秘密分享的形式存在的。

寫(xiě)怎么寫(xiě)呢？寫(xiě)會(huì)比讀麻煩一點(diǎn)，因?yàn)槿绻蛔x的話(huà)3方也夠，我們這個(gè)算法有3方的版本。如果你要寫(xiě)的話(huà)必須得4方。寫(xiě)，我們其實(shí)是有一個(gè)限制的。我們的寫(xiě)法大概的原理是你需要知道原始的數(shù)據(jù)是什么，你需要知道你寫(xiě)進(jìn)去的這個(gè)數(shù)據(jù)是什么，然后你把寫(xiě)進(jìn)去的這個(gè)數(shù)據(jù)減掉原始的數(shù)據(jù)，你就會(huì)有一個(gè)delta，即有個(gè)修改量、偏移量。你需要把原始的數(shù)據(jù)增加多少量才會(huì)變成你現(xiàn)在想要它變成的這個(gè)數(shù)據(jù)。

因?yàn)樵谖覀兊膽?yīng)用場(chǎng)景里面，你在寫(xiě)之前必定是讀過(guò)那個(gè)格子的值的，所以我們這邊并不會(huì)增加任何額外的開(kāi)銷(xiāo)。即我們這個(gè)假設(shè)你需要知道原始的數(shù)據(jù)是什么？現(xiàn)在修改的數(shù)據(jù)是什么？在我們這個(gè)應(yīng)用場(chǎng)景里面是默認(rèn)的假設(shè)。你會(huì)利用DPF針對(duì)你內(nèi)存里面的每一個(gè)值都進(jìn)行增加一個(gè)偏移量，就是剛才你算出來(lái)的最新的值和以前的值之間的差。當(dāng)然這個(gè)增加的時(shí)候你會(huì)需要乘以一個(gè)Point Function，也就是說(shuō)絕大部分除了一個(gè)位置之外，其他所有位置你增加的偏移量都是0。然后到那個(gè)位置，你增加的偏移量是Δv，在其他部分都是0。增加完、更新完以后，你的輸出結(jié)果還是秘密分享，所以可以繼續(xù)往下走不需要做讀和寫(xiě)的轉(zhuǎn)換。

這個(gè)是我們具體的一個(gè)Benchmark的一個(gè)result。我們針對(duì)一些常見(jiàn)的或者現(xiàn)在state-of-the-art  Distributed ORAM進(jìn)行比較。比如我分別用紅色、黃色和綠色來(lái)表示FLORAM ORAM、SQRT ORAM、CIRCUIT ORAM，我用藍(lán)色來(lái)表示我們自己的。因?yàn)槲覀冏约嚎梢宰鰋ffline和online的分離，所以在圖中我會(huì)畫(huà)兩條線，一條線就是直接online的運(yùn)行時(shí)間，一條線是把online和offline合在一起的運(yùn)行時(shí)間。那么我們的初始化時(shí)間是顯著優(yōu)于任何其他工作，可以說(shuō)我們幾乎不要初始化。在讀的做法里面，我們?cè)诮^大多數(shù)情況下優(yōu)于任何其他的工作，只有當(dāng)這個(gè)數(shù)據(jù)量比較小的時(shí)候，比如說(shuō)數(shù)據(jù)量在2的20次以下的時(shí)候，那么SQRT ORAM會(huì)比我們的快一點(diǎn)點(diǎn)。這只是在某一些場(chǎng)景下面，比如說(shuō)在WAN的場(chǎng)景下面。在寫(xiě)的方面，我們整體的效率和FLORAM ORAM差不了多少。但是因?yàn)槲覀兪强梢园裲nline和offline分開(kāi)的，如果你只看online效率，當(dāng)數(shù)據(jù)庫(kù)比較大的時(shí)候、超過(guò)2的20次的時(shí)候，我們的效率明顯高于所有已知的Distributed ORAM。

MPC模擬CPU

有了這個(gè)非常高效的Distributed ORAM，我們就可以開(kāi)始模擬這個(gè)RAM結(jié)構(gòu)的CPU了。我們模擬的思路是以RAM的形式去管理存儲(chǔ)結(jié)構(gòu),包括所有的存儲(chǔ)結(jié)構(gòu)（我們用的是馮諾依曼結(jié)構(gòu)）、包括整體CPU運(yùn)行時(shí)候的你的指針PC值和一些Flag值、一些寄存器值、一些內(nèi)存的值、一些指令，所有東西都由RAM形式接管。具體來(lái)說(shuō)，我們把普通的代碼，也就是任何一些C語(yǔ)言、高級(jí)語(yǔ)言的代碼，用常規(guī)的編譯器編譯成TinyRAM的指令集。我們會(huì)對(duì)TinyRAM指令集里面的指令進(jìn)行解析。解析完以后，我們會(huì)進(jìn)行隱私保護(hù)的執(zhí)行。我們后面會(huì)講具體是怎么執(zhí)行的。它是密態(tài)執(zhí)行然后密態(tài)選擇、茫然更新，整體、所有的過(guò)程都是Oblivious，都是內(nèi)存保護(hù)的。

具體的指令集大概有25個(gè)左右，前半部分是boolean的指令集，也就是說(shuō)位操作，比如說(shuō)AND、OR、XOR、NOT 、Shift等等。中間是一些加減乘除的常規(guī)操作，后面第三類(lèi)是一些各種各樣的比較，它的Flag會(huì)不一樣，然后會(huì)有一些mov的操作、存取的操作和跳轉(zhuǎn)的指令。

整個(gè) Oblivious Cycle如上圖中的左圖所示，你可以想象成它其實(shí)就是TinyRAM的一個(gè)機(jī)器。這個(gè)機(jī)器的所有狀態(tài)全部都是以秘密分享密態(tài)的形式存儲(chǔ)的,它有Private PC （Program Counter）。你每次來(lái)一個(gè)指令的時(shí)候，指令是從哪里讀的呢？指令我們專(zhuān)門(mén)有內(nèi)存的Memory，我們這個(gè)結(jié)構(gòu)、內(nèi)存的Memory是可以不區(qū)分指令區(qū)和數(shù)據(jù)區(qū)的。也就是說(shuō)如果你的代碼的寫(xiě)作方式是在你代碼的運(yùn)行期間動(dòng)態(tài)產(chǎn)生代碼、新的代碼，我們是可以支持這種形式的。即你不需要把代碼定制在這個(gè)Memory里面，代碼的那部分Memory只讀，數(shù)據(jù)的Memory可以讀寫(xiě)，我們不需要這樣。代碼和數(shù)據(jù)是可以混在一起的，而且你可以動(dòng)態(tài)的去修改你的代碼。有一些病毒就很喜歡并且能做到把自己數(shù)據(jù)區(qū)域的數(shù)據(jù)變成代碼再去運(yùn)行。

我現(xiàn)在不是以程序安全的角度去講這件事情，是以功能性的角度去講這件事情。我們其實(shí)可以滿(mǎn)足這樣的功能需求。我們這個(gè)程序會(huì)從這個(gè)Memory里面、隱私保護(hù)里面取一條指令進(jìn)行解析，解析完畢后，這條指令它會(huì)有操作數(shù)還有它自己做的是什么操作、要用到什么寄存器。比如說(shuō)我們會(huì)用到什么寄存器，寄存器尋址或者立即數(shù)尋址。我們?cè)俚絻?nèi)存里去取相關(guān)的數(shù)，取了相關(guān)的數(shù)以后我們做操作，做完操作以后再進(jìn)行選擇，就是你實(shí)際上的結(jié)果。我們?cè)侔堰@個(gè)結(jié)果存回去，然后根據(jù)你的Flag，我們會(huì)去update這個(gè)Program Counter，就是我們下一條要運(yùn)行哪條指令。我們基本上是根據(jù)這個(gè)Program Counter到這個(gè)Memory里面再去取下一條指令。

具體來(lái)說(shuō)，其實(shí)我們的Oblivious Cycle最大的開(kāi)銷(xiāo)就是我們要支持二十多條的TinyRAM的指令集。我們要做到所有指令集都在同一個(gè)步驟里面完成。大致的思路就是如何防止你知道我做的是哪一條指令，我們就把所有的指令都做了，當(dāng)然不是把每一條指令單獨(dú)做一遍。觀察上圖的左邊部分你會(huì)發(fā)現(xiàn)，我們對(duì)所有的指令集有機(jī)進(jìn)行組合。

也有前人在工作中把若干的指令集用姚式混淆電路編出來(lái)。姚式混淆電路會(huì)比較大，我們這里是用ABY的結(jié)構(gòu)，有一些用姚式混淆電路做，有一些用布爾電路做，有一些是用代數(shù)電路做，所以我們這個(gè)非常高效。對(duì)于所有的指令集，我們可以在三輪內(nèi)完成，包括Compare、一些比較、一些跳轉(zhuǎn)，各種指令在三輪內(nèi)完成。我們有一些指令做的會(huì)比較快，有一些指令做的會(huì)比較慢，有一些指令之間是共享一些中間結(jié)果的，所以我們是有機(jī)的去組合起來(lái)。

我們整體的MPC的Private Function Evaluation的大概運(yùn)行結(jié)構(gòu)如上圖所示：第一輪要Fetch，就讀一條指令。第二輪Decode這個(gè)指令，順便去讀取相關(guān)的操作數(shù)。第三輪是Execute，因?yàn)槲覀冃枰w指令集里面所有的指令，所以Execute其實(shí)需要三輪。第四輪是寫(xiě)，因?yàn)閷?xiě)和Fetch可以同時(shí)執(zhí)行，所以它們?cè)谕粋€(gè)pipeline里面可以重疊?；旧衔覀冞@個(gè)程序就是這樣循環(huán)。

我們?yōu)榱苏故具@個(gè)程序的效率做了一些相關(guān)的RAM結(jié)構(gòu)下比較常見(jiàn)的函數(shù)的Evaluation。比如說(shuō)Binary Search，比如說(shuō)Set Intersection，比如說(shuō)Quick Sort。具體我們把Offline、Fetch、Decode、Evaluation、Write的時(shí)間都分開(kāi)測(cè)了，也包括Total time。注意，因?yàn)槲覀兪潜Ｗo(hù)函數(shù)的，所以相比于不保護(hù)函數(shù)的一些安全多方計(jì)算，時(shí)間確實(shí)慢一點(diǎn)。

有人說(shuō)這個(gè)Binary Search感覺(jué)和Linear Scan差不多。注意，我們是保護(hù)函數(shù)的，你其實(shí)根本不知道我是在做Binary Search。為什么這個(gè)Binary Search會(huì)拿出來(lái)單獨(dú)做呢？因?yàn)槿绻@個(gè)不是RAM模型的結(jié)構(gòu)，要做Binary Search是非常難做的，必須要整個(gè)Memory scan一遍才能夠做到。我們現(xiàn)在基本上你只要做log2(n)步就可以了，也就是說(shuō)你只要做log2(n)次的比較你就能得出這個(gè)結(jié)果。

因?yàn)闀r(shí)間關(guān)系我們今天就分享到這里。如果大家有什么問(wèn)題，歡迎大家Email，我的郵箱是bingsheng@zju.edu.cn，謝謝大家，再見(jiàn)。

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。