与离散对数有关的问题

Question

设G是一个循环群的生成元，其中离散对数问题是困难的，x和u分别是该群的标量，使得X = xG和U = uG分别成为该群的标量。我们要计算J = x^{-1}U。即使我们知道x，也可以在不知道u的情况下计算它吗？

Answer 1

这个问题等价于计算Diffie问题；即使我们知道u，这仍然是正确的。

有关详细信息，请参见本论文；总之：

• 假设我们有一个甲骨文，给定G，X = xG，或者(取决于甲骨文类型) U = uG或u，给出值J = x^{-1}uG。然后，我们可以使用这个Oracle构造第二个Oracle，给定H, aH，计算a^2H (通过传递G = aH、X = H = a^{-1}G、U=G (或u=1)并恢复J = (a^{-1})^{-1} \cdot 1 \cdot aH = a^2H )。然后，我们可以使用第二个Oracle来解决CDH问题(给定G, aG, bG，我们计算(2ab)G = (a+b)^2G - a^2G - b^G，然后进行点减半。
• 假设我们有一个解决CDH问题的oracle，即给定H, aH, bH，给出值abH。然后，给定G，xG，我们可以通过设置H = xG、aH = bH = G = x^{-1}H和bH = H来计算x^{-1}G。我们将其交给Oracle，它为我们提供了值(x^{-1} \cdot x^{-1}) H = x^{-1}G。然后，我们可以将该值转换为J，方法是将其乘以u (如果我们知道的话)，或者再次使用输入G, x^{-1}G, uG调用CDH。