究竟什麼是“亂碼電路”？
這裡有很多關於“亂碼電路”的細節和操作方法的問題，但我還沒有看到任何定義什麼是亂碼電路的東西。
究竟什麼是亂碼電路？它們的用途是什麼？它們的局限性是什麼？
亂碼電路的標籤只是說它們用於安全的多方計算。但是，這個答案表明它們僅適用於兩方計算？
這個問題尋求“電路”的定義。電路和亂碼電路有什麼區別？
電路只是表示計算的一種方式。沒有關於電路的特別加密。它僅僅意味著一個直線計算（沒有循環或流控制結構），只包含對位的操作，如 AND、OR、NOT。
亂碼電路是一種“加密計算”的方法，它只顯示計算的輸出，但不顯示輸入或任何中間值。我們使用術語“電路”是因為亂碼電路的工作原理是通過將您關心的計算表示為電路，然後為電路中的每個操作（AND、OR、NOT）執行一些加密操作。
如果我們想更精確一點，“亂碼方案”包括：
- （Garble）一種轉換（普通）電路的方法 $ C $ 進入亂碼電路 $ \widehat C $ .
- （編碼）一種轉換任何（普通）輸入的方法 $ x $ 對於電路進入亂碼輸入 $ \widehat x $ . 您需要用於使電路亂碼的秘密隨機性進行編碼 $ x $ 進入 $ \widehat x $ .
- (Evaluate) 一種走亂碼電路的方法 $ \widehat C $ 和亂碼輸入 $ \widehat x $ 併計算電路輸出 $ C(x) $ . 任何人都可以做到這一點，你不必知道 $ x $ 或者裡面的秘密隨機性 $ \widehat C $ 評估和學習 $ C(x) $ .
我在這裡簡化了一點。但是安全的主要思想是 $ \widehat C $ 和 $ \widehat x $ 一起洩露的資訊不超過 $ C(x) $ . 特別是，它們沒有透露任何關於 $ x $ ，但它們允許計算 $ C(x) $ 完成（不經意間）。這就是我所說的“加密計算”。
亂碼電路的主要應用是安全的兩方計算。假設 Alice 有私人輸入 $ x $ Bob 有私人輸入 $ y $ . 他們就某些功能達成一致 $ f $ 並同意他們都想學習 $ f(x,y) $ ，但不希望他們的對手學到更多東西 $ f(x,y) $ . 為此，他們可以執行以下操作（這是 Yao 的經典協議）：
- 雙方就表達方式達成一致 $ f $ 作為（普通）電路。愛麗絲弄亂了電路 $ f \mapsto \widehat f $ . 她發 $ \widehat f $ 給鮑勃以及她自己的“亂碼輸入” $ \widehat x $ .
- Alice 知道如何對任何輸入進行編碼 $ f $ 進入“亂碼”輸入，但只有 Bob 知道他的私人輸入 $ y $ . 於是雙方安排 Bob 拿起一個亂碼版本 $ \widehat y $ 沒有愛麗絲學習什麼 $ y $ 曾是。這可以通過稱為不經意轉移的原語來完成。
- 現在 Bob 出現了亂碼電路 $ \widehat f $ , 和一個亂碼輸入 $ \widehat x, \widehat y $ 對於那個電路。然後他可以執行評估程序並學習 $ f(x,y) $ . 他可以透露 $ f(x,y) $ 給愛麗絲。
我們可以爭辯說，該協議揭示的不超過 $ f(x,y) $ 通過以下方式：
- 除了最終的答案，愛麗絲什麼也沒看到 $ f(x,y) $ 在這個協議中（不經意傳輸的安全性確保她在步驟 2 中什麼也學不到）。
- 儘管鮑勃看到 $ \widehat f $ , $ \widehat x $ 和 $ \widehat y $ ，亂碼電路的安全性確保這些值不會洩露任何超出 $ f(x,y) $ .
這種方法適用於 Alice 和 Bob 是半誠實的（即他們按照指示遵循協議）。但是當愛麗絲是惡意的時，她可以亂碼一些其他功能 $ f’ $ 而不是 $ f $ 他們同意的。因此，當我們需要針對惡意對手的安全性時，需要在協議中添加其他內容以防止這種情況發生。
參考資料：
- Yao 結構及其安全證明（影片），Yehuda Lindell
- 姚氏安全兩方計算協議的證明, Yehuda Lindell & Benny Pinkas
- 亂碼電路的基礎，Mihir Bellare，Viet Tung Hoang，Phillip Rogaway
- 實用亂碼電路優化簡史，我的影片。前幾張幻燈片介紹了亂碼電路的“經典”結構。