丁香五月天婷婷久久婷婷色综合91|国产传媒自偷自拍|久久影院亚洲精品|国产欧美VA天堂国产美女自慰视屏|免费黄色av网站|婷婷丁香五月激情四射|日韩AV一区二区中文字幕在线观看|亚洲欧美日本性爱|日日噜噜噜夜夜噜噜噜|中文Av日韩一区二区

您正在使用IE低版瀏覽器,為了您的雷峰網(wǎng)賬號安全和更好的產(chǎn)品體驗,強烈建議使用更快更安全的瀏覽器
此為臨時鏈接,僅用于文章預覽,將在時失效
業(yè)界 正文
發(fā)私信給嘉嘉
發(fā)送

0

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

本文作者: 嘉嘉 2022-08-09 17:13 專題:IEEE X ATEC科技思享會
導語:什么是RAM模型,什么是隱私函數(shù)評估?

IEEE x ATEC

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

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

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

 演講嘉賓 | 張秉晟

浙江大學百人計劃研究員、國家級青年人才項目獲得者、科技部重大科研項目首席科學家

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

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

目的與場景

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

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

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

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

在我看來它們是不對等的一個比較。因為全同態(tài)加密只是一個加密的原語,這就相當于在安全多方計算里我可不可以應(yīng)用例如AES加密,你說可以。在我看來,AES加密和全同態(tài)加密都是一種加密算法,而安全多方計算是一種協(xié)議、是一個更高維度的東西。安全多方計算的協(xié)議如果使用了比如說簽名算法、加密算法,這個協(xié)議仍然是安全多方計算協(xié)議。所以在我個人的理解里面,安全多方計算協(xié)議即使使用了同態(tài)加密、半同態(tài)、全同態(tài),它仍然是安全多方計算協(xié)議。在業(yè)界,因為一些要求它把基于可信硬件的安全多方計算叫做Confidential Computing(機密計算),又把聯(lián)邦學習從安全多方計算中分離出來。其實聯(lián)邦學習提出的時候,它并沒有安全的定義。在我看來,聯(lián)邦學習和安全多方計算其實也是一個不可比較的概念。因為聯(lián)邦學習里面是可以應(yīng)用安全多方計算技術(shù)去做一些隱私保護的事情。

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

我們研究這個成果的研究目的是什么呢?

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

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

我們在程序秘密分享和數(shù)據(jù)秘密分享的前提下進行安全的執(zhí)行,我們可以密態(tài)的執(zhí)行。

MPC分布式ORAM

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

什么是分布式的ORAM呢?

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

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

2PC會有一些缺點,2PC的這個FSS,傳統(tǒng)的FSS-based PIR:

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

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

因為在我們的應(yīng)用場景里面,你在寫之前必定是讀過那個格子的值的,所以我們這邊并不會增加任何額外的開銷。即我們這個假設(shè)你需要知道原始的數(shù)據(jù)是什么?現(xiàn)在修改的數(shù)據(jù)是什么?在我們這個應(yīng)用場景里面是默認的假設(shè)。你會利用DPF針對你內(nèi)存里面的每一個值都進行增加一個偏移量,就是剛才你算出來的最新的值和以前的值之間的差。【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估當然這個增加的時候你會需要乘以一個Point Function,也就是說絕大部分除了一個位置之外,其他所有位置你增加的偏移量都是0。然后到那個位置,你增加的偏移量是Δv,在其他部分都是0。增加完、更新完以后,你的輸出結(jié)果還是秘密分享,所以可以繼續(xù)往下走不需要做讀和寫的轉(zhuǎn)換。

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

這個是我們具體的一個Benchmark的一個result。我們針對一些常見的或者現(xiàn)在state-of-the-art  Distributed ORAM進行比較。比如我分別用紅色、黃色和綠色來表示FLORAM ORAM、SQRT ORAM、CIRCUIT ORAM,我用藍色來表示我們自己的。因為我們自己可以做offline和online的分離,所以在圖中我會畫兩條線,一條線就是直接online的運行時間,一條線是把online和offline合在一起的運行時間。那么我們的初始化時間是顯著優(yōu)于任何其他工作,可以說我們幾乎不要初始化。在讀的做法里面,我們在絕大多數(shù)情況下優(yōu)于任何其他的工作,只有當這個數(shù)據(jù)量比較小的時候,比如說數(shù)據(jù)量在2的20次以下的時候,那么SQRT ORAM會比我們的快一點點。這只是在某一些場景下面,比如說在WAN的場景下面。在寫的方面,我們整體的效率和FLORAM ORAM差不了多少。但是因為我們是可以把online和offline分開的,如果你只看online效率,當數(shù)據(jù)庫比較大的時候、超過2的20次的時候,我們的效率明顯高于所有已知的Distributed ORAM。

MPC模擬CPU

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

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

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

我們整體的MPC的Private Function Evaluation的大概運行結(jié)構(gòu)如上圖所示:第一輪要Fetch,就讀一條指令。第二輪Decode這個指令,順便去讀取相關(guān)的操作數(shù)。第三輪是Execute,因為我們需要涵蓋指令集里面所有的指令,所以Execute其實需要三輪。第四輪是寫,因為寫和Fetch可以同時執(zhí)行,所以它們在同一個pipeline里面可以重疊?;旧衔覀冞@個程序就是這樣循環(huán)。

【浙江大學張秉晟分享】RAM模型下的多方隱私函數(shù)評估

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

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

因為時間關(guān)系我們今天就分享到這里。如果大家有什么問題,歡迎大家Email,我的郵箱是bingsheng@zju.edu.cn,謝謝大家,再見。


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

分享:
相關(guān)文章
當月熱門文章
最新文章
請?zhí)顚懮暾埲速Y料
姓名
電話
郵箱
微信號
作品鏈接
個人簡介
為了您的賬戶安全,請驗證郵箱
您的郵箱還未驗證,完成可獲20積分喲!
請驗證您的郵箱
立即驗證
完善賬號信息
您的賬號已經(jīng)綁定,現(xiàn)在您可以設(shè)置密碼以方便用郵箱登錄
立即設(shè)置 以后再說