CDH算法构造

Question

如果A是解决输入\frac{1}{2}的计算Diffie-Hellman问题并返回一个特殊符号的有效算法，那么如何使用A构造另一种算法B，以更高的概率求解CDH (1 -\frac{1}{2^k})？

Answer 1

假设C_k: (g, g^a, g^b) \mapsto g^{ab}是你的CDH-解算器，它用概率1 - \frac{1}{2^k}解决它，否则用特殊的符号解决它.让我们从C_1递归地构造它们。

C_{k+1}的建设：

1. 计算C_k(g, g^a, g^b)。如果它返回g^{ab}，输出它(这的概率是1 - \frac{1}{2^k})。否则，进入第二步。
2. 生成两个独立的随机数x和y，从1到p-1均匀分布。
3. 计算g^{ax}和g^{by}。请注意，它们独立于g^a和g^b。
4. 计算C_1(g, g^{ax}, g^{by})。如果返回特殊符号，则输出它(概率为\frac{1}{2^{k+1}})。否则，它已经计算了g^{abxy}。进入第五步。
5. 使用扩展的欧几里德算法来查找z，例如xyz \equiv 1 (\mod p-1)。
6. 计算g^{abxyz} = g^{ab}并输出它(概率为\frac{1}{2^{k+1}})。

不难看出，现在输出g^{ab}的总概率是1 - \frac{1}{2^k}。