密钥协商协议通信下界与极损函数研究

### 密钥协商协议通信下界与极损函数研究 #### 密钥协商协议通信下界分析 在密钥协商协议的研究中，我们聚焦于攻击者的效率和准确性，以及协议通信复杂度的下界。 ##### 攻击者准确性 考虑一个由 $\ell$ 个预言机辅助的非自适应 $(1, q, \gamma)$ 密钥协商协议 $\Pi$。若 $\Pi$ 是归一化的，那么存在一个算法 $E$，它猜测密钥正确的概率至少为 $1 - \sqrt{2\varepsilon}$，即： \[Pr_{v=(r_A,r_B,f)\leftarrow EV} [E_f(tran(v)) = out_A(v)] > 1 - \sqrt{2\varepsilon}\] 这里的证明基于引理 3，$E$ 输出 $out_A(v)$ 的错误概率小于 $\sqrt{2\varepsilon}$。 ##### 攻击者效率 为了分析攻击者 Eve（算法 1）的效率，我们引入了密度函数 $\Phi(\tau, f_E)$，其定义为： \[\Phi(\tau, f_E) \triangleq H (F | R_A, R_B, F (Q_E) = f_E) - H (F | R_A, R_B, F (Q_E) = f_E \land T = \tau)\] 其中，$(R_A, R_B, F)$ 是随机扩展视图，$T \triangleq tran(R_A, R_B, F)$。 密度函数 $\Phi$ 具有以下性质： 1. **非负性**：$\Phi$ 是非负的，因为 $F$ 在给定 $R_A, R_B$ 和 $F (Q_E) = f_E$ 的条件下是均匀分布。 2. **期望上界**：$E_{\tau\leftarrow T} [\Phi(\tau, f_{\varnothing})] \leq CC(\Pi)$，其中 $f_{\varnothing}$ 表示空函数。 3. **相关性递减**：若 $S$ 关于 $(\tau, f_E)$ 是 $\varepsilon$-相关的，则 \[E_{f_S\leftarrow F (S)|T = \tau,F (Q_E) = f_E} [\Phi(\tau, f_E \cup f_S)] \leq \Phi(\tau, f_E) - \varepsilon\] 基于这些性质，我们可以推断出算法 $E$ 运行的迭代次数期望至多为 $\frac{CC(\Pi)}{\varepsilon}$，即： \[E[\text{# of iterations in the running of } E] \leq \frac{CC(\Pi)}{\varepsilon}\] 然而，算法 1 在最坏情况下可能会进行过多的查询。为了解决这个问题，我们构造了一个新的攻击者 $E'$，它在迭代次数超过 $\frac{CC(\Pi)}{\varepsilon^{3/2}}$ 时中止。$E'$ 具有以下特性： 1. **效率**：