為什麼 XOR 和 NOT 在亂碼電路中是免費的
我無法理解V.Kolesnikov 等人的論文中的“免費”一詞。
1. 為什麼不免費
在第 4 頁第 3.1 節中，他們說 NOT 門是免費的
通過簡單地消除它們並反轉電線值的對應關係和亂碼
我想出了下面的例子，這讓我很困惑
讓我們這麼說 $ a,b $ 分別是來自 Alice 和 Bob 的兩個單位數字輸入。假設 Alice 是亂碼者，她對上述電路進行了亂碼，並連同她的亂碼輸入一起發送給 Bob $ GI(a) $ . 然後她發送 Bob 的亂碼輸入 $ GI(b) $ 通過不經意的轉移給鮑勃。在此範例中，無需嘗試“免費”實現 NOT，Alice 只需發送
- 亂碼電路 $ \hat{C} $ ，其中包含 7 根電線（上面有不同顏色），每根電線都有兩個標籤
- . $ GI(a) $
- $ GI(b) $ , Bob 可以算出結果。
在第一步“簡單地消除它們”之後，我刪除了所有的非門並得到以下電路
現在，AND1 和 OR1 共享相同的輸入 $ b $ . 無論我如何反轉電線的值，電路都不會像以前那樣代表相同的功能。
現在看來我必須將 AND1 和 OR1 的輸入分開，然後給它們不同的標籤，儘管它們來自原始電路中的單一來源。然後電路仍然有 6 根電線，這不是很“免費”。如果它是免費的，我們不應該只能使用 5 根線來建構電路嗎？
2. 為什麼 XOR 是免費 的 在同一個頁面，他們展示了他們的 XOR gate $ G $ .
我看到通過這樣做，亂碼器不必為 $ w_i^1 $ 和 $ w_c^0 $ . 但是為什麼叫免費呢？
此外，為所有電線生成隨機標籤和只生成隨機標籤之間的計算節省是多少？ $ w_a^0,w_b^0,R $ 然後從這三個中計算其他標籤？
關於您範例中的非門。假設電線叫 $ b $ 有電線標籤 $ B $ 對於虛假和 $ B \oplus R $ 真的。然後你會像往常一樣使用這些標籤來混淆門“AND1”，並且想像一下你會混淆門“OR1” $ B \oplus R $ 意味著虛假和 $ B $ 意味著真實。
有兩種等效的方法來考慮這個問題。一種是將非門的輸出視為單獨的線（與非門的輸入分開）。如果非門輸入線有標籤 $ A, A\oplus R $ 然後輸出線有標籤 $ A \oplus R, A $ .
另一種思考方式是將所有非門吸收到它們相鄰的與/或門中。在您的範例中，我們可以為門 AND1 亂碼 NAND，我們可以亂碼門 $ (x,y) \mapsto (\lnot x \lor y) $ 為 OR1。實際做到這一點的方法和上面一樣，只是讓亂碼器切換兩個線標籤的“含義”，本地為這個門。
關於免費異或：它節省的主要成本不是為輸出線生成隨機線標籤。（事實上，高級 GC 結構不會隨機採樣線標籤，除非在輸入處。）節省的是：（1）亂碼器和評估器都不必評估加密原語來處理這個門。相反，他們只進行一次異或計算。(2)亂碼電路中不得包含任何內容，節省頻寬。因此，XOR 門對於通信成本是免費的，並且在加密操作的計算成本方面是“免費的”（正如您所指出的，由於需要一些較小的異或計算，因此並非所有計算成本都“免費”）。