使用亂碼電路的與門的具體範例
大多數線上資源(如wiki)都以一種相當不必要的抽象方式呈現了亂碼電路的美妙想法。這是 Wiki 協議的截圖:
第 2 步的範例是什麼?愛麗絲是如何弄亂電路的?使用任何公鑰加密或私有?誰能給我一個任何門的*具體例子,比如使用這個原語嗎?*就像,在位串級別。例如,假設愛麗絲有一點 $ 0 $ , Bob 有一點 $ 1 $ . 他們想計算 AND。謝謝!
亂碼背後的主要概念思想是用(對稱密鑰)加密方案的密鑰“標記”電路中線路上的布爾值。然後根據這些標籤而不是基礎布爾值進行計算。在剩下的時間裡,我將使用 $ \mathsf{in}_0, \mathsf{in}_1, \mathsf{out} $ 表示與門的兩條輸入線和(單條)輸出線。如果我們將它們視為直接取布爾值,則它們滿足等式:
$$ \mathsf{in}_0\land \mathsf{in}_1 = \mathsf{out} $$ 特別是,給定 $ \mathsf{in}_0, \mathsf{in}_1 $ ,我們可以計算 $ \mathsf{out} $ 使用這個公式。
使這種計算“私有”的一種方法是,如果不是直接擁有 $ \mathsf{in}i $ 和 $ \mathsf{out} $ 取布爾值,我們會在某種程度上“混淆”事物。生成密鑰 $ k{\mathsf{in}0, 0}, k{\mathsf{in}0, 1}, k{\mathsf{in}1, 0}, k{\mathsf{in}1, 1}, k{\mathsf{out}, 0}, k_{\mathsf{out}, 1} $ . 請注意,恰好有 6 個鍵 — 對於電路中的(三)條線中的每條線,我們為線可以採用的每個可能值生成一個鍵。
現在如果有人給我兩把鑰匙 $ k_{\mathsf{in}0, i}, k{\mathsf{in}1, j} $ ,我不知道鍵的“價值”是什麼 $ i $ 和 $ j $ 是。但我也不知道如何計算鍵的與,這意味著我還不能計算 $ k{\mathsf{out}, i\land j} $ . 如果我能以某種方式(不學習價值觀 $ i $ 和 $ j $ 直接)我們就完成了。
Garbling 允許我們通過計算四個密文來做到這一點 $ C_{i, j} = \mathsf{Enc}{k{\mathsf{in}0, i}}(\mathsf{Enc}{k_{\mathsf{in}1, j}}(k{\mathsf{out}, i\land j})) $ . 如果我們知道兩個鍵 $ k_{\mathsf{in}0, i} $ 和 $ k{\mathsf{in}1, j} $ ,我們可以解密密文 $ C{i, j} $ 學習 $ k_{\mathsf{out}, i\land j} $ . 但是,如果我不知道這些密鑰,那麼通過底層加密方案的安全性,我將無法解密 $ C_{i, j} $ ,將可能計算的“其餘部分”保持為“私有”。
所以 Alice 的工作(在亂碼步驟中)是生成上述所有資訊:
- 電路中的每根電線都有兩個鍵。
- $ 2k $ 每個的密文 $ k $ -電路中的arity門。
這個過程被稱為“亂碼”電路。
$ \newcommand{\AK}{\mathsf{K}} \newcommand{\AE}{\mathsf{E}} \newcommand{\AD}{\mathsf{D}} \newcommand{\out}{\leftarrow} $
對於第 2 步,姚的原始構造
$$ Y $$依賴於對稱加密方案 $ (\AK,\AE,\AD) $ . 高層次的想法是關聯每條線 $ w $ 在電路中用一對鑰匙 $ k_w^0,k_w^1\out\AK $ 然後計算密鑰。為此,我們為每個門構造了一個“亂碼表”,直覺上就是對門的真值表的加密。 讓我們暫時假設電路僅包含與門。讓 $ a $ 和 $ b $ 表示其輸入線和 $ c $ 表示其輸出線。亂碼表由以下四個密文組成: $$ \begin{matrix} c_{00}=\AE_{k_a^0}\left(\AE_{k_b^0}(k_c^0)\right) & c_{01}=\AE_{k_a^0}\left(\AE_{k_b^1}(k_c^0)\right) \ c_{10}=\AE_{k_a^1}\left(\AE_{k_b^0}(k_c^0)\right) & c_{11}=\AE_{k_a^1}\left(\AE_{k_b^1}(k_c^1)\right)\end{matrix} $$ 電路的亂碼(AND)由亂碼表組成 $ \mathbf{c}={c_{00},c_{01},c_{10},c_{11}} $ 和輸出地圖 $ (k_c^{0}\mapsto 0,k_c^1\mapsto 1) $ .
現在,讓我們看看 Alice 如何輸入 $ x $ , 和 Bob, 輸入 $ y $ , 聯合計算 $ x\wedge y $ . Alice 如上所述計算亂碼電路(即密文和輸出映射)(步驟 2)。接下來,她將亂碼電路連同密鑰一起發送 $ k_a^x $ (她的輸入加密)給 Bob(步驟 3)。然後 Bob 獲得了他的亂碼輸入 $ k_b^y $ 通過不經意轉移(步驟 4)。鮑勃現在通過表演“明白了”$$ \AD_{k_b^y}\left(\AD_{k_a^x}(c_i)\right) $$對於每個密文 $ c_i\in\mathbf{c} $ ,將結果與輸出映射進行比較,並輸出匹配的位(步驟 5)。請注意,Bob 只能正確解密其中一個密文,即對應於正確輸入的密文(密鑰 $ k_a^x $ 和 $ k_b^y $ ).
一般來說,(布爾)門的亂碼表 $ g:{0,1}^2\rightarrow{0,1} $ , 由密文組成 $$ \begin{matrix} c_{00}=\AE_{k_a^0}\left(\AE_{k_b^0}(k_c^{g(0,0)})\right) & c_{01}=\AE_{k_a^0}\left(\AE_{k_b^1}(k_c^{g(0,1)})\right) \ c_{10}=\AE_{k_a^1}\left(\AE_{k_b^0}(k_c^{g(1,0)})\right) & c_{11}=\AE_{k_a^1}\left(\AE_{k_b^1}(k_c^{g(1,1)})\right)\end{matrix} $$ 然而,要弄亂任意電路,只需弄亂它的組成門。為什麼建設完成?因為底層加密方案是完整的。為什麼它是安全的?從 Alice 的角度來看,給定密鑰 $ k_a^x $ 和密文 $ \mathbf{c} $ , 她的輸入 $ x $ 由於加密方案,在計算上對 Bob 是隱藏的。(選擇性)安全性在很久以後才正式討論過,並在對稱加密方案上做了一個溫和的附加假設
$$ LP $$. $$ Y $$Yao,安全計算協議,FOCS 1982。 $$ LP $$林德爾和平卡斯。Yao 的兩方計算協議的安全性證明,JoC 2009。