混淆電路Garbled Circuit介紹

08-17

來自專欄安全計算與密碼學

閱讀此文之前，請先閱讀差分隱私Differential Privacy介紹，並一直向上追溯直至到達根節點或已訪問節點。

混淆電路（Garbled Circuit）這個可得好好寫寫，一則這玩意兒確實有點抽象，每次說半天都未必能對一個程序猿講明白，畢竟一堆只發亂碼的參與者，怎麼就得到了計算結果呢？然而密碼學方法已經決定了，確實可以這麼做；二則混淆電路乃我們院長的傑作，不能丟他的臉。話不多說，貼圖鎮樓。

先明確一下混淆電路解決的是什麼問題。通俗的說，就是一堆人各自擁有其隱私數據，他們想把這些數據合起來算點什麼，但又不想把數據交給別人，混淆電路解決的就是此類問題。我們先來考慮一個經典問題——百萬富翁問題。兩個身價也就那麼百來萬的人覺得自己是富翁，他們在某會所里碰見，因為某種原因需要比個高下方能取得某種資格，但又覺得自己那些存款數目是多大秘密似的捨不得告訴別人，於是他倆遮遮掩掩地將數據拆散、打亂、加密，最後算出了結果並只解密結果。

那麼，我現在要說說混淆電路具體是如何工作的了。注意關鍵詞「電路（circuit）」，我們知道可計算問題都可以轉換為一個個電路，於是就有了加法電路、比較電路和乘法電路等等。當然，更複雜的計算過程，如深度學習等等，也是可以轉換成電路的。一個電路是由一個個門（gate）組成的，比如與門、非門、或門、與非門等等。

如上圖所示，封面中的兩個人Alice和Bob想要搞點事情，他們搞了個電路（比如比較電路，或者emmmm什麼電路），電路裡面有一些門，每個門包括輸入線（input wire）和輸出線（output wire）。混淆電路就是通過加密和擾亂這些電路的值來掩蓋信息的。在最經典的混淆電路中，加密和擾亂是以門為單位的。每個門都有一張真值表。比如下圖就是與門的真值表和或門的真值表。下面就以與門為例來說明混淆電路的工作原理。

Alice和Bob想計算一個與門。該門兩個輸入線 $x$ 和 $y$ 和一個輸出線 $z$ ，每條線有0和1兩個可能的值。Alice首先給每條線指定兩個隨機的key，分別對應0和1。

然後，Alice用這些密鑰加密真值表，並將該表打亂後發送給Bob。加密過程就是將真值表中每一行對應的 $x$ 和 $y$ 的密鑰加密 $z$ 的密鑰。這一加密+打亂的過程，就是混淆電路（garbled circuit）的核心思想。

那Bob收到加密表後，如何計算呢？首先Alice把自己的輸入對應的key發給Bob，比如Alice的輸入是0，那就發 $k_{0x}$ ，輸入是1就發 $k_{1x}$ 。同時把和Bob有關的key都發給Bob，也就是 $k_{0y}$ 和 $k_{1y}$ 。然後Bob根據自己的輸入挑選相關的key。由於Bob收到的這些key都是隨機數，所以其實並沒有任何有效信息泄露。Bob根據收到的 $k_x$ 和自己的 $k_y$ ，對上述加密表的每一行嘗試解密，最終只有一行能解密成功，並提取出相應的 $k_z$ 。