27、超椭圆曲线迪菲 - 赫尔曼问题的比特安全性与自然 sd - RCCA 安全公钥加密方案

超椭圆曲线迪菲 - 赫尔曼问题的比特安全性与自然 sd - RCCA 安全公钥加密方案

超椭圆曲线迪菲 - 赫尔曼问题的比特安全性

超椭圆曲线密码学是椭圆曲线密码学的一种替代方案。在超椭圆曲线迪菲 - 赫尔曼问题（DHP）中，研究其比特安全性具有重要意义。

任意比特的扩展

对于任意的 (z = \sum_{i = 0}^{n} z_{i}2^{i})，(bit_{i}(z)) 表示 (z) 的二进制表示中的第 (i) 位，最低有效位 (LSB(z) = bit_{0}(z))。如果超椭圆曲线迪菲 - 赫尔曼问题是困难的，那么超椭圆曲线迪菲 - 赫尔曼值的每一位（即 (bit_{i}(z))）都是不可预测的。有两种方法可以实现这一目标：
- 从 LSB - HNP - CM 到 (bit_{i}) - NHP - CM ：H˙astad 和 N¨aslund 以及 Kiltz 等人的研究表明，HNP - CM 可以针对 (z) 的每一位进行定义，相关定理也成立。对于给定的素数 (p) 和 (\alpha \in F_{p})，设 (L : F_{p}^{ } \to {0, 1}) 是一个满足 (Pr_{t \in F_{p}^{ }}[L(t) = bit_{i}(\alpha \cdot t \mod p)] \geq \frac{1}{2} + \epsilon) 的函数。(bit_{i}) - NH 问题是：给定 (L(t)) 的预言机，在多项式时间内找到 (\alpha)。对于所有奇素数 (p)，(bit_{i}) - NHP - CM 对于所有位都是可有效求解的，因此可以将最低有效位的结果扩展到任