來自矩陣分支程序的 iO
最近我正在學習如何通過多線性映射從矩陣分支程序建構 iO（確切地說，
$$ GGH+13 $$和$$ GGH15 $$）。但是，我有一個小問題，我無法弄清楚。 似乎將程序/電路轉換為混淆的步驟是首先將其轉換為 MBP（一堆 $ M_{i,b} $ s) 離開
$$ Bar86 $$. 然後，我們可以使用 Kilian 隨機化來添加隨機 2k $ R_i, R_i^{-1} $ 使 MBP 矩陣分佈看起來隨機的矩陣。接下來，我們將其放入允許人們進行加法/乘法加零測試的 MMap 框架中。最後，還有一些結構可以保護輸入混合攻擊。 我的問題是為什麼我們需要把這個 MBP 放到 MMap 框架中？似乎在 Kilian 隨機化之後，MBP 中的矩陣看起來已經是隨機的並且不會洩漏資訊。我們不能將隨機 MBP 作為程序的混淆版本發布嗎？我覺得我在這裡遺漏了一些東西……
問題是兩個相同長度的部分評估 $ \ell $ 將有形式 $ R_0 B_1 R_\ell^{-1} $ 和 $ R_0 B_2 R_\ell^{-1} $ . 因此，因為攻擊者可能知道 $ B_1 $ 和 $ B_2 $ ，他們可以了解一些關於被混淆的分支程序的資訊。用多線性映射對這些隨機矩陣進行編碼隱藏（或至少試圖隱藏）這些關係。
考慮 iO 的安全定義。它說攻擊者選擇了兩個等效的分支程序 $ P_1 $ 和 $ P_2 $ ，將它們發送到混淆器，然後接收混淆程序 $ P $ . 目標是猜測是否 $ P $ 對應於 $ P_1 $ 或者 $ P_2 $ .
現在，如果在沒有多線性映射的情況下進行混淆，攻擊者可以破壞安全定義，如下所示：
- 選擇兩個不同的矩陣 $ A $ 和 $ B $ ;
- 選擇長度為 2 的分支程序 $ P_1 $ 單個輸入位如下： $$ \text{bit 0:} ~ ~ ~ ~ I ~ ~ ~ ~ A $$ $$ \text{bit 1:} ~ ~ ~ ~ I ~ ~ ~ ~ B $$ $$ \text{inp}(1) = \text{inp}(2) = 1 $$
- 選擇長度為 2 的分支程序 $ P_2 $ 單個輸入位如下： $$ \text{bit 0:} ~ ~ ~ ~ A ~ ~ ~ ~ I $$ $$ \text{bit 1:} ~ ~ ~ ~ B ~ ~ ~ ~ I $$ $$ \text{inp}(1) = \text{inp}(2) = 1 $$
請注意 $ P_1(0) = P_2(0) = A $ 和 $ P_1(1) = P_2(1) = B $ ，因此，它們是等效的程序。
現在，如果 $ P $ 混淆 $ P_1 $ , 它的形式是 $$ \text{bit 0:} ~ ~ ~ ~ R_1 \cdot R_2^{-1} ~ ~ ~ ~ ~ ~ ~ ~ R_2 \cdot A \cdot R_3^{-1} $$ $$ \text{bit 1:} ~ ~ ~ ~ R_1 \cdot R_2^{-1} ~ ~ ~ ~ ~ ~ ~ ~ R_2 \cdot B \cdot R_3^{-1} $$
因此，我們可以通過檢查與第一步對應的矩陣是否相等來區分混淆程序。