亂碼電路第2部分：通用解決方案

在我們的亂碼電路系列的第 1 部分中，我們找到了拯救遇難朋友的特定問題解決方案。但是，該解決方案沒有提供私下計算函數的通用方法（不透露其輸入）。構建用于評估特定函數f（x）的通用解決方案的一種方法是設計一個電路，將可能的輸入x映射到可能的輸出f（x）。例如，考慮一個NAND門：

門將其輸入導線 （{0，1}， {0，1}） 的所有可能值映射到其輸出導線 {0，1} 的值。但是，為了找到輸出導線的值，評估器必須知道輸入導線的值。我們的目標問題要求輸入線保持私有，因此我們需要修改這種方法。

亂碼電路

一般的解決方案是由圖靈獎獲得者Andrew Yao在1986年給出的[1]。令人難以置信的是，Yao證明了任何多項式時間函數都可以通過“亂碼”規則電路在多項式時間內安全地計算（不泄露玩家的輸入）。在本介紹中，我們將考慮最簡單的情況，即只有兩個參與者，愛麗絲和鮑勃。每個都有一個不應透露給對方的專用輸入位，并且每個都想了解NAND（Alice Input，Bob Input）的結果。由于任何函數都可以從NAND門構造，因此僅顯示如何亂碼就足夠了。我們將讓 Alice 生成（構建）亂碼電路，Bob 將評估亂碼電路以恢復結果。

發電機步驟（愛麗絲）

生成器的第一步是將導線輸入 {0，1} 替換為獨立且相同分布 （i.i.d.） 隨機值 K。這些隨機值將用作對稱密碼（如 AES）的加密密鑰。在我們的表示法中，K 映射到的二進制值 {0，1} 是上標，而 K 對應的輸入線 {1，2} 是下標。在我們的示例中，Alice 將向導線 1 提供輸入，Bob 將向導線 2 提供輸入。

由于 Alice（電線 1）知道她的輸入位 b，她只需刪除與 1-b 對應的另一個鍵。但是，Alice 將如何向 Bob 發送與他的輸入位對應的密鑰？

顯而易見的解決方案存在問題：

如果鮑勃向愛麗絲索要與他的位b相對應的密鑰，那么他已經透露了他的私人輸入。

如果 Alice 向 Bob 發送 b 和 1-b 的兩個鍵，那么 Bob 可以在兩個輸入上評估 f（x），而不僅僅是一個輸入。這揭示了其他信息，可能包括愛麗絲的私人輸入。

若要理解為什么發送兩個密鑰都會顯示其他信息，請考慮一個示例，其中 Alice 的輸入位為 0，Bob 的輸入位為 0。NAND（0，0） 的輸出為 1。如果 Bob 只知道他的輸入位是 0 并且結果是 0，那么 Alice 的輸入位可能是 0 或 1。但是，如果 Bob 能夠同時評估 0 和 1 上的門，他會發現 NAND（A，0）=1 和 NAND（A，1）=1，這表明 Alice 的輸入位必須是 0。這是對愛麗絲私人輸入位的不必要披露。

由于 Bob 無法要求他的輸入密鑰，而 Alice 無法同時給他兩個可能的密鑰，因此我們需要一個解決方案，其中 Bob 只接收其輸入位的密鑰，而 Alice 不知道她發送給 Bob 的密鑰。不可能的？

審核編輯：郭婷