Yao’s混淆電路

?? 姚期智院士提出的首個安全多方計算方案，該方案可以計算任意可以轉換成電路的函數f(x),屬于安全雙方計算方案。安全思想：一個人加密整個電路的輸入輸出，另一個人盲算，這樣就導致信息不對稱，從而一方不能獲得另一方的數據。

?? 以加密一個與門G為例。該與門有兩個輸入A,B；一個輸出Y。

與門G

?? 假設Alice與Bob要計算這樣的一個與門G，Alice擁有輸入A的值，Bob擁有輸入B的值，他們要各自用自己的數據做“與運算”。

方案如下：

1. Alice為輸入和輸出每個可能的值創建一個標簽，分別為?。?表示當A取0時生成的標簽，?表示當A取1時生成的標簽，其他類似。

2. Alice使用輸入標簽作為密鑰將輸出標簽進行加密生成一個加密的真值表。

在這個表中，表示使用標簽作為密鑰進行對稱加密,其他類似。

Alice再將這個表的位置進行隨機置換就得到了混淆表。

3. Alice將混淆表和自己的輸入所對應的標簽發送給Bob。

4. Bob運用不經意傳輸協議（OT）向Alice請求自己的輸入對應的標簽。這樣Bob就得到了解密輸出標簽所需要的全部兩個標簽。

5. Bob使用兩個標簽對混淆表解密，最終只有一行可以成功解密，這個結果就是與運算的輸出標簽，將標簽發送給Alice。Alice將最后的真實結果告訴Bob。

關于混淆電路的一些解釋：

第一點： 標簽只是一些隨機數，標簽其實就代表了某根導線的取值（0或1）。

第二點：不經意傳輸協議可以做到：Bob可以向Alice請求自己的輸入對應的標簽，但Alice并不知道Bob最后請求的是哪個標簽。

第三點： 上述方案只是一個與門的例子，如果只計算這么一個門，那么一方可以根據自己的輸入和最終結果推出另一方的輸入。實際中的電路是由很復雜的各種門組合而成，在這樣的電路中，一方是不會反推出另一方的輸入的。

第四點：在較復雜的電路里，Alice是對電路中每一根導線都設定兩個標簽，對每個門都生成一張混淆表。這里的導線可能同時是一個門的輸出和另一個門的的輸入，這時候，導線作為門輸出的兩個標簽和作為門輸入的兩個標簽是對應一樣的。所以在Bob的計算過程中，Bob始終不知道Alice的輸入是什么（他只知道Alice輸入的標簽，但不知道標簽對應的真實值是什么。換句話說，Bob可以完成整個計算，但是Bob計算的都是一些標簽值，他并不知道這些標簽所對應的真實值，所以他不能推出Alice的輸入）。而Alice雖然知道每個標簽所代表的真實值，但是他全程都沒有參與計算，所以并不能知道中間結果，也就不能推出Bob的輸入

第五點：這一點我沒有想明白，如果有大佬知道，請在評論區告訴我，不勝感激！！Bob用兩個標簽解密時會對混淆表的四行都嘗試解密，只有一個會解密成功，那么它是如何判定某一行是解密成功的呢？畢竟都是一些看似是亂碼的隨機數。（PS：這個問題在一些Yao’s混淆電路優化方案中被得到優化，有一個方案大概是生成混淆表時把對應位置也記錄下來，這樣只要解密特定位置的行就可以了，這樣就減少了計算開銷。）

總結

以上是生活随笔為你收集整理的安全多方计算——Yao‘s 混淆电路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。