讀懂安全多方計算的簡化版本:混淆電路。

原文標題:《Vitalik:混淆電路(Garbled circuits)快速入門》
撰文:Vitalik Buterin
翻譯:灑脫喜
來源:巴比特

特別感謝 Dankrad Feist 對本文進行的審閱工作。

混淆電路(Garbled circuits)是一種非常古老,且非常簡單的密碼學原語。它們很可能是通用「多方計算」(MPC)的最簡單形式。

以下是該方案的常規設置:

  1. 假設存在兩方,愛麗絲(Alice )和鮑勃(Bob),他們想要計算一些函數 f(alice_inputs, bob_inputs),這需要從雙方那獲取輸入。愛麗絲(Alice)和鮑勃(Bob)都想知道計算函數 f 的結果,但是愛麗絲(Alice)不想鮑勃(Bob)知道她的輸入,而鮑勃(Bob)則不想愛麗絲(Alice)知道他的輸入。理想情況下,除了 f 的輸出外,他們都不會得知任何其它東西。
  2. 愛麗絲(Alice )執行特殊的過程(「混淆」-garbling)來加密評估函數 f 的電路(意味着一組「與」、「或」門)。她將輸入(也以與加密電路兼容的方式進行加密)傳遞給鮑勃(Bob)。
  3. 鮑勃(Bob)使用一種稱爲「1-of-2 茫然傳輸(Oblivious Transfer)」的技術來學習自己輸入的加密形式,而不讓愛麗絲(Alice )知道他獲得了哪些輸入。
  4. 鮑勃(Bob)在加密數據上運行加密電路,得到答案,並將其傳遞給愛麗絲(Alice )。

額外的密碼學封裝可用於保護該方案,以防止愛麗絲(Alice )和鮑勃(Bob)發送錯誤的信息並互相給出錯誤的答案。爲了簡單起見,我們不會討論這些問題,儘管可以說「把 ZK-SNARK 封裝在所有東西上」是其中之一有效的解決方案(相當繁重且次優!)。

那基本方案如何運作呢? 讓我們從電路開始:

Vitalik Buterin:技術簡述密碼學原語「混淆電路」運行方式

這是一個最簡單的電路例子,它實際上做了一些事情:它是一個兩位加法器。它以二進制形式輸入兩個數字,每個數字具有兩位,並輸出一個三位二進制數字(即總和)。

現在,讓我們對電路進行加密。首先,對於每個輸入,我們隨機生成兩個「標籤」(256 位數字):一個表示輸入爲 0,另一個表示輸入爲 1。然後我們也對每個中間線做同樣的操作,不包括輸出線。注意,這些數據不是愛麗絲(Alice )發送給鮑勃(Bob)的「混淆」的一部分;到目前爲止,這只是設置。

Vitalik Buterin:技術簡述密碼學原語「混淆電路」運行方式

現在,對於電路中的每個門,我們執行以下操作。對於每一個輸入組合,我們在愛麗絲(Alice )提供給鮑勃(Bob)的「混淆」中包含輸出標籤(或者如果輸出標籤是「最終」輸出,則直接包含輸出),該標籤是通過將導致該輸出的輸入標籤散列在一起而生成的密鑰加密的。爲了簡單起見,我們的加密算法可以是 enc(out, in1, in2) = out + hash(k, in1, in2),其中 k 是門的索引(它是電路中的第一個門,第二個,第三個?)。如果你知道這兩個輸入的標籤,並且你有混淆(garbling),那麼你可以學習相應輸出的標籤,因爲你只需計算相應的哈希,並將其減去即可。

這是第一個異或門(XOR gate)的混淆(garbling):

Vitalik Buterin:技術簡述密碼學原語「混淆電路」運行方式

請注意,我們直接包括 0 和 1 (的加密形式),因爲此異或門的輸出直接是程序的最終輸出。 現在,讓我們看一下最左邊的與門(AND gate):

