量子密码与伪随机函数的安全分析

### 量子密码与伪随机函数的安全分析 #### 1. 量子概率性量子不经意传输方案 在量子概率性量子不经意传输（QPQ）方案中，有诸多关键的安全特性和性能指标值得关注。 ##### 1.1 密钥获取概率 在该方案的单轮操作中，Alice 能够猜测的最终密钥比特（或数据比特）数量为 1。从相关公式可以得出，获取该最终密钥比特的概率下限为 \(P_c \geq 1 - \exp(-1) \approx 0.632\)。这一概率下限为方案的安全性和可靠性提供了一定的保障。 ##### 1.2 设备无关安全性测试 该方案的设备无关（DI）测试分为三个阶段： - **源设备验证阶段的 LocalCHSH 测试**：在这个测试中，要么设备对于 Alice 和 Bob 都达到 \(C = \cos^2\frac{\pi}{8}\)（即共享状态为 EPR 对），要么在渐近极限下协议以高概率中止。这一测试确保了共享状态的正确性和设备的可靠性。 - **Bob 测量设备的 OBStest**：在这个测试中，要么 Bob 的测量设备达到 \(\beta = \frac{1}{\sqrt{2}}|\cos\theta - \sin\theta|\)（即设备能在 \(\{|0\rangle, |1\rangle\}\) 和 \(\{|0'\rangle, |1'\rangle\}\) 基下正确测量），要么在渐近极限下协议以高概率中止。这一测试保证了 Bob 测量设备的功能正常。 - **Alice 的 POVM 元素测试**：根据 Bob 声明的 \(a_i\) 值，Alice 使用设备 \(M_0 = \{M_0^0, M_0^1, M_0^2\}\) 或 \(M_1 = \{M_1^0, M_1^1, M_1^2\}\) 对所选状态进行测量。对于不同的 \(a_i\) 值，测量结果有不同的结论。例如，当 \(a_i = 0\) 时，要么协议在渐近极限下以高概率中止，要么 Alice 的测量设备达到 \(\Omega_0 = \frac{2\sin^2\theta}{1 + \cos\theta}\)；当 \(a_i = 1\) 时，要么协议在渐近极限下以高概率中止，要么 Alice 的测量设备达到 \(\Omega_1 = \frac{2\sin^2\theta}{1 + \cos\theta}\)。 这些测试的结果可以总结为：要么该 DI 方案在渐近极限下以高概率中止，要么它能证明 QPQ 方案中涉及的设备在相应测试中达到预期值。 ##### 1.3 数据库安全对抗不诚实的 Alice 在密钥建立阶段，对于不诚实的 Alice，有以下结论： - 如果 Alice 的测量设备未经过测试，她在密钥建立阶段平均最多能不确定地（即无法确定正确猜测比特的位置）检索到 \(\left(\frac{1}{2} + \frac{1}{2}\sin\theta\right)\) 比例的整个原始密钥比特。 - 对于该 QPQ 方案，数据库包含 \(N\) 个数据比特。不诚实的 Alice 平均能猜测的最终密钥比特比例 \(\tau\) 满足 \(\tau \leq (1 - \cos\theta)k\)，进一步替换可得 \(\tau < \frac{2}{N}\)。这表明在该方案中，\(\tau\) 相对于 \(N\) 较小，即不诚实的 Alice 能获取的信息有限。 ##### 1.4 用户安全对抗不诚实的 Bob 在 QPQ 协议中，经过 Alice 对 \(N\) 比特数据库进行 \(l\) 次查询后，不诚实的 Bob 成功猜测某个特定索引 \(i\) 是否属于 Alice 的查询索引集 \(I_l\) 的概率至多为 \(\frac{l}{N}\)。如果 Bob 猜测 \(l\) 个索引，他正确猜测的索引数量的期望值 \(E[I_{B^*}]\) 满足 \(E[I_{B^*}] \leq \frac{l^2}{N}\)。不诚实的 Bob 平均能猜测的 Alice 查询索引集 \(I_l\) 中的索引比例 \(\delta\) 满足 \(\delta \leq \frac{l}{N}\)，当 \(N \approx l^n\) 时，\(\delta \leq \frac{1}{l^{n - 1}}\)。这表明在该方案中，\(\delta\) 相对于 \(l\) 较小，即不诚实的 Bob 能获取的信息有限。 #### 2. 基于公共随机置换的 PRF 的量子攻击 在对称密钥密码学中，伪随机函数（PRF）起着重要的作用。为了统一分析基于置换的 PRF 的量子安全性，提出了三个通用框架 \(F1\)、\(F2\) 和 \(F3\)。 ##### 2.1 对称密钥方案与 PRF 消息认证码（MAC）是确保消息完整性的对称密钥原语。对于流行的基于随机数的 MAC，如 Wegman - Carter 方案，用伪随机函数（PRF）替换底层的伪随机置换（PRP）可以提供更好的安全性。其他密码设计，如加密模式 CTR 和认证加密模式 GCM，用 PRF 替换底层的 PRP 也能提供更好的安全性。因此，设计固定输入长度的 PRF 非常必要。 ##### 2.2 超越生日界安全的 PRP - to - PRF 转换方法 有四种主要的 PRP - to - PRF 转换方法可以实现超越生日界的安全性：Trunc、Xop、EDM 和 EDMD。 - **Trunc**：将 \(n\) 比特块密码的输出截断 \(m < n\) 比特，得到 \(\frac{m + n}{2}\) 比特的安全性。 - **Xop**：对于输入 \(M\)，\(Xop_{E_1, E_2}(M) = E_1(M) \oplus E_2(M)\)，基于两个独立的块密码 \(E_1\) 和 \(E_2\)，提供 \(n\) 比特的安全性。 - **EDM**：\(EDM_{E_1, E_2}(M) = E_2(E_1(M) \oplus M)\)，基于两个独立的块密码 \(E_1\) 和 \(E_2\)，提供 \(n\) 比特的安全性。 - **EDMD**：\(EDMDE_{E_1, E_2}(M) = E_2(E_1(M)) \oplus E_1(M)\)，基于两个独立的块密码 \(E_1\) 和 \(E_2\)，提供 \(n\) 比特的安全性。 ##### 2.3 基于置换设计的优势 设计块密码比设计无密钥公共置换更复杂，因为前者涉及评估底层密钥调度算法。基于公共置换的设计不需要存储轮密钥，并且分析基于公共置换的密码设计安全性的理论已经很成熟。因此，基于公共置换直接设计密码方案是一种非常流行的方法。 ##### 2.4 Even - Mansour 构造 Even - Mansou