Let $G$ be a cyclic group of order $n$, with $n$ an RSA modulus. Let $g$ be a random element generating $G$, and $h$ another element which discrete logarithm to the base $g$ is unknown.

Given an element $y \in G$, a representation of $y$ to the bases $g$ and $h$ is a pair $(x_1, x_2)$ such that

$$y = g^{x_1} h^{x_2}.$$

This definition can of course be extended to tuples of arbitrary length, but I am mostly concerned with the case of two bases. This concept is useful, e.g., in the proof/signature of knowledge of representation.

My question is: is such a representation unique?

That is, is there a pair $(x_1', x_2') \neq (x_1, x_2) : y = g^{x_1'} h^{x_2'}$ ? Why/why not?


This representation is not unique. If $k$ is the discrete logarithm of $h$ with relation to base $g$, then $$y = g^{x_1}h^{x_2} = g^{x_1}(g^{k})^{x_2} = g^{x_1 + k \cdot x_2}$$

Then for any $m$, $$x_1' = x_1 + m \cdot k,$$ $$x_2' = x_2-m$$ is another pair such that $y=g^{x_1}h^{x_2}=g^{x_1'}h^{x_2'}$.

We can reduce the discrete logarithm problem to finding a second pair $x_1', x_2'$. Given a second pair, we can efficiently compute:

$$ m \equiv x_2 - x_2' \mod n$$ $$ k \equiv (x_1' - x_1) \cdot m^{-1} \mod n$$ $$ k \equiv (x_1' - x_1)(x_2 - x_2')^{-1} \mod n$$

So finding a second pair is at least as hard as solving the discrete logarithm problem.

  • $\begingroup$ That's right. If we consider that such a $k$ is unknown however (as per definition of $h$), can we consider that it is hard to find a different representation? Maybe I should rephrase my question. Thanks! $\endgroup$
    – doc
    Dec 5 '17 at 22:29
  • $\begingroup$ @doc Finding a second pair given $(g, h, x_1, x_2)$ is exactly as hard as solving the discrete logarithm problem for $(G, g, h)$. I've updated my answer with a one-way reduction. $\endgroup$
    – knbk
    Dec 5 '17 at 23:37
  • $\begingroup$ What this means, of course, is that a kleptographer designing this system could choose $g$ and $h$ to implant a back door that nobody else can figure out! $\endgroup$ Dec 6 '17 at 2:31

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.