计算$g^y\bmod p$从$g^{y^2}\bmod $如果Diffie-Hellman被破坏？

Question

给定乘法群模的生成元g，一个素数p，由g^x\bmod p和g^y\bmod p求出g^{xy}\bmod p问题。解决这个问题的最好方法是通过离散对数。假设我们可以在不打破离散对数的情况下做到这一点。

那么从g^z\bmod p到g^{z^2}\bmod p的计算在多项式时间内可行吗？

Answer 1

那么从g^z\bmod p到g^{z^2}\bmod p的计算在多项式时间内可行吗？

如果我们假设我们知道q的g顺序，并且它是素数，那么是的，它是可行的。

然后，我们可以将这个子组的成员看作一个抽象组，其中每个成员对于某些g^a都是a。在这个抽象组中，我们可以使用Oracle执行乘法，也就是说，给定g^a和g^b，我们可以计算g^{ab \bmod q}。通过推广，我们可以在多项式时间内进行指数运算，即在给定g^a和整数c的情况下，可以计算g^{a^c \bmod q}。并且，我们可以计算相加逆(给定g^a，我们可以计算g^{-a \bmod q})。

我们在这个组中还有一个相等运算符，即给定g^a和g^b，我们可以确定a \equiv b \pmod q)。

这些操作足以在抽象组内实现托内利-香克算法；这允许我们在多项式时间1中计算平方根，特别是给定g^{z^2}，以恢复两个平方根元素g^z和g^{-z}。

1：概率多项式时间，如果q \equiv 1 \pmod 4；然而，概率步骤是找到一个二次非剩余，而这只需要对一个特定的组做一次。