泛型群模型：在主定理證明中使用多項式
我一直在看 Boneh, Boyen, Goh Hierarchical Identity Based Encryption with Constant Size Ciphertext的論文 ，其中包含關於攻擊者在通用組模型中的優勢的一般定理（定理 A.2）。它似乎基於這樣的想法，即在通用雙線性組模型中，我們只能計算給定輸入的線性組合以及在計算配對時將線性多項式相乘一次。他們爭論的是，如果隨機抽樣的輸入是 $ x_1,\ldots,x_n $ 我們已經計算了兩個（最多二次）多項式 $ L_i(x_1,\ldots,x_n) $ 和 $ L_j(x_1,\ldots,x_n) $ , 然後相等檢查
$$ L_i(x_1,\ldots,x_n)=L_j(x_1,\ldots,x_n) $$ 可以用相等檢查代替
$$ L_i(X_1,\ldots,X_n)=L_j(X_1,\ldots,X_n), $$ 即我們檢查是否相等作為多項式，而不是評估多項式。
證明的一般思想是，我們可以事後檢查對手看到這兩種情況之間差異的機率是多少。這似乎是基於這樣的想法，即對於隨機多項式，我們有一個隨機採樣點是根的機率的上限。
我對這個證明的問題是，由於計算中出現的多項式取決於對手從之前的預言機查詢中獲得的資訊，所以多項式列表 $ L_1,\ldots,L_q $ 已自適應建構。因此，列表不獨立於採樣值 $ x_1,\ldots,x_n $ . 我看不出在證明中如何考慮到這一點？任何人都願意更詳細地解釋這一點，因為後來所有具有類似定理的論文似乎也迴避了這個問題。
該問題可以簡化為以下問題，因為標準參數並沒有真正考慮到您不能生成給定最大度數的所有多項式：
假設我們已經採樣了一個隨機點 $ \vec{x}\in \mathbb{F}_p^n $ . 我們讓對手自適應地選擇最多次數的多項式 $ d $ 在每一個選擇之後，我們告訴你是否 $ \vec{x} $ 是所選多項式的根。然後 $ q $ 查詢，攻擊者找到一個多項式的機率 $ \vec{x} $ 是一個根在上面有界
$$ \frac{qd}{p}. $$
我們所知道的是，一個隨機元素在 $ \mathbb{F}_p^n $ 是某個多項式的根 $ d $ 上界為 $ d/p $ . 因此，攻擊者本質上最多選擇大小的子集 $ d/p\cdot p^n $ ，因為我們只關心根，而不關心實際的多項式。因此，問題等同於以下問題：
假設我們選擇了一個隨機點 $ x $ 在一組 $ S $ 大小的 $ p $ . 我們讓攻擊者自適應地選擇 $ d $ 在每一輪得分，然後告訴攻擊者是否 $ x $ 是其中 $ d $ 點。那麼之後的機率 $ q $ 查詢我們選擇了一組包含的點 $ x $ 上界為 $ qd/p $ .
我們通過歸納證明上限由下式給出 $ qd/p $ . 這顯然適用於一個查詢，因為在第一次嘗試時我們只是選擇一組大小 $ d $ 和機率 $ x $ 在這個集合中是 $ d/p $ . 現在通過歸納假設獲勝機率 $ q $ 查詢是 $ qd/p $ . 現在有了 $ q+1 $ 查詢，我們要麼在第一場比賽中獲勝 $ q $ 查詢，否則我們不會並贏得 $ q+1 $ 英石。由此我們得到
$$ \frac{qd}{p}+\frac{d}{p-dq}\left(1-\frac{qd}{p}\right)=\frac{(q+1)d}{p} $$
然而，文獻中的現有證明都沒有討論對手自適應地選擇多項式這一點，這是正確的。所有的證明只是說最後我們有 $ (s+q)^2 $ 可能的多項式和一個隨機元素是一個根的機會是 $ (s+q)^2d/p $ ，在這種情況下這不是一個真正有效的論點，儘管你得到了相同的界限。