安全多方计算-入门学习笔记(三)
四、基于非噪音的安全多方計算介紹
1概念
非噪音方法一般是通過密碼學方法將數據編碼或加密，得到一些奇怪的數字，而且這些奇怪的數字有一些神奇的性質，比如看上去很隨機但其實保留了原始數據的線性關系，或者順序明明被打亂但人們卻能從中很容易找到與原始數據的映射關系(但是對于數據量大的內容，其處理需要消耗的資源非常多)。
2.方法分類
主要包括三種：混淆電路（Garbled Circuit）、同態加密（Homomorphic Encryption）、密鑰分享（Secret Sharing）。
這些方法一般是在源頭上就把數據加密或編碼了，計算操作方看到的都是密文，因此只要特定的假設條件滿足，這類方法在計算過程中是不會泄露信息的。
比如計算函數??的時候，實際操作的是?（這里??是??的密文）。
3.優缺點
優點：是不會對計算過程加干擾，因此我們最終得到的是準確值，且有密碼學理論加持，安全性有保障，
缺點：則是由于使用了很多密碼學方法，整個過程中無論是計算量還是通訊量都非常龐大，對于一些復雜的任務（如訓練幾十上百層的CNN等），短時間內可能無法完成。而且對于密碼學基礎薄弱的程序猿來說，要實現前一類基于噪音的方法沒啥難度，但要實現后一類方法則還是要費不少功夫的。
?
?
五、混淆電路Garbled Circuit
1.混淆電路的工作原理
混淆電路就是通過加密和擾亂電路的值來掩蓋數據信息的。
我們知道可將計算問題都可以轉換為一個個電路，于是就有了加法電路、比較電路和乘法電路等等。當然，更復雜的計算過程，如深度學習等等，也是可以轉換成電路的。一個電路是由一個個門（gate）組成的，比如與門、非門、或門、與非門、異或門(XOR)等等。
如上圖所示，電路里面有一些門，每個門包括輸入線（input wire）和輸出線（output wire）。
2.單個電路的混淆電路設計工作原理
加密和擾亂是以門為單位的。每個門都有一張真值表。比如下圖就是與門的真值表和或門的真值表。
(1)加密混淆過程：
Alice和Bob想計算一個與門。該門兩個輸入線?x?和?y?和一個輸出線?z?，每條線有0和1兩個可能的隨機值。Alice首先給每條線指定兩個隨機的key(密鑰)，分別對應0和1。
然后，Alice用這些密鑰加密真值表(加密過程就是將真值表中每一行對應的( x ，y、 z 的密鑰)去加密真值表對應的值)，并將該表打亂(只調換行位置，輸入輸出的對應值肯定不能變化)后發送給Bob。這一加密+打亂的過程，就是混淆電路（garbled circuit）的核心思想。
(2)解密分析過程：
那Bob收到加密表后，如何計算呢？
首先Alice把自己的輸入對應的key(密鑰)發給Bob，比如Alice的輸入是0，那就發??(輸入是1就發??)[說明：此時由于真值表是加密且打亂狀態,Alice發送的密鑰被他人獲取(包括Bob)也是屬于無用數據，因為加密過程是A操作的]。同時把和Bob有關的key都發給Bob，也就是??和??兩個密鑰都發送給Bob。然后Bob根據自己的輸入挑選相關的或是，并且根據收到Alice的??和自己的??，對上述加密表的每一行嘗試解密，最終只有一行能解密成功，并提取出相應的?。
Bob將Kz發給Alice，[說明：此時對于Bob來說，自身的數據為自己控制輸入，他人無法獲取，自身數據得到保護，而發送給Alice的Kz結果對于Alice來說并不知道數據源]Alice通過對比是??還是??得知計算結果是0還是1，從而解密得到最后結果，由于整個過程大家收發的都是密文或隨機數，所以沒有有效信息泄露。
(3)流程圖如下：
以上就是混淆電路中單個門的計算方法。當然每個電路肯定是由多個門組成的，這時候需要將這些門都串起來。當然，這樣的混淆電路方法有點復雜，現在大家已經研究出了很多優化方法，具體方法可以去看論文。
[1] Kolesnikov, Vladimir, and Thomas Schneider. "Improved
garbled circuit: Free XOR gates and applications."?International Colloquium on
Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 2008.
[2] Yao, Andrew Chi-Chih. "How to generate and exchange
secrets."?Foundations of Computer
Science, 1986., 27th Annual Symposium on. IEEE, 1986.
?
六、密鑰分享(Secret Sharing)
(對混淆電路處理復雜運算à密鑰分享)
1.基本原理
(1)獲取數據。將每個數字?x?拆散成多個數?x1,x2,x3,…,xn?，并將這些數分發到多個參與方?S1,S2,…Sn?那里。然后每個參與方拿到的都是原始數據的一部分，一個或少數幾個參與方無法還原出原始數據，只有大家把各自的數據湊在一起時才能還原真實數據。
(2)各個服務器計算。各參與方直接用它自己本地的數據進行計算，并且在適當的時候交換一些數據（交換的數據本身看起來也是隨機的，不包含關于原始數據的信息），計算結束后的結果仍以secret sharing的方式分散在各參與方那里
(3)得出結果。所有服務器最終將所有計算結果數據合起來，得出最終數據。這樣的話，密鑰分享便保證了計算過程中各個參與方看到的都是一些隨機數，但最后仍然算出了想要的結果。
2.閾值密鑰分享
定義一種名為?(t,n)?閾值密鑰分享的方案，此類方案允許任意?t個參與方將秘密數據解開，但任何不多于?t-1個參與方的小團體都無法將秘密數據解開。
2.1思想：
假設A想要使用?（t，n）?閾值密鑰分享技術將某秘密數字?s?分享給S1,S2,S3,….,Sn，那么他首先生成一個?t-1?次多項式多項式??，其中?a0?就等于要分享的秘密數字?s?，而??，則是A生成的隨機數。隨后A只需將?分別發給(S1,S2,S3,….,Sn)（s1,s2,s3,….,sn值A可事先算出吧）即可， ?中任意?t?個湊在一起構成t個方程組，t個變量(a0,a1a2..at)則可以解出a0的值，而任意?t-1?個湊在一起都無法得到?a0?（即?s?）的確切解。通過這一點便達到了?（t，n）?閾值的要求，同時也滿足加法同態。
2.2多發計算，實現乘法計算：
使得(S1,S2,S3,….,Sn能在計算發生前預先得到兩個隨機數?a?和?b?的秘密分享，以及?a?和?b?的乘積?c?的秘密分享，而且它們都不知道?a?和?b?和?c?的真實值，如下圖所示：
?
現在有A和B分別分享了兩個數字?x?和?y?，參與方需要算出?x?和?y?的乘積?z?的密鑰分享。
可以借助前面生成的隨機乘積元組。我們令?s=x-a?以及?t=y-b?，然后我們可以看到
參與方S1,S2,S3,….,Sn可以聯合起來{s+t=x+y-(a+b)；s-t=x-y+b-a}將?s?和?t?的值解開，由于?a?和?b?都是值未知的隨機數，因此?s?和?t?的值并不會暴露關于?x?和?y?的信息。上面那個式子中，?s*t,s*b,a*t??以及?c?的值可計算出來，因此這幾項合起來便能得到?z=x*y?的密鑰分享。
七、同態加密（Homomorphic Encryption）
劉巍然-學酥
https://www.zhihu.com/people/liu-wei-ran-8-34
Ph.D/公鑰加密/數據隱私保護/Java/
如果未來真的做出了Practical Fully Homomorphic Encryption，那么Gentry一定可以得到圖靈獎。哭死！
1.概念
同態加密提供了一種對加密后的數據進行處理的功能。其他人可以對加密后的數據進行處理，但是處理過程不會泄露任何原始內容，同時，擁有密鑰的用戶對處理過的數據進行解密后，得到的正好是處理后的結果。
數據處理運行流程：
2.應用
同態加密幾乎就是為云計算而量身打造的！我們考慮下面的情景：一個用戶想要處理一個數據，但是他的計算機計算能力較弱。這個用戶可以使用云計算的概念，讓云來幫助他進行處理而得到結果。但是如果直接將數據交給云，無法保證安全性啊！于是，他可以使用同態加密，然后讓云來對加密數據進行直接處理，并將處理結果返回給他。這樣一來：
?? 用戶向云服務商付款，得到了處理的結果；
?? 云服務商掙到了費用，并在不知道用戶數據的前提下正確處理了數據；
?
3.同態加密的兩類：
Fully Homomorphic Encryption (FHE)全同態：這意味著HE方案支持任意給定的f函數，只要這個f函數可以通過算法描述，用計算機實現。顯然，FHE方案是一個非常棒的方案，但是計算開銷極大，暫時還無法在實際中使用。
Somewhat Homomorphic Encryption (SWHE)：這意味著HE方案只支持一些特定的f函數。SWHE方案稍弱，但也意味著開銷會變得較小，容易實現，現在已經可以在實際中使用。
最最經典的RSA加密，其本身對于乘法運算就具有同態性。Elgamal加密方案同樣對乘法具有同態性。Paillier在1999年提出的加密方案也具有同態性，而且是可證明安全的加密方案哦！后面還有很多啦，比如Boneh-Goh-Nissim方案[BGN05], Ishai-Paskin方案等等。不過呢，2009年前的HE方案要不只具有加同態性，要不只具有乘同態性
4.面臨的問題
效率。一個是加密后的數據的處理速度，一個是這個加密方案的數據存儲量
1.精準度會變差。加密后的數據處理與現有原數據在構造上會有差別，處理會出現誤差。
2. 密文的操作花費更長的時間
3.算法要求更高
4.更大的存儲容量需求
總結
以上是生活随笔為你收集整理的安全多方计算-入门学习笔记(三)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 5G工业物联网环境下多方认证性能评估
- 下一篇： NS2实验代码解析