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

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

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

亂碼電路

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

發(fā)電機(jī)步驟（愛麗絲）

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

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

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

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

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

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

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

審核編輯：郭婷