基於密鑰策略屬性的加密的安全證明
我的問題與原始 KP-ABE 論文有關：
http://research.microsoft.com/en-us/um/people/vipul/abe.pdf
我無法理解該方案在選擇性集模型中安全的證明（第 10-13 頁）：
證明：假設存在一個多項式時間的對手 A，它可以在 Selective-Set 模型中以優勢攻擊我們的方案 $ \epsilon $ . 我們建構了一個模擬器 B，可以優勢地玩 Decisional BDH 遊戲 $ \epsilon/2 $ . 模擬過程如下：
我們首先讓挑戰者使用有效的雙線性映射 e 和生成器 g 設置組 G1 和 G2。挑戰者獲得公平的二元硬幣 $ \mu $ ，在 B 的視野之外。如果 $ \mu = 0 $ , 挑戰者集 $ (A, B, C, Z) = (g^a,g^b,g^c,e(g,g)^{abc}) $ , 否則設置 $ (A, B, C, Z) =(g^a, g^b, g^c, e(g,g)^z) $ 對於隨機 $ a, b, c, z $ . 我們假設宇宙，U 被定義。
…
階段 1 A 自適應地請求與任何訪問結構 T 對應的密鑰，使得挑戰集 $ \gamma $ 不滿足 T 。假設 A 請求訪問結構 T 的密鑰，其中 $ T(\gamma) = 0 $ . 為了生成密鑰，B 需要分配一個多項式 $ Q_x $ 學位 $ d_x $ 對於訪問樹 T 中的每個節點。
我們首先定義以下兩個過程：PolySat 和 PolyUnsat。
多衛星 $ (T_x,\gamma,{\lambda_x}) $ : ….
聚未飽和 $ (T_x,\gamma, g^{\lambda_x}) $ ：此過程為具有不滿足根節點的訪問樹的節點設置多項式，即 $ T_x(\gamma) = 0 $ . 該過程採用訪問樹 $ T_x $ （帶有根節點 x）作為輸入以及一組屬性 $ \gamma $ 和一個元素 $ g^{\lambda_x} \in G1 $ （在哪裡 $ \lambda_x \in Z_p $ ）。 它首先定義了一個多項式 $ q_x $ 學位 $ d_x $ 對於根節點 $ x $ 這樣 $ q_x(0) = \lambda_x $ . 因為 $ T_x(\gamma) = 0 $ ， 不超過 $ d_x $ 的孩子 $ x $ 滿意。讓 $ h_x \leq d_x $ 是滿足的孩子的數量 $ x $ . 對於每個滿意的孩子 $ x’ $ 的 $ x $ ，程序選擇一個隨機點 $ \lambda_{x’} \in Z_p $ 並設置 $ q_x(index(x’)) = \lambda_{x’} $ . 然後它修復剩餘的 $ d_x - h_x $ 的點 $ q_x $ 隨機完全定義 $ q_x $ .
…
為訪問結構提供密鑰 $ T $ , 模擬器首先執行PolyUnsat $ (T,\gamma,A) $ 定義多項式 $ q_x $ 對於每個節點 $ x $ 的 $ T $ .
…
我的問題與最後（粗體）段落有關：如何定義這樣的 $ q_x $ ，因為模擬器無法學習 $ \lambda_{x} $ 從 $ g^{\lambda_x} $ 除非他可以計算離散對數？
我已經設法找出我自己問題的答案，所以我想我會在這里分享它，以防其他人遇到同樣的問題。
模擬器的設置 $ B $ 是為了模擬遊戲中的挑戰者 $ A $ ，其中挑戰者擁有主秘密 $ ab $ ， 在哪裡 $ g^a, g^b $ 作為 BDDH 遊戲的輸入給出。現在當然 $ B $ 學不會 $ a $ , $ b $ ， 或者 $ ab $ ，但它可以為訪問樹構造私鑰 $ T $ 隱含地分享秘密 $ ab $ .
PolyUnsat _ $ (T_x,\gamma,g^a) $ 被呼叫來拆分秘密 $ a $ 分享，使得他們的組合滿足 $ T_x $ 會恢復 $ a $ . 請注意 $ T_x(\gamma)=0 $ .
它首先定義了一個多項式 $ q_x $ 學位 $ d_x $ 對於根節點 x 使得 $ q_x(0)=a $
現在這很容易，因為 $ g^{q_x(0)}=g^a $ 這是作為輸入給出的。完全定義 $ q_x $ ，它需要另一個 $ d_x $ 點。它可以通過分配來做到這一點： $ g^{q_x(i)}=g^{\alpha_i} $ 對於隨機 $ \alpha_i \in Z_q $ . 請注意 $ B $ 不知道 $ q_x $ ，但是以這種方式定義它可以確保它可以計算 $ g^{q_x(j)} $ 對於任何 $ j $ （使用拉格朗日插值），並且 $ g^{q_x(0)} = g^a $ . 就這樣含蓄地分裂了秘密 $ a $ （自己不知道）共享，以便它們可以合併以恢復 $ g^a $ .
對於每個子節點 $ x’ $ 這不是一個滿意的節點，算法呼叫 $ PolyUnsat(T_{x’},\gamma,g^{q_x(index(x’))}) $
現在這很容易做到，因為 $ g^{q_x(index(x’))} $ 可以從計算 $ {g^a, g^{q_x(0)}, g^{q_x(1)}, ..} $ 使用插值。
每個葉節點對應的鍵使用其多項式給出，如下所示：
$ D_x = g^{b.q_x(0)/r_i} $ 如果 $ x \in \gamma $
在這種情況下， $ B $ 知道 $ q_x(0) $ 但不知道 $ b $ . 然而， $ D_x = (g^b)^{q_x(0)/r_i} $ 可以計算，因為 $ g^b $ 給定了，那 $ q_x(0)/r_i $ 眾所周知，因為 $ 1/r_i $ 眾所周知 $ Z_q $ .
$ D_x = g^{q_x(0)/\beta_i} $ 如果 $ x \notin \gamma $
這也是可計算的，因為 $ g^{q_x(0)} $ 已知（不 $ q_x(0) $ )，所以是 $ 1/\beta_i $ .
這些共享是有效的，因為對於任何秘密 $ s $ ，我們可以得到以下有效密文： $ E = \langle\gamma, E’ = m.e(g^a,g^b)^s, {E_i = g^{s.r_i} | i \in \gamma} \ \cup \ {E_i = (g^b)^{s.\beta_i} | i \notin \gamma}\rangle $ . 此外，所有 $ D_x $ 是均勻分佈的，因此它們的分佈與原始遊戲中的分佈相同。
最後，模擬BDDH遊戲，在一個挑戰中 $ {m_0,m_1} $ ，模擬器將擲硬幣並設置 $ E’ = g^h, {E_i = (g^c)^{r_i}} $ . 如果 $ A $ 猜對了，然後 $ g^h = g^{abc} $ , 模擬器贏得 BDDH 遊戲。
因為模擬器選了 $ \gamma $ 生成 $ g^\gamma $ . 他充當破壞選擇性集模型安全遊戲的攻擊者的 ABE 權威，因此他可以使用攻擊者解決決策雙線性 Diffie-Hellman 問題。
作為 ABE 權限的結果，模擬器知道 ABE 權限創建的主機密和所有其他機密。請記住，對於普通的 ABE，權限知道一切，包括使用者的私鑰（屬性）。
證明：假設存在一個多項式時間的對手 A，它可以在 Selective-Set 模型中以優勢攻擊我們的方案 $ \epsilon $ . 我們建構了一個模擬器 B，可以優勢地玩 Decisional BDH 遊戲 $ \frac{\epsilon}{2} $ . 模擬過程如下：
我們首先讓挑戰者使用有效的雙線性映射 e 和生成器 g 來設置組 G1 和 G2。挑戰者擲出公平的二元硬幣 $ \mu $ ，在 B 的視野之外。如果 $ \mu $ = 0，挑戰者集 $ (A; B; C; Z) = (g^a, g^b, g^c, e(g, g)^{abc} ) $ 否則它設置 $ (A; B, C,Z) = (g^a, g^b,g^c, e(g, g)^z) $ 對於隨機 $ a, b, c, z $ . 我們假設宇宙， $ U $ 被定義為。
然後，模擬器開始設置 ABE 系統，以便他可以使用攻擊者
模擬器 B 執行 A。A 選擇屬性集 $ \gamma $ 它希望受到挑戰
$ \gamma $ 與 DBLDH 假設無關。