Double discrete logarithm on elliptic curve

Question

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?

Answer 1

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.