# Uniqueness of representation of $y$ to the bases $g$ and $h$

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.

• 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! – doc Dec 5 '17 at 22:29
• @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. – knbk Dec 5 '17 at 23:37
• 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! – Squeamish Ossifrage Dec 6 '17 at 2:31