1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.