# Double discrete logarithm on elliptic curve

Background:

I am attempting to implement the paper Publicly Verifiable Secret Sharing. I managed to get it working using modular groups, but when I want to make it more efficient by transferring to elliptic curve groups, Section 3.1 in the paper gives me problems:

Let $$p$$ be a large prime.

$$G$$ is a group of order $$p$$

$$g$$ is a generator of $$G$$

$$q = (p - 1)/2$$ is prime.

$$h$$ $$\epsilon$$ $$\Bbb Z_p^*$$ is an element of order q.

The double discrete logarithm of $$y$$ to the bases $$g$$ and $$h$$ is defined as $$x$$ where:

$$y = g^{(h^x)}$$

Question:

Implementing this double exponentiation is straightforward in modular groups since $$h^x$$ can be naturally interpreted as an integer. However, in the case of elliptic curves, $$h^x$$ is interpreted as the point $$h$$ added to itself $$x$$ times, resulting in curve point, $$[x]h$$. It is then unclear to me how to get $$y = g^{(h^x)}$$, knowing $$g$$, $$h$$ and $$x$$. To calculate a curve point to the power of another curve point does not seem possible to me.

The folklore is that any cryptographic scheme based on a modular multiplicative group can be translated to an additive curve group. However, I don't see how this case. Can this double exponentiation be done on an elliptic curve or is is only possible in modular groups?

• – kelalaka Jan 27 at 17:28

However, in the case of elliptic curves, $$h^x$$ is interpreted as the point $$h$$ added to itself $$x$$ times, resulting in curve point, $$[x]h$$

That is incorrect; as you had stated previously:

$$h \in \mathbb{Z}_p^*$$ is an element of order $$q$$.

That is, $$h$$ is not a point on the elliptic curve; instead, it is a member of a finite field, and so $$h^x$$ is interpreted as $$h$$ multiplied to itself $$x$$ times (using the field multiplication operation).

The folklore is that any cryptographic scheme based on a modular multiplicative group can be translated to an additive curve group.

One has to be careful; there are schemes such as SRTP that really rely on a modular field (rather than a modular group).

However, even in those cases where things can translate nicely (which are actually most of them; exceptions are comparatively rare), you do have to remember that, while the actual group operation (modular multiplication) translates into point addition, the operations on the exponents (which are done modulo $$p-1$$ in the modular case) translate to integer operations modulo $$q$$ in the Elliptic Curve case.