Vitalik Buterin:技術簡述密碼學原語「混淆電路」運行方式

在這裏,門的輸出僅用作其他門的輸入,因此我們使用標籤(label)而不是位(bit)來隱藏評估器(evaluator)中的這些中間位。

愛麗絲(Alice )將提供給鮑勃(Bob)的混淆(garbling)只是每個門第三列中的所有內容,每個門的行被重新排序(以避免顯示給定的行是否對應於任何一行中的 0 或 1)。爲了幫助鮑勃(Bob)瞭解爲每個門解密哪個值,我們將使用一個特定的順序:對於每個門,第一行變爲兩個輸入標籤均爲偶數的行,第二行第二個標籤爲奇數,第三行第一個標籤爲奇數,第四行兩個標籤均爲奇數(我們故意選擇較早的標籤,以便每個門在一個輸出上都具有偶數標籤,而在另一個輸出上具有奇數標籤)。我們以相同的方式混淆電路中的每個其他門。

總之,愛麗絲(Alice )爲電路中的每個門向鮑勃(Bob)發送了四個 約 256 位的數字。事實證明,4 遠非最佳值;有關如何將與門(AND gate)的數量減少爲 3 甚至是 2,以及將異或門( XOR gate)數量減少爲零,請參見此處的一些優化。請注意,這些優化確實依賴於某些更改,使用 XOR 代替加法和減法,儘管爲了安全起見還是應該這樣做。

當鮑勃(Bob)收到電路時,他向愛麗絲(Alice )索要與她的輸入相對應的標籤,並且他使用稱爲「1-of-2 茫然傳輸」的協議來向愛麗絲(Alice )索要與自己的輸入相對應的標籤,而沒有向愛麗絲(Alice )透露他的輸入是什麼。然後他一個接一個地通過電路中的各個門,揭露每個中間門的輸出線。

假設愛麗絲(Alice )的輸入是兩條左線,她給出(0,1),而鮑勃(Bob)的輸入是兩條右線,他給出(1,1)。這又是帶有標籤的電路:

Vitalik Buterin:技術簡述密碼學原語「混淆電路」運行方式

  1. 在一開始,鮑勃(Bob)知道標籤 6816, 3621, 4872, 5851;
  2. 鮑勃(Bob)評估第一個門,他知道 6816 和 4872,因此他可以提取與(1,6816,4872)對應的輸出值(請參見上表)並提取第一個輸出位 1;
  3. 鮑勃(Bob)評估第二個門,他知道 6816 和 4872,因此他可以提取與(2,6816,4872)對應的輸出值(請參見上表)並提取標籤 5990;
  4. 鮑勃(Bob)評估第三個門(異或門),他知道他知道 3621 和 5851,並學習 7504;
  5. 鮑勃(Bob)評估第四個門(或門),他知道 3621 和 5851,並學習 6638;
  6. 鮑勃(Bob)評估第五個門(與門),他知道 3621 和 5851,並學習 7684;
  7. 鮑勃(Bob)評估第六個門(異或門),他知道 5990 和 7504,並學習第二個輸出位 0;
  8. 鮑勃(Bob)評估第七個門(與門),他知道 5990 和 6638,並且學習了 8674;
  9. 鮑勃(Bob)評估第八個門(或門),他知道 8674 和 7684,並學習了第三個輸出位 1;

這樣鮑勃(Bob)就瞭解了輸出:101 。在二進制中,10 + 11 實際上等於 101 (在電路中,輸入和輸出位都是以從最小到最大的順序給出,這就是爲什麼愛麗絲的輸入 10 在電路中被表示爲(0,1)的原因),所以它起作用了!

