<mark id="oztn4"></mark>
0
IEEE x ATEC科技思享會是由專業技術學會IEEE與前沿科技探索社區ATEC聯合主辦的技術沙龍。邀請行業專家學者分享前沿探索和技術實踐，助力數字化發展。
在萬物互聯的大數據時代，數據鏈接了我們生活的方方面面。一方面，大數據極大便利了我們的工作與生活；另一方面，數據的海量化也增加了諸多隱私信息泄露的風險與挑戰。本期科技思享會邀請到了四位重磅嘉賓，共同圍繞“隱私保護的前沿技術及應用”這個主題，分別從機器學習算法、通訊協議、APP及操作系統等不同層面，就隱私安全風險及技術創新應用展開討論。
以下是浙江大學張秉晟研究員的演講，《RAM模型下的多方隱私函數評估》。
大家好，我是浙江大學的張秉晟。今天跟大家分享一個我們組和螞蟻摩斯最新的合作研究成果《RAM模型下的多方隱私函數評估》。什么是RAM模型，什么是隱私函數評估？在這個Talk中我會慢慢跟大家介紹。
目的與場景
首先是目的和場景。隱私泄露的問題日益嚴重，也得到了越來越多人的關注，包括國家、政府和各級的地方機關。我國的大部分互聯網公司都或多或少有一些需要整改的地方，也收到過國家的整改條令、約束等。上圖中列舉了一些隱私泄露的相關案例，其他案例在此不再一一列舉。
最近，我們國家對數據安全和隱私保護的相關立法加速落地。從2012年開始到現在，我們國家相繼出臺了網絡安全法、個人信息保護法、數據安全法等一系列法律法規。目前這些法律法規還只是比較上層的指導意見。例如在個人安全法里面提到，含有個人敏感信息的數據在通過處理不可以逆推、不可以反推出原始數據的情況下，是不受該法保護的。即它從側面提供了一個我們對隱私計算、對數據互流互通的一個約束，數據要經過處理是不可以逆推成原始數據的。這些法律法規目前還比較上層，具體的評判標準還在制定當中。但是我們相信在不久的將來，我們這個評判標準也會越來越明確，至少現在去標識化已經有相關的標準。
去年Gartner給出了一個預測，根據預測報告：在2023年底，全球有75%的人口的個人數據將受到隱私法律的保護。到2023年底之前，全球有超過80%的公司將面臨至少一項以隱私為重點的數據保護法規。到2024年，全球隱私驅動的數據保護和合規技術將突破150億美元。到2025年，有60%的大型組織和企業，他們會通過至少一種或者多種隱私增強技術來實現數據的分析、云計算、建模制、數據的智能化處理等等。
隱私保護和數據安全的技術有很多，我們這個工作主要是屬于安全多方計算的范疇。那什么是安全多方計算呢？它的英文叫Secure Multiparty Computation，它是密碼學的一個重要研究分支。如果你去網上搜索什么是安全多方計算，那么你一般會找到以下這句定義：為解決一組互不信任的參與方之間在保護隱私信息以及沒有可信第三方的前提下協同計算問題而提出的密碼協議與理論框架。
如果你是學習密碼學或者密碼協議或者隱私計算的圈內人士，那我們有相關的狹義定義。在狹義定義中，安全多方計算一般可以分為兩種主要的實現形式：一種是姚氏混淆電路，它主要是用于兩方計算，當然也可以用于多方計算。姚氏混淆電路比較好的特點是它對布爾電路的支持非常好，這也是安全多方計算。姚期智教授是在1982年提出安全多方計算時提出的設想。現在的姚氏混淆電路經過40年的優化和改良，效率已經非常非常高了。第二種是針對布爾電路或者代數電路，我們是以秘密分享的形式來實現兩方或者多方的協議。這種實現方式有什么好處？它的通信量會比姚氏混淆電路整體通信量小，但是它的通信輪次會比較多，比較適用于帶寬比較小、但是延時比較少的應用場景。如果延時比較高的話還是建議用姚氏混淆電路，當然秘密分享對代數電路的支持肯定是好于姚氏混淆電路。
當然現在也有一些混合的協議，即你在同一個函數中或者同一個計算任務中，既要解決布爾電路，又要解決代數電路如何在它們之間進行轉換，比如說ABY系列。廣義來說，就我個人理解而言，安全多方計算可以包括密碼學的一些原語，比如說全同態加密。
有人問，全同態加密和安全多方計算是什么關系？它們是不是兩個不同的技術？
在我看來它們是不對等的一個比較。因為全同態加密只是一個加密的原語，這就相當于在安全多方計算里我可不可以應用例如AES加密，你說可以。在我看來，AES加密和全同態加密都是一種加密算法，而安全多方計算是一種協議、是一個更高維度的東西。安全多方計算的協議如果使用了比如說簽名算法、加密算法，這個協議仍然是安全多方計算協議。所以在我個人的理解里面，安全多方計算協議即使使用了同態加密、半同態、全同態，它仍然是安全多方計算協議。在業界，因為一些要求它把基于可信硬件的安全多方計算叫做Confidential Computing（機密計算），又把聯邦學習從安全多方計算中分離出來。其實聯邦學習提出的時候，它并沒有安全的定義。在我看來，聯邦學習和安全多方計算其實也是一個不可比較的概念。因為聯邦學習里面是可以應用安全多方計算技術去做一些隱私保護的事情。
我們研究這個成果的研究目的是什么呢？
我們主要是為了解決兩方或者多方在比如說云計算的時候，要保護計算任務、要保護特定的算法。什么意思呢？傳統的安全多方計算指你在計算的時候所有的安全多方計算參與方都會知道你要計算的是什么任務，也就是說我的算法是公開給所有的安全多方計算參與方。而我們要保護的只是數據、只是輸入，只是這個計算的輸入。但是對于一些應用場景，它的算法是非常重要的，比如別人的知識產權，比如DNA精準、靶向制藥。例如我有一個算法，我的算法需要應用到你的DNA產生藥的配方，但是我的算法不能公開給你，雖然你的DNA也是隱私保護的，但我和你做兩方計算的時候你不可以得到我的算法。也就是說我有需求是保護算法，你有需求是保護輸入。這個就牽扯到一個分支，這個分支一般我們在Community里面會把它稱為Private Function Evaluation，我把它翻譯成隱私函數評估，也就是說我們在保護輸入的前提下，還要保護我們所計算的函數、我們要計算的任務。我們不可以讓計算方知道在計算什么任務，即保護你的計算算法的IP。
顯然這是一個安全多方計算的一個分支，也就是說它仍然是屬于安全多方計算的領域。據我所知，目前傳統的安全多方計算，所有商用的安全多方計算都是基于電路格式。Sort格式什么意思？也就是說你只能順序執行，你在安全多方計算里面是不可以支持RAM計算模型的。什么叫RAM計算？RAM就是Random Access Machine。我們現在的常規電腦是馮諾依曼結構，在內存里可以隨機訪問或跳轉Random Access。比如說你做一個Binary Search，二分搜索，你不需要scan整個Memory，你可以跳到你指定的位置去做讀寫、做比較，然后再做下一步操作。但是因為一些技術的限制，在安全多方計算里面我們現在不能做這種類似操作，我們現在只能順序執行。而這種順序執行會極大程度的限制我們安全多方計算可以使用的場景，比如說有一些我們需要跳轉或者跳轉比較多的算法就沒辦法高效的用安全多方計算來實現。
我們這次想要做的一個工作是在RAM模型下去實現一個Private Function Evaluation。也就是說我們這個安全多方計算系統再也不用被編譯成電路就能支持RAM的計算結構。如果你有一個死循環，你有一個While Loop，甚至你的While Loop里面的Condition是一個不確定的Condition。比如說一個死循環里面，你有一個基于私密數據的隱私保護數據的條件，那么我們這個模型也能夠去支持，并且我們這個模型會保護你的算法。我們的做法大致講來是把一些高級語言(比如C++語言或者Java等)用編譯器(比如用LLVM的編譯器)編譯成TinyRAM的指令集，為什么是TinyRAM呢？因為我們需要一個精簡指令集，如果指令集太復雜了我們整個系統的開銷就會非常的大。所以我們就選了一個精簡指令集，TinyRAM。當然RISC-V也是可以的，我們對程序和輸入都進行隱私保護。具體來說我們都進行秘密分享，我后面會一一和大家解釋具體操作。
我們在程序秘密分享和數據秘密分享的前提下進行安全的執行，我們可以密態的執行。
先講一下我們構建的一個前提工作，也就是我們要構建一個分布式的ORAM。
什么是分布式的ORAM呢？
傳統的ORAM是講你有一個服務器或者有多個服務器，然后有一個Client，這個Client在服務器上面進行讀寫，它不能讓服務器知道你讀寫的是哪一個位置。分布式ORAM指的是我已經不存在這樣的一個Client，我在安全多方計算時我要讀寫哪一格的位置，其實我要讀寫的這個數據也是隱私保護的，比如說它是以秘密分享的形式去保護的，然后在服務器上面進行讀寫，它也是一個分布式的結構。具體我們采用了4個服務器架構。如果你要只讀的話，我們也可以做出3PC的格式。這個2PC的格式后面我們會講，這是一個經典的PIR，但它不是標準的ORAM，它只是一個Private Information Retrieval的實現形式，主要是基于DPF（Distributed Point Function），也就是FSS（Functioning Secret Sharing）。
我們構建的這個分布式有幾個特點：第一個特點，它可以進行任意次的讀和寫，而且讀和寫之間的轉換是不需要Refresh、是不需要Eviction的。即我們看見的一些常見操作，可能它的讀會很快，但是讀轉到寫的過程中需要非常多的時間或者它的讀寫都比較快，但是它經過若干次的讀寫突然要進行一次Refresh或者進行一次Image，這就極大程度的限制了這些ORAM在我們這個場景中的使用。具體來說，我們的O-READ，它的通信量是12log2(n) bits，這個N就是你這個Memory大概有多少Memory的size。然后你在Memory里面取一個數，不讓這個服務器知道你取哪一個數。我們需要的通信量是12倍的log2(n)，然后你想oblivious去改寫那個Memory，就是你在一個N個size的Memory里面，你在某一條里面想去寫入一個數。比如說在i條里面寫入一個數，在我們這里All Right的通信量是24倍的log2(n)加12t bits，T其實就是你要寫入的這個數據的長度，具體的操作它分Open δ、Cyclic- shift、Scale、Re-randomize，稍后我會一一介紹。
我先簡單介紹一下DPF。DPF是Distributed Point Function，它最經典的構造是兩方的DPF，就是有個Generate，它會Generate出兩個K，這個K一方給左邊，一方給右邊，兩個服務器S1和S2。這兩個服務器分別針對這個K做Evaluate，把做出來的最后一行的從β0到β3兩個東西全加起來，它其實是一個Unit vector。什么叫Unit vector？它只有一位是non-zero，none-zero位通常在這個應用場景里面會把它取為1，其他每一位都是0，也就是說這其實是一個Compression的過程，把一個Unit vector給compress成一個log2(n) Size的T。因時間問題，具體的做法我在此就不一一講了，這是一個比較經典的技術，它是用一個Tree的Structure，在每一層會有一個Correction。也就是說它一共有log2(n)層，所以它的K Size會有log2(n)。這個在數據量比較大的時候，這個Tree的Expansion耗時會比較長；但是在數據量比較小的時候，它的操作會非常的快。
2PC會有一些缺點，2PC的這個FSS，傳統的FSS-based PIR：
第一,它不能直接用在我們這里，原因是它需要兩個Server兩個服務器，看見相同的銘文，它其實是一個多Server的PIR。服務器上面的兩個服務器要有一模一樣的數據，然后你選取這個數據里面一模一樣的PIR的位置，再到自己本地進行合成。
第二是這個Client知道自己要取哪一個數。那我們要做這個分布式的RAM，首先服務器不能知道這個數據的銘文是什么。其次，服務器在我們這個應用場景里面甚至也不可以知道它要取哪一個數。也就是說這兩個都必須得秘密分享、必須得保護。
所以我們才會有一個4Server的結構。大概的思路是一個DPF需要兩個服務器，有相同的值。在雙服務器的情況下，這兩個服務器必須存明文。但我們如果有4服務器，我們其實可以把這個數據秘密分享成兩份。舉個例子，這兩份分別由S3和S4去拿同一份秘密分享的Share，S1和S2拿同一份秘密分享的Share，也就是Replicated Share。這兩個拿同一份、那兩個拿同一份，這樣我們可以讓S1去生成一個DPF的K分給S3和S4。S3和S4針對他們共有的Share可以做剛才的PIR的Evaluation。同理，這個S1和S2也可以對他們共有的Share去做PIR的Evaluation。
這里還會有一個問題，就是我們要取的這個點也不能透露給別人。要取的這個點不透露給別人，我們的做法就是在offline階段，可以做一個DPF針對一個隨機的點。比如說i是0到N減一里面任意的一個數，等到你實際上你要存取的那個值出來的時候，你把實際要存取的值減掉我們之前prepare的時候隨機選的那個值，出來的那個數它其實就是一個offset，就是一個糾正量。我們讓所有的服務器對自己的數據shift這個Cyclic的shift，就是去循環的移動偏移量，使得我們做的這個DPF它就相當于是針對一個未知的秘密分享的目標索引做的DPF。具體我在此就不細講了。
做完了以后，4方各自會做一個linear function，也就是說他們不需要通信就可以以秘密分享的形式去得到要取的數，就比如說你要取第i個數，那么這個數就叫Xi。根據上圖的公式，你其實就可以算出這個Xi是什么，即Xi也是一個秘密分享的形式存在的。
寫怎么寫呢？寫會比讀麻煩一點，因為如果只讀的話3方也夠，我們這個算法有3方的版本。如果你要寫的話必須得4方。寫，我們其實是有一個限制的。我們的寫法大概的原理是你需要知道原始的數據是什么，你需要知道你寫進去的這個數據是什么，然后你把寫進去的這個數據減掉原始的數據，你就會有一個delta，即有個修改量、偏移量。你需要把原始的數據增加多少量才會變成你現在想要它變成的這個數據。
因為在我們的應用場景里面，你在寫之前必定是讀過那個格子的值的，所以我們這邊并不會增加任何額外的開銷。即我們這個假設你需要知道原始的數據是什么？現在修改的數據是什么？在我們這個應用場景里面是默認的假設。你會利用DPF針對你內存里面的每一個值都進行增加一個偏移量，就是剛才你算出來的最新的值和以前的值之間的差。
當然這個增加的時候你會需要乘以一個Point Function，也就是說絕大部分除了一個位置之外，其他所有位置你增加的偏移量都是0。然后到那個位置，你增加的偏移量是Δv，在其他部分都是0。增加完、更新完以后，你的輸出結果還是秘密分享，所以可以繼續往下走不需要做讀和寫的轉換。
這個是我們具體的一個Benchmark的一個result。我們針對一些常見的或者現在state-of-the-art Distributed ORAM進行比較。比如我分別用紅色、黃色和綠色來表示FLORAM ORAM、SQRT ORAM、CIRCUIT ORAM，我用藍色來表示我們自己的。因為我們自己可以做offline和online的分離，所以在圖中我會畫兩條線，一條線就是直接online的運行時間，一條線是把online和offline合在一起的運行時間。那么我們的初始化時間是顯著優于任何其他工作，可以說我們幾乎不要初始化。在讀的做法里面，我們在絕大多數情況下優于任何其他的工作，只有當這個數據量比較小的時候，比如說數據量在2的20次以下的時候，那么SQRT ORAM會比我們的快一點點。這只是在某一些場景下面，比如說在WAN的場景下面。在寫的方面，我們整體的效率和FLORAM ORAM差不了多少。但是因為我們是可以把online和offline分開的，如果你只看online效率，當數據庫比較大的時候、超過2的20次的時候，我們的效率明顯高于所有已知的Distributed ORAM。
MPC模擬CPU
有了這個非常高效的Distributed ORAM，我們就可以開始模擬這個RAM結構的CPU了。我們模擬的思路是以RAM的形式去管理存儲結構,包括所有的存儲結構（我們用的是馮諾依曼結構）、包括整體CPU運行時候的你的指針PC值和一些Flag值、一些寄存器值、一些內存的值、一些指令，所有東西都由RAM形式接管。具體來說，我們把普通的代碼，也就是任何一些C語言、高級語言的代碼，用常規的編譯器編譯成TinyRAM的指令集。我們會對TinyRAM指令集里面的指令進行解析。解析完以后，我們會進行隱私保護的執行。我們后面會講具體是怎么執行的。它是密態執行然后密態選擇、茫然更新，整體、所有的過程都是Oblivious，都是內存保護的。
具體的指令集大概有25個左右，前半部分是boolean的指令集，也就是說位操作，比如說AND、OR、XOR、NOT 、Shift等等。中間是一些加減乘除的常規操作，后面第三類是一些各種各樣的比較，它的Flag會不一樣，然后會有一些mov的操作、存取的操作和跳轉的指令。
整個 Oblivious Cycle如上圖中的左圖所示，你可以想象成它其實就是TinyRAM的一個機器。這個機器的所有狀態全部都是以秘密分享密態的形式存儲的,它有Private PC （Program Counter）。你每次來一個指令的時候，指令是從哪里讀的呢？指令我們專門有內存的Memory，我們這個結構、內存的Memory是可以不區分指令區和數據區的。也就是說如果你的代碼的寫作方式是在你代碼的運行期間動態產生代碼、新的代碼，我們是可以支持這種形式的。即你不需要把代碼定制在這個Memory里面，代碼的那部分Memory只讀，數據的Memory可以讀寫，我們不需要這樣。代碼和數據是可以混在一起的，而且你可以動態的去修改你的代碼。有一些病毒就很喜歡并且能做到把自己數據區域的數據變成代碼再去運行。
我現在不是以程序安全的角度去講這件事情，是以功能性的角度去講這件事情。我們其實可以滿足這樣的功能需求。我們這個程序會從這個Memory里面、隱私保護里面取一條指令進行解析，解析完畢后，這條指令它會有操作數還有它自己做的是什么操作、要用到什么寄存器。比如說我們會用到什么寄存器，寄存器尋址或者立即數尋址。我們再到內存里去取相關的數，取了相關的數以后我們做操作，做完操作以后再進行選擇，就是你實際上的結果。我們再把這個結果存回去，然后根據你的Flag，我們會去update這個Program Counter，就是我們下一條要運行哪條指令。我們基本上是根據這個Program Counter到這個Memory里面再去取下一條指令。
具體來說，其實我們的Oblivious Cycle最大的開銷就是我們要支持二十多條的TinyRAM的指令集。我們要做到所有指令集都在同一個步驟里面完成。大致的思路就是如何防止你知道我做的是哪一條指令，我們就把所有的指令都做了，當然不是把每一條指令單獨做一遍。觀察上圖的左邊部分你會發現，我們對所有的指令集有機進行組合。
也有前人在工作中把若干的指令集用姚式混淆電路編出來。姚式混淆電路會比較大，我們這里是用ABY的結構，有一些用姚式混淆電路做，有一些用布爾電路做，有一些是用代數電路做，所以我們這個非常高效。對于所有的指令集，我們可以在三輪內完成，包括Compare、一些比較、一些跳轉，各種指令在三輪內完成。我們有一些指令做的會比較快，有一些指令做的會比較慢，有一些指令之間是共享一些中間結果的，所以我們是有機的去組合起來。
我們整體的MPC的Private Function Evaluation的大概運行結構如上圖所示：第一輪要Fetch，就讀一條指令。第二輪Decode這個指令，順便去讀取相關的操作數。第三輪是Execute，因為我們需要涵蓋指令集里面所有的指令，所以Execute其實需要三輪。第四輪是寫，因為寫和Fetch可以同時執行，所以它們在同一個pipeline里面可以重疊。基本上我們這個程序就是這樣循環。
我們為了展示這個程序的效率做了一些相關的RAM結構下比較常見的函數的Evaluation。比如說Binary Search，比如說Set Intersection，比如說Quick Sort。具體我們把Offline、Fetch、Decode、Evaluation、Write的時間都分開測了，也包括Total time。注意，因為我們是保護函數的，所以相比于不保護函數的一些安全多方計算，時間確實慢一點。
有人說這個Binary Search感覺和Linear Scan差不多。注意，我們是保護函數的，你其實根本不知道我是在做Binary Search。為什么這個Binary Search會拿出來單獨做呢？因為如果這個不是RAM模型的結構，要做Binary Search是非常難做的，必須要整個Memory scan一遍才能夠做到。我們現在基本上你只要做log2(n)步就可以了，也就是說你只要做log2(n)次的比較你就能得出這個結果。
因為時間關系我們今天就分享到這里。如果大家有什么問題，歡迎大家Email，我的郵箱是bingsheng@zju.edu.cn，謝謝大家，再見。
專題
