關於沃特世 IBE 的問題
我正在閱讀Brent Waters 的“沒有隨機預言機的基於身份的高效加密” 。
在第 9 頁，我不知道如何
$$ \mathcal{P}_{BDH}=\Pr[\beta’=1]=\Pr[\beta’=1|\textbf{abort}]\Pr[\textbf{abort}]+\Pr[\beta’=1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}] $$ 變成
$$ \mathcal{P}{BDH}=\frac{1}{2}+\frac{1}{2}(\Pr[\overline{\textbf{abort}}|\gamma’=\gamma]\Pr[\gamma’=\gamma]-\Pr[\overline{\textbf{abort}}|\gamma’\neq\gamma]\Pr[\gamma’\neq\gamma]) $$ $$ $$$$ $$ 自從 $$ \Pr[\beta’=1|\textbf{abort}]=\frac{1}{2}, $$ $$ \mathcal{P}{BDH}=\frac{1}{2}\Pr[\textbf{abort}]+\Pr[\beta’=1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}] $$ 在那之後我不能不跟隨。$$ $$ 請幫助我理解沃特斯所說的。
自從我閱讀這篇論文已經有一段時間了，我記得在推導時遇到了很多麻煩。我敢肯定有一種簡單的方法可以看到它，但我看不到它，所以我會用代數蠻力。
首先，一些背景：
當模擬器被賦予一個隨機元素作為元組中的最後一項時，模擬器要麼中止（並猜測 $ \beta’ = 1 $ 有機率 $ \frac12 $ ) 或猜測 $ \beta’ = 1 $
$$ exactly $$當對手猜測正確時 $ \gamma $ . 然而 $ \gamma $ 在這種情況下，將對對手完全隱藏，因此對手很有可能是正確的 $ \frac12 $ .
我添加了這個詞，因為實際上如果模擬器沒有中止，那麼 $ \beta’ = 1 $ 當且當 $ \gamma = \gamma’ $ . 這可以在第 5.1 節末尾的模擬器描述中看到。
我們將從您的簡化表達式開始 $ \mathcal{P}_{BDH} $ . 然後我們有
$$ \begin{align*} \mathcal{P}_{BDH} &= \frac12\Pr[\textbf{abort}] + \Pr[\beta’ = 1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}] \ &= \frac12 + \left(\Pr[\beta’ = 1|\overline{\textbf{abort}}] - \frac12\right)\Pr[\overline{\textbf{abort}}] \end{align*} $$ 對於非中止的情況，我們知道 $ \beta’ = 1 $ 如果 $ \gamma = \gamma’ $ . 所以如果分案 $ \overline{\textbf{abort}} $ 一分為二， $ (\overline{\textbf{abort}} \land \gamma = \gamma’) $ 和 $ (\overline{\textbf{abort}} \land \gamma \neq \gamma’) $ ，我們得到
$$ \begin{align*} \Pr[\overline{\textbf{abort}}] &= \Pr[\overline{\textbf{abort}}] \ &= (\Pr[\overline{\textbf{abort}}|\gamma = \gamma’]\Pr[\gamma = \gamma']
- \Pr[\overline{\textbf{abort}}|\gamma\neq\gamma’]\Pr[\gamma\neq\gamma’]) \end{align*} $$ 由於對手不知道 $ \gamma $ ，我們可以設置 $ \Pr[\gamma=\gamma’] = \frac12 +\epsilon $ （因此 $ \Pr[\gamma\neq\gamma’] = \frac12-\epsilon $ ）。這讓我們
$$ \Pr[\textbf{abort}] = \Pr[\overline{\textbf{abort}}|\gamma = \gamma’](\frac12 + \epsilon)
- \Pr[\overline{\textbf{abort}}|\gamma \neq \gamma’](\frac12 - \epsilon) $$ 所以我們的總機率是 $$ \frac12 + \left(\Pr[\beta’ = 1|\overline{\textbf{abort}}] - \frac12\right)\left(\Pr[\overline{\textbf{abort}}|\gamma = \gamma’](\frac12 + \epsilon)
- \Pr[\overline{\textbf{abort}}|\gamma \neq \gamma’](\frac12 - \epsilon)\right) $$ 到現在為止還挺好。這就是愚蠢的代數的用武之地：讓我們將這些大術語重命名為
$$ \frac12 + (A - \frac12)(B + C) $$ 並註意帶有這些新名稱的所需形式是 $$ \frac12 + \frac12(B - C) $$ 接下來，請注意
$$ A = \Pr[\beta’ = 1|\overline{\textbf{abort}}] = \frac{\Pr[\beta’ = 1 \land \overline{\textbf{abort}}]}{\Pr[\overline{\textbf{abort}}]} = \frac{B}{B + C} $$ 以便 $$ \begin{align*} (A - \frac12)(B + C) &= \left(\frac{B}{B + C} - \frac12\right)(B + C) \ &= \left(\frac{2B - B - C}{2B + 2C}\right)(B + C) \ &= \frac12(B - C) \end{align*} $$ 你去吧！