請注意,加法的使用在混淆電路中是毫無意義的,因爲知道 101 的鮑勃(Bob)可以減去他自己的輸入並得到 101 - 11 = 10 (愛麗絲的輸入),從而破壞了隱私。 但是,一般情況下,混淆電路可用於不可逆的計算,因此請勿以此方式破壞隱私(例如,人們可能會想到一種計算,其中愛麗絲的輸入和鮑勃的輸入,是他們對個性測驗的答案,而輸出是一個位,決定算法是否認爲它們是兼容的;而這一位的信息不會讓愛麗絲和鮑勃知道彼此的個人測驗答案。

1-of-2 茫然傳輸(oblivious transfer)

現在讓我們更多地討論 1-of-2 茫然傳輸(oblivious transfer),這是鮑勃(Bob)用來從愛麗絲(Alice )那獲取與他自己輸入對應標籤的技術。問題是這樣的:聚焦於鮑勃(Bob)的第一個輸入位(第二個輸入位的算法相同),愛麗絲(Alice )有一個對應於 0 (6529)的標籤,和一個對應於 1 (4872)的標籤。鮑勃(Bob)有他想要的輸入位:1。鮑勃(Bob)想學習正確的標籤(4872),而又不讓愛麗絲(Alice )知道他的輸入位是 1。平凡的解決方案(愛麗絲只向鮑勃發送 6529 和 4872)不起作用,因爲愛麗絲(Alice )只想放棄兩個輸入標籤中的一個,如果鮑勃(Bob)同時接收兩個輸入標籤,則可能泄漏愛麗絲(Alice)不想放棄的數據。

下面是一個使用橢圓曲線的簡單協議:

  1. 愛麗絲(Alice )生成一個隨機橢圓曲線點 H;
  2. 鮑勃(Bob)生成兩個點 P1 和 P2,要求 P1 + P2 等於 H。鮑勃(Bob)選擇 P1 或 P2 爲 G * k (即他知道對應私鑰的點)。請注意,P1 + P2 = H 的要求可確保鮑勃(Bob)不能生成 P1 和 P2。這是因爲如果在鮑勃(Bob)知道 k1 和 k2 的情況下,如果 P1 = G * k1 和 P2 = G * k2,則 H = G *(k1 + k2),因此這意味着鮑勃(Bob)可提取 H 的離散對數(或「對應的私鑰」 」),這意味着橢圓曲線密碼系統的所有部分都被破壞了;
  3. 愛麗絲(Alice )確認 P1+P2=H,並使用一些標準公鑰加密方案(例如 El-Gamal)加密 P1 下的 v1 和 P2 下的 v2。鮑勃(Bob)只能解密這兩個值中的一個,因爲他知道最多對應一個值(P1,P2)的私鑰,而愛麗絲(Alice )又不知道是哪一個。

這解決了問題,鮑勃(Bob)根據輸入位的不同,學習兩個線標籤(6529 或 4872)中的一個,而愛麗絲(Alice )卻不知道鮑勃(Bob)學習了哪個標籤。

應用領域

混淆電路(Garbled circuits)對於很多應用都有潛在的用途,而不僅僅是 2-of-2 的計算。例如,你可以使用它們進行任意複雜度的多方計算,其中任意數量的參與者提供輸入,這些輸入可以在恆定數量的交互中運行。產生一個混淆電路是完全並行的,你可以同時進行多個混淆門。

因此,你可以簡單地進行大規模多方計算,其中許多參與者計算電路中所有門的混淆(garbling),併發布與其輸入對應的標籤。標籤本身是隨機的,因此不會透露任何關於輸入的信息,但是任何人都可以執行公佈的混淆電路,並在「清除」中學習輸出。有關使用混淆(garbling)作爲成分的 MPC 協議的最新示例,請參見此處。

多方計算不是唯一的應用環境,在這種情況下,這種將計算拆分爲可並行處理部分的技術可對祕密數據進行操作,然後再進行可明確運行的順序部分,這是有用的,而混淆電路並不是實現這一點的唯一技術。一般來說,關於隨機編碼的文獻,包括很多更復雜的技術,這一數學分支在函數加密和模糊處理等技術中也是很有用的。

來源鏈接:www.8btc.com