對基於身份的加密的一種可能更強的攻擊類型
關於基於身份的加密方案對涉及查看多個密文然後接收與其中一些密文對應的私鑰的攻擊的安全性，我們了解多少？
例如，是否已知可行的對手將有一個可以忽略不計的（在安全參數中 $ k $ ) 對於 IND-CCA2 IBE 方案，以下成功的機率是多少？
- 挑戰者生成 $ :\langle $ 酒吧，MSK $ \rangle: $ 然後給 $ : $ 酒館 $ : $ 到 $ \mathcal{A} $
- $ \mathcal{A} $ 輸出一個列表 $ :(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)\hspace{-0.01 in}+\hspace{-0.02 in}1: $ 不同的 ID
- 挑戰者選擇 $ :x\in {0,\hspace{-0.04 in}1}^k: $ 均勻地
- 挑戰者計算 $ :(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)\hspace{-0.01 in}+\hspace{-0.02 in}1: $ 沙米爾的股份 $ x $ 所以需要 $ :k\hspace{-0.03 in}+\hspace{-0.04 in}1: $ 其中恢復 $ x $
- 挑戰者使用加密這些共享 $ : $ 酒館 $ : $ 以及由提供的列表中的相應 ID $ \mathcal{A} $
- Challenger 將生成的密文列表提供給 $ \mathcal{A} $
$ \mathcal{A} $ 輸出一個列表 $ k $ 身份證
- 挑戰者用途 $ :\langle $ 酒吧，MSK $ \rangle: $ 提取這些 ID 的私有解密密鑰
- Challenger 將對應的私有解密密鑰列表提供給 $ \mathcal{A} $ $ \mathcal{A} $ 輸出 $ y $
$ \mathcal{A} $ 當且僅當成功 $ y = x $
您可能可以通過 Boneh 和 Franklin 的 IND-ID-CCA 遊戲中的安全性來證明您的遊戲的安全性（參見http://courses.cs.vt.edu/cs6204/Privacy-Security/Papers/Crypto/IBE-威爾配對.pdf )。這個想法是創造一個對手 $ \mathcal{B} $ 對抗來自對手的 IND-ID-CCA $ \mathcal{A} $ . 本質上 $ \mathcal{B} $ 將在 IND-ID-CCA 挑戰者和 $ \mathcal{A} $ .
什麼時候 $ \mathcal{B} $ 收到 $ 2k+1 $ 身份來自 $ \mathcal{A} $ ，他隨機選擇其中一個（我們稱之為 $ ID_0 $ ) 發送兩個隨機值 $ (x_0,x_0’) $ 和…一起 $ ID_0 $ 給挑戰者並接收加密 $ C_0 $ 任何一個 $ x_0 $ 或者 $ x’0 $ . 對於其他每個身份 $ ID_i $ , $ \mathcal{B} $ 加密值 $ x_i $ 以這樣的方式選擇 $ (x_0,\cdots, x{2k+1}) $ 是秘密共享的有效共享，密文表示為 $ C_i $ . 然後 $ \mathcal{B} $ 將密文返回給 $ \mathcal{A} $ .
$$ Note that if the challenger has chosen $x_0$ your game is perfectly emulated, otherwise, the shares are invalid $$ 什麼時候 $ \mathcal{A} $ 發送 $ k $ 身份，如果 $ ID_0 $ 在集合中 $ \mathcal{B} $ 中止與 $ \mathcal{A} $ 並將隨機猜測返回給挑戰者。除此以外， $ \mathcal{B} $ 問 $ k $ 挑戰者的鑰匙並將其發送到 $ \mathcal{A} $ . 什麼時候 $ \mathcal{A} $ 返回 $ y $ , $ \mathcal{B} $ 進行如下：如果 $ y $ 與份額一致 $ x_0 $ ， 然後 $ \mathcal{B} $ 猜測挑戰者返回了一個加密 $ x_0 $ ， 除此以外 $ \mathcal{B} $ 隨機猜測。
如果 $ \mathcal{A} $ 以機率贏得比賽 $ \epsilon $ , 的優勢 $ \mathcal{B} $ 大約是 $ \epsilon/4 $ .
附加資訊：
- 優點不是 $ \epsilon/2 $ 正如我最初寫的那樣，但是 $ \epsilon/4 $ ，這是由於區分器的優勢有兩種可能的定義。一些論文使用差值的絕對值來 $ 1/2 $ 有些論文使用了兩倍。出於技術原因，最好有兩倍的差異，而且我最初並沒有註意到 Boneh-Franklin 不使用這個版本。
- 優勢是如何計算的？這需要一個我沒有提到的額外假設。以可變數量的份額進行遊戲，例如 $ \ell $ , 保持 $ k $ 固定並表示為 $ \ell_0 $ 存在具有不可忽略優勢的對手的最小值。顯然，如果存在一個對手 $ \ell=2k+1 $ 然後 $ \ell_0\leq 2k+1 $ . 而且當然， $ \ell_0>k $ 因為與 $ k $ 您沒有任何資訊的股票 $ x $ .
如果 $ \ell_0=2k+1 $ 使用上述推理。在這種情況下， $ \mathcal{A} $ 無法返回 $ y=x $ 當一股包含 $ x’_0 $ 因為你可以改變 $ \mathcal{A} $ 成為對手 $ \ell_0-1 $ 只需添加一個隨機值的份額即可。如果 $ \ell_0<2k+1 $ ，用新的重新推理 $ \ell_0 $ . 這改變了優勢 $ \frac{(\ell_0-k)\epsilon}{2k} $ . 唯一的問題是，在這種情況下 $ \ell_0=k+1 $ ，減少不緊。
回應 Ricky 對減少緊張程度的評論：
我看不出你是如何獲得指數級退化的 $ k $ . 如果您不假設成功機率從可忽略到不可忽略，而是進行更精確的分析，那麼這裡是對整個遊戲的更精確分析。
讓 $ \epsilon_\ell $ 成為贏得比賽的對手的最大優勢 $ \ell $ 查詢。注意 $ \epsilon_\ell $ 形成一個遞增的序列。
此外，您的原始遊戲的優勢是：
$$ \epsilon=\epsilon_{2k+1}=\sum_{i=k+1}^{2k+1}\epsilon_i-\epsilon_{i-1}. $$ 因此，至少有一個差異大於 $ \epsilon/(k+1) $ . 跑 $ \mathcal{A} $ 為 $ \ell_0 $ 這樣 $ \epsilon_{\ell_0}-\epsilon_{\ell_0-1} $ 是不是太小了。的機率 $ \mathcal{A} $ 獲勝 $ \ell_0 $ 真股比假股的機率高至少 $ \epsilon_{\ell_0}-\epsilon_{\ell_0-1} $ ， 除此以外 $ \mathcal{A} $ 可以用來改善 $ \epsilon_{\ell_0-1} $ .
作為結果， $ \mathcal{B} $ 至少以優勢獲勝 $ \frac{(\ell_0-k)(\epsilon_{\ell_0}-\epsilon_{\ell_0-1})}{2k}\geq \frac{(\ell_0-k)\epsilon}{2k^2} $ .
所以退化是多項式的 $ k $ 不是指數